Polynomial evaluation

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 ${\displaystyle P(x_{1},x_{2})=2x_{1}x_{2}+x_{1}^{3}+4}$ at ${\displaystyle x_{1}=2,x_{2}=3}$ consists of computing ${\displaystyle P(2,3)=2\cdot 2\cdot 3+2^{3}+4=24.}$ See also Polynomial ring § Polynomial evaluation

For evaluating the univariate polynomial ${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{0},}$ the most naive method would use ${\displaystyle n}$ multiplications to compute ${\displaystyle a_{n}x^{n}}$, use ${\displaystyle n-1}$ multiplications to compute ${\displaystyle a_{n-1}x^{n-1}}$ and so on for a total of ${\displaystyle {\tfrac {n(n+1)}{2}}}$ multiplications and ${\displaystyle n}$ additions. Using better methods, such as Horner's rule, this can be reduced to ${\displaystyle n}$ multiplications and ${\displaystyle n}$ additions. If some preprocessing is allowed, even more savings are possible.