Polynomial evaluation

Polynomial evaluation is the computation of the value of a polynomial when its indeterminates are replaced by given values. For a univariate polynomial of degree n the naive method uses n(n+1)/2 multiplications and n additions, while Horner's rule reduces this to n multiplications and n additions, and preprocessing the coefficients can save still more. The problem arises often in practice: in computational geometry, polynomials give function approximations through Taylor polynomials, and in cryptography and hash tables they compute k-independent hashing. Evaluation in floating point is not exact, so different schemes give slightly different answers, whereas evaluation in a finite field is always exact. Other methods the article names are Estrin's scheme, which allows the computation to be parallelized, Motzkin's preprocessing, the Knuth-Eve and Rabin-Winograd algorithms, and fast multipoint evaluation using the fast Fourier transform.