1 Answers
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 = 2 x 1 x 2 + x 1 3 + 4 {\displaystyle P=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 ⋅ 2 ⋅ 3 + 2 3 + 4 = 24. {\displaystyle P=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 n , {\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{n},} 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 2 {\displaystyle {\tfrac {n}{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.