In mathematics and computer science, polynomial evaluation refers to computation of the value of a polynomial when its indeterminates are substituted for some values. In other words, evaluating the polynomial P ( x 1 , x 2 ) = 2 x 1 x 2 + x 1 3 + 4 {\displaystyle P(x_{1},x_{2})=2x_{1}x_{2}+x_{1}^{3}+4} at x 1 = 2 , x 2 = 3 {\displaystyle x_{1}=2,x_{2}=3} consists of computing P ( 2 , 3 ) = 2 ⋅ 2 ⋅ 3 + 2 3 + 4 = 24. {\displaystyle P(2,3)=2\cdot 2\cdot 3+2^{3}+4=24.} See also Polynomial ring § Polynomial evaluation For evaluating the univariate polynomial a n x n + a n − 1 x n − 1 + ⋯ + a 0 , {\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0},} the most naive method would use n {\displaystyle n} multiplications to compute a n x n {\displaystyle a_{n}x^{n}} , use n − 1 {\displaystyle n-1} multiplications to compute a n − 1 x n − 1 {\displaystyle a_{n-1}x^{n-1}} and so on for a total of n ( n + 1 ) 2 {\displaystyle {\tfrac {n(n+1)}{2}}} multiplications and n {\displaystyle n} additions. Using better methods, such as Horner's rule, this can be reduced to n {\displaystyle n} multiplications and n {\displaystyle n} additions. If some preprocessing is allowed, even more savings are possible.
Background This problem arises frequently in practice. In computational geometry, polynomials are used to compute function approximations using Taylor polynomials. In cryptography and hash tables, polynomials are used to compute k-independent hashing. In the former case, polynomials are evaluated using floating-point arithmetic, which is not exact. Thus different schemes for the evaluation will, in general, give slightly different answers. In the latter case, the polynomials are usually evaluated in a finite field, in which case the answers are always exact.
General methods
Horner's rule
Horner's method evaluates a polynomial using repeated bracketing:
… excerpt ends here. Continue reading the full article.
