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.