Fast Polynomial Evaluation - Compute polynomials twice as fast
Fast Polynomial Evaluation is a web tool that compiles evaluation chains for polynomials, reducing the number of multiplications needed from n to about n/2+1. By preprocessing coefficients with rational arithmetic, it achieves exact results and outperforms classic methods like Horner's. You can input any polynomial, choose a field (rationals, reals, complex, or finite fields), and get optimized C code or mathematical expressions. This is useful for approximating functions like exp, sin, and cos, or for applications in cryptography, hashing, and coding theory. The tool is backed by a new paper and open-source code on GitHub.
With a bit of preprocessing of the coefficients, ⌊n/2⌋+1 multiplications suffice for any monic polynomial—one more for a general one—doubling the speed of polynomial evaluation.
- huhtenberg
* "monic" = the leading coefficient is 1
- emil-lp
I read your arxiv paper yesterday (or was it the day before).
Do you think this can be used to speed up the algebraic method for k-path?
If so, you should enter next years PACE challenge.
- pvillano
This is super cool. I learned a lot playing with the demo. I only knew Horner and Estrin, but I think I've gotten a grasp on most of them.
One small change I'd recommend is for the graph visualization, have a separate source node for each x, x^2, x^4 used. A single x source clutters the graph and hides the structure.
- IsTom
Pretty cool, especially in finite fields. Though coefficients seem to blow up pretty quick in Q?
- throwaway81523
If you're going to preprocess the polynomial, maybe you want to evaluate it at many different points. But then why not use the FFT?