(self, xs, ys)
| 131 | # 3. Add these polynomials together. |
| 132 | |
| 133 | def lagrange_interp(self, xs, ys): |
| 134 | # Generate master numerator polynomial, eg. (x - x1) * (x - x2) * ... * (x - xn) |
| 135 | root = self.zpoly(xs) |
| 136 | assert len(root) == len(ys) + 1 |
| 137 | # print(root) |
| 138 | # Generate per-value numerator polynomials, eg. for x=x2, |
| 139 | # (x - x1) * (x - x3) * ... * (x - xn), by dividing the master |
| 140 | # polynomial back by each x coordinate |
| 141 | nums = [self.div_polys(root, [x, 1]) for x in xs] |
| 142 | # Generate denominators by evaluating numerator polys at each x |
| 143 | denoms = [self.eval_poly_at(nums[i], xs[i]) for i in range(len(xs))] |
| 144 | invdenoms = self.multi_inv(denoms) |
| 145 | # Generate output polynomial, which is the sum of the per-value numerator |
| 146 | # polynomials rescaled to have the right y values |
| 147 | b = [0 for y in ys] |
| 148 | for i in range(len(xs)): |
| 149 | yslice = self.mul(ys[i], invdenoms[i]) |
| 150 | for j in range(len(ys)): |
| 151 | if nums[i][j] and ys[i]: |
| 152 | b[j] ^= self.mul(nums[i][j], yslice) |
| 153 | return b |
| 154 | |
| 155 | def _simple_ft(field, vals): |
| 156 | assert len(vals) == 2**field.height |
nothing calls this directly
no test coverage detected