Horner's Method
Ask a computer to evaluate p(x) = 2x^3 - 6x^2 + 2x - 1 at some number, and
the naive way is to do exactly what the notation says: work out x^3,
multiply by 2; work out x^2, multiply by
-6; and so on. It works — but it wastes effort, recomputing powers of
x from scratch again and again. Horner's method is a way
to evaluate any polynomial with the fewest possible multiplications, by re-writing it as a
nest of parentheses. It is one of those rare ideas that is simultaneously faster, shorter to code,
and more accurate — a clean win on every axis, which is why it hides inside almost every
numerical library you will ever touch.
The nesting trick
Take a general degree-n polynomial
p(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n,
and factor out an x from every term past the first, then again from
what remains, and again, peeling one layer at a time. You end up with a staircase of nested brackets:
p(x) = a_0 + x\bigl(a_1 + x\bigl(a_2 + x\bigl(\cdots + x\,a_n\bigr)\cdots\bigr)\bigr).
Read that from the inside out and it becomes an algorithm. Start with the top coefficient
a_n. Multiply by x, add the next coefficient
down, and repeat until you reach a_0:
-
The recurrence. Set b_n = a_n, then for
k = n-1 down to 0,
b_k = a_k + x\,b_{k+1}, \qquad\text{and}\qquad p(x) = b_0.
-
The cost. Exactly n multiplications and
n additions — one of each per step.
Watch it on our cubic p(x) = 2x^3 - 6x^2 + 2x - 1 at
x = 3. The coefficients top-to-bottom are
2, -6, 2, -1:
2 \;\xrightarrow{\times 3,\, -6}\; 0 \;\xrightarrow{\times 3,\, +2}\; 2 \;\xrightarrow{\times 3,\, -1}\; 5.
Three multiplications, three additions, answer p(3) = 5. Compare the
direct computation 2\cdot 27 - 6\cdot 9 + 2\cdot 3 - 1 = 54 - 54 + 6 - 1 = 5:
same answer, but the direct route needed to build x^2 and
x^3 along the way.
n multiplications, not \sim n^2/2
How much does the nesting actually save? Evaluate a_0 + a_1 x + \cdots + a_n x^n
the naive way, building each power x^k from scratch. The term
a_k x^k costs k multiplications
(k-1 to raise the power, one more for the coefficient), so the total is
1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} \sim \frac{n^2}{2}.
Horner needs only n. The gap is the difference between a straight line and
a parabola: for a degree-20 polynomial that is
20 multiplications versus 210 — better than a
tenfold saving, growing without bound as the degree climbs.
(You can be cleverer about the naive method by reusing the previous power —
x^k = x\cdot x^{k-1} — which brings it down to about
2n multiplications. Horner still wins, at exactly n,
and it does so while touching each coefficient only once, streaming through the array in a single
pass.)
See it run: naive versus Horner
Here are both methods side by side, each counting its own multiplications as it goes. They agree on
the value; they disagree, sharply, on the effort. Press Run:
// coeffs[i] is the coefficient of x^i, so [-1, 2, -6, 2] is -1 + 2x - 6x^2 + 2x^3.
function naive(coeffs: number[], x: number): { value: number; mults: number } {
let value = 0, mults = 0;
for (let i = 0; i < coeffs.length; i++) {
let power = 1;
for (let j = 0; j < i; j++) { power = power * x; mults++; } // build x^i from scratch
value = value + coeffs[i] * power;
mults++; // times the coefficient
}
return { value, mults };
}
function horner(coeffs: number[], x: number): { value: number; mults: number } {
let value = coeffs[coeffs.length - 1]; // start at the top coefficient a_n
let mults = 0;
for (let i = coeffs.length - 2; i >= 0; i--) {
value = value * x + coeffs[i]; // one multiply, one add per step
mults++;
}
return { value, mults };
}
const p = [-1, 2, -6, 2]; // -1 + 2x - 6x^2 + 2x^3
const a = naive(p, 3), b = horner(p, 3);
console.log(`naive: p(3) = ${a.value} using ${a.mults} multiplications`);
console.log(`horner: p(3) = ${b.value} using ${b.mults} multiplications`);
// The gap widens fast. A degree-20 polynomial (21 random coefficients):
const big = Array.from({ length: 21 }, () => Math.round(Math.random() * 10 - 5));
console.log(`\ndegree 20: naive ${naive(big, 1.1).mults} mults vs horner ${horner(big, 1.1).mults} mults`);
The cubic costs 6 multiplications naively but only
3 under Horner; the degree-20 case shows the
quadratic-versus-linear gulf in full.
The synthetic-division connection
The intermediate values b_k are not throwaways — they are the
coefficients you get from dividing p(x) by (x - c).
This is exactly the shortcut called synthetic division, a stripped-down
polynomial long division
for a linear divisor. Running Horner at x = c computes, in one sweep,
p(x) = (x - c)\,q(x) + r, \qquad r = p(c),
where the quotient q(x) has coefficients
b_n, b_{n-1}, \ldots, b_1 and the remainder is the final value
r = b_0 = p(c). That last equality is the
Remainder
Theorem falling out for free: the number Horner spits out is the remainder on
division by (x-c). So a single Horner pass both evaluates the
polynomial and divides it. Here it is, printing the quotient and remainder together:
// Divide p(x) = 2x^3 - 6x^2 + 2x - 1 by (x - c) via one Horner sweep.
// coeffs are TOP-DOWN here: [a_n, ..., a_0].
function syntheticDivide(coeffs: number[], c: number): { quotient: number[]; remainder: number } {
const out: number[] = [coeffs[0]];
for (let i = 1; i < coeffs.length; i++) {
out.push(coeffs[i] + c * out[i - 1]); // the Horner recurrence b_k = a_k + c * b_{k+1}
}
const remainder = out.pop() as number; // the last b is the remainder = p(c)
return { quotient: out, remainder };
}
const { quotient, remainder } = syntheticDivide([2, -6, 2, -1], 3);
console.log(`quotient q(x) coefficients (top-down): ${quotient.join(", ")}`);
console.log(`remainder r = p(3) : ${remainder}`);
// So 2x^3 - 6x^2 + 2x - 1 = (x - 3)(2x^2 + 0x + 2) + 5.
Fewer operations means fewer chances to lose digits to
floating-point
rounding, but the deeper reason is structural. Building large powers
x^k and multiplying by large coefficients produces big intermediate
numbers that must then cancel — a recipe for catastrophic loss of significance. Horner's
interleaved "multiply, add, multiply, add" keeps the running value close to the final magnitude at
every step, so there are no wildly large partial results to cancel away. In the language of
numerical analysis it is backward stable: the computed value is the exact value of
a polynomial whose coefficients differ from yours only by a whisker of rounding. Faster and
steadier.
A worked example, by hand
Evaluate p(x) = x^4 - 3x^3 + 0\cdot x^2 + 5x - 2 at
x = 2. Lay the coefficients out top-down —
1, -3, 0, 5, -2 — and roll Horner:
\begin{aligned}
b_4 &= 1,\\
b_3 &= -3 + 2(1) = -1,\\
b_2 &= 0 + 2(-1) = -2,\\
b_1 &= 5 + 2(-2) = 1,\\
b_0 &= -2 + 2(1) = 0.
\end{aligned}
So p(2) = 0 — meaning x = 2 is a root, and the
quotient x^3 - x^2 - 2x + 1 reads straight off the
b_k column. Four multiplications, four additions, a root and a
factorisation, all from one tidy sweep.
Horner runs from the highest coefficient down to the constant — get the direction
wrong and you evaluate a different polynomial entirely. Two habits keep you safe. First, always
include zero coefficients for missing powers: in
x^4 - 3x^3 + 5x - 2 the x^2 term is absent, so
its 0 must still take its place in the sequence
1, -3, \mathbf{0}, 5, -2 — skip it and every later step is off. Second,
Horner in its basic form divides only by a linear factor
(x - c); dividing by a quadratic or higher needs full
long division,
not this single-column shortcut.