The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition

4.6.4. Evaluation of Polynomials

Now that we know efficient ways to evaluate the special polynomial xⁿ, let us consider the general problem of computing an nth degree polynomial

$\begin{array}{cc}\begin{array}{cc}u\left(x\right)=u_n{x}^n+u_{n-1}{x}^{n-1}+\cdot \cdot \cdot +u_{1}x+u_0,& u_n\ne 0,\end{array}& \left(1\right)\end{array}$

for given values of x. This problem arises frequently in practice.

In the following discussion we shall concentrate on minimizing the number of operations required to evaluate polynomials by computer, blithely assuming that all arithmetic operations are exact. Polynomials are most commonly evaluated using floating point arithmetic, which is not exact, and different schemes for the evaluation will, in general, give different answers. A numerical analysis of the accuracy achieved depends on the coefficients of the particular polynomial ...