You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
At the moment, the logic for sparse polynomial evaluation is:
let total = self.coeffs.iter()
.map(|(i, c)| (*c * point.pow(&[*i as u64])))
.sum();
This recomputes the power of point for each term, which is more costly than need be.
Sparse polynomials for the most part used in vanishing polynomials in our codebase. I suggest we write a fast path for sparse polynomial evaluation, when all terms are powers of 2. (This captures vanishing polynomials for unions of cosets, and vanishing polynomials for subspaces of binary fields)
Then for general sparse polynomial evaluation, I suggest we compare the current method against computing all of the squares, and then make the per-term work just computing the correct product of the squares. (As this removes any duplicate squarings computed)
At the moment, the logic for sparse polynomial evaluation is:
This recomputes the power of point for each term, which is more costly than need be.
Sparse polynomials for the most part used in vanishing polynomials in our codebase. I suggest we write a fast path for sparse polynomial evaluation, when all terms are powers of 2. (This captures vanishing polynomials for unions of cosets, and vanishing polynomials for subspaces of binary fields)
Then for general sparse polynomial evaluation, I suggest we compare the current method against computing all of the squares, and then make the per-term work just computing the correct product of the squares. (As this removes any duplicate squarings computed)
Originally posted by @ValarDragon in #117 (comment)
The text was updated successfully, but these errors were encountered: