Horner's Method

Evaluating a polynomial looks too simple to need an algorithm, but the obvious way wastes work. Synthetic division already contains a better way: the remainder of dividing $p(x)$ by $x - c$ is $p(c)$, and the steps of synthetic division are exactly Horner's method.

Factor $x$ out again and again: $$a_3x^{3} + a_2x^{2} + a_1x + a_0 = ((a_3x + a_2)x + a_1)x + a_0.$$ Start with $b = a_n$, then for $k = n - 1$ down to $0$ replace $b$ by $bx + a_k$. The last $b$ is $p(x)$.

Key idea

Horner's method evaluates a degree-$n$ polynomial with only $n$ multiplications and $n$ additions, starting from the leading coefficient and writing a $0$ for every missing power.

Why it works

Term by term, $a_kx^{k}$ costs $k$ multiplications if each power is built from scratch: $1 + 2 + \cdots + n = \frac{n(n + 1)}{2}$ in all. Even reusing powers costs about $2n$. The nested form does one multiply and one add per coefficient. Fewer operations also means fewer roundings, and the intermediate values $b$ have a meaning of their own: they are the coefficients of the quotient $q(x)$ in $p(x) = (x - c)q(x) + p(c)$.

Worked example: Evaluating a cubic

Evaluate $p(x) = 2x^{3} - 6x^{2} + 2x - 1$ at $x = 3$.

Coefficients from the top: $2, -6, 2, -1$. Start with $b = 2$.
$b = 2 \cdot 3 - 6 = 0$.
$b = 0 \cdot 3 + 2 = 2$.
$b = 2 \cdot 3 - 1 = 5$. So $p(3) = 5$ (check: $54 - 54 + 6 - 1 = 5$).

Answer: $5$

Worked example: A missing power

Evaluate $p(x) = x^{4} - 3x^{2} + x - 2$ at $x = -2$.

There is no $x^{3}$ term, so the coefficients are $1, 0, -3, 1, -2$.
$b$: $1 \to 1(-2) + 0 = -2 \to (-2)(-2) - 3 = 1 \to 1(-2) + 1 = -1 \to (-1)(-2) - 2 = 0$.
$p(-2) = 0$, so $x = -2$ is a root. Leaving out the $0$ would have evaluated a different polynomial.

Answer: $0$

The first example as a synthetic-division row: 2, 0, 2 are the coefficients of the quotient, and 5 is the remainder.
coefficient	$2$	$-6$	$2$	$-1$
$b$ (at $x = 3$)	$2$	$0$	$2$	$5$

The second example as a table: bring down the leading coefficient, then multiply by x and add the next coefficient, column by column.

Worked example: The derivative for free

Use the quotient from the first example to find $p'(3)$.

$p(x) = (x - 3)q(x) + p(3)$ with $q(x) = 2x^{2} + 0x + 2$.
Differentiate: $p'(x) = q(x) + (x - 3)q'(x)$, so $p'(3) = q(3)$.
A second Horner pass on $2, 0, 2$: $b = 2 \to 2 \cdot 3 + 0 = 6 \to 6 \cdot 3 + 2 = 20$. Check: $p'(x) = 6x^{2} - 12x + 2$ gives $54 - 36 + 2 = 20$.

Answer: $p'(3) = 20$

In code the whole method is two lines: set b = a[n], then for k = n - 1 down to 0 set b = b*x + a[k]. Each pass through the loop does one rounding in the multiply and one in the add, so the computed value is close to the exact value of a polynomial whose coefficients have been changed only slightly: Horner's method is backward stable.

Common mistake

Starting the nesting from the constant term, or skipping a missing power instead of writing a $0$ for it. Both evaluate the wrong polynomial. Check: the number of steps must equal the degree, and a quick direct evaluation at $x = 1$ (the sum of the coefficients) should match.

Horner's method is the standard way to evaluate polynomials in software; it is also the inner loop of Newton's method for polynomials, where $p(c)$ and $p'(c)$ come from two passes.

Sources and further reading

Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation (University of Delaware, free online edition): chapter "Introduction", section "Algorithms" (Horner's rule)

Autar Kaw, Holistic Numerical Methods (University of South Florida): Nonlinear Equations, "Newton–Raphson Method" (evaluating polynomials by nesting)

Horner's Method

Practice

Builds on

Leads to

Sources and further reading