You may believe that evaluating a polynomial in $x$ at a specific value of $x$ should be quite easy.

Suppose you have a table, the entries of which are labelled $0$ through $n$ where $n$ is the degree of a polynomial, and the entry indexed by $k$ is the coefficient of $x^k$.

For example, suppose we had the table

0	1	2
-0.807	-1.32	1.99

This table represents the polynomial $1.99x^2 - 1.32x - 0.807$.

Describe an algorithm that evaluates this polynomial at the value $x = 1.05$.

Now, most secondary school students would have you calculate $x^2 = 1.1025$, and so the result is $1.99 \cdot 1.1025 - 1.32 \cdot 1.05 - 0.807 = 2.193975 - 1.3860 - 0.807 = 0.000975$.

Efficiency and the slide rule

The calculation described above requires three multiplications and an addition of three numbers. As you may recall, explicitly calculating the product of two real numbers is time consuming, and in the 1600s, the invention of the slide rule simplified the multiplication of reals significantly, but at the cost of only allowing the computer to achieve three (although later four and five) digits of precision.

Thus, in calculating $1.05^2$, a human computer using a slide rule would likely get $1.05^2 \approx 1.10$, and then in calculating $1.99 x^2 \approx 2.19$. Similarly, $-1.32 x \approx -1.39$. Addition can usually be done with all the digits available, so $2.19 - 1.39 - 0.807 = -0.007$. You will note that not only is this number not even close to the correct answer of $0.000975$, it doesn't even have the correct sign.

Thus, an alternative algorithm of evaluating polynomials was developed. Today, this algorithm is called Horner's rule after William George Horner who described it in the early 1800s; however, the algorithm had been described in the early 1100s by the Persian mathematician Sharaf al-Din al-Tusi, and described independently a century later by the Chinese mathematician Qin Jiushao.

This algorithm may be described as follows:

• Let the result be the coefficient of the largest term of the polynomial.
• While there are smaller coefficients (some of which may be zero),
• multiply the result by $x$ and add to the result the next smaller coefficient.

This is equivalent to rewriting the polynomial as

$1.99x^2 - 1.32x - 0.807 = (1.99x - 1.32)x - 0.807$.

You will notice that this only requires two multiplications, not three. Now,

• $1.99 \cdot 1.05 \approx 2.09$,
• $2.09 - 1.32 = 0.77$,
• $0.77 \cdot 1.05 \approx 0.808$ (rounding to the closest even digit),
• $0.808 - 0.807 = 0.001$.

Thus, this polynomial evaluated using Horner's rule results in the value $0.001$, which is remarkably close to the correct answer of $0.000975$, and a much better approximation than that found using the algorithm you would have used in secondary school.

Horner's rule in general

Using Horner's rule to evaluate a polynomial of degree $n$ requires $n$ multiplications and $n$ additions. The minimum number of multiplications required for the best implementation of the algorithm taught in secondary school would require $2n - 1$ multiplications and $n$ additions.