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.

More from this day

2026-09-10