Why This Matters
A Show HN tool demonstrates that with one-time preprocessing of coefficients, a polynomial of degree n can be evaluated in about n/2 multiplications instead of Horner's n — roughly halving the multiply count. That matters wherever polynomial evaluation is hot code: math library approximations of exp/sin/cos, cryptography, hashing, and error-correcting codes. The web tool lets developers paste a polynomial, pick a field, and get the preprocessed form directly.
Key Takeaways
- Preprocessing coefficients cuts polynomial evaluation to ⌊n/2⌋+1 multiplications for monic polynomials, versus n with Horner's method.
- The savings apply to common workloads: function approximation, cryptography, hashing, and coding theory.
- The interactive tool does the coefficient transformation for you, given a polynomial and a choice of field.
Evaluating Polynomials Fast
You may have heard about Horner's method, which evaluates a polynomial of degree n in n multiplications (n−1 if it is monic). But did you know that with a bit of preprocessing of the coefficients, ⌊n/2⌋+1 multiplications suffice for any monic polynomial, one more for a general one? You can use this to approximate functions like exp, sin, cos, or to evaluate polynomials in cryptography, hashing, and coding theory. Simply type a polynomial below, pick your field, and we'll preprocess it for you.
GoKawiil