Introduction

Suppose you need the value of p(x)=anxn+an−1xn−1+⋯+a1x+a0p(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0 at some number xx. The textbook way is to compute each power of xx separately and add up the terms — but computing xnx^n from scratch, then xn−1x^{n-1}, and so on, recomputes the same multiplications over and over.

Horner's method rewrites the polynomial as a chain of nested parentheses:

p(x)=(…((anx+an−1)x+an−2)x+⋯+a1)x+a0p(x) = (\dots((a_n x + a_{n-1})x + a_{n-2})x + \dots + a_1)x + a_0

Read it from the inside out: multiply the leading coefficient by xx, add the next coefficient, multiply by xx again, add the next one, and keep going. No power of xx is ever computed on its own — every multiplication does double duty, carrying forward all the work done so far.

The result is exactly nn multiplications and nn additions for a degree-nn polynomial, done in one pass with a single running value. It looks almost too simple to have a name, and yet it is the provably optimal way to do this — you cannot evaluate a general polynomial with fewer arithmetic operations.

Try It

Below is a fixed polynomial and a value of xx. Press Evaluate to run both methods side by side: the naive approach that computes each power of xx from scratch, and Horner's nested sweep.

<p class="hint">This fixed degree-5 polynomial gets evaluated two ways at the same x: the naive method recomputes each power of x from scratch, while Horner's method nests the multiplications so no power is ever computed on its own.</p>
<div class="poly" id="poly"></div>
<div class="row">
  <label for="xval">x =</label>
  <input id="xval" type="number" value="3" step="1" />
  <button id="run" type="button">Evaluate</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="cols">
  <div class="col">
    <h4>Naive (powers from scratch)</h4>
    <div class="log" id="naiveLog"></div>
    <div class="tally" id="naiveTally"></div>
  </div>
  <div class="col">
    <h4>Horner (nested)</h4>
    <div class="log" id="hornerLog"></div>
    <div class="tally" id="hornerTally"></div>
  </div>
</div>
<div class="status" id="status">Pick a value of x and press Evaluate.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.poly { font: 700 16px ui-monospace, monospace; background: #eef2f6; border: 1px solid #d3dce4;
        border-radius: 8px; padding: .5rem .7rem; margin-bottom: .6rem; color: #1d3557; }
.row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
label { font: 600 13px system-ui, sans-serif; color: #444; }
input[type="number"] { width: 4.5rem; font: 600 14px ui-monospace, monospace; padding: .35rem .5rem;
         border: 1px solid #adb1b8; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.cols { display: grid; grid-template-columns: 1fr 1fr; gap: .7rem; }
.col h4 { margin: 0 0 .3rem; font-size: .85rem; color: #1d3557; }
.log { font: 12px ui-monospace, monospace; background: #f7f9fb; border: 1px solid #e1e6ea;
       border-radius: 6px; padding: .4rem .5rem; min-height: 90px; max-height: 140px; overflow-y: auto;
       white-space: pre-wrap; line-height: 1.4; }
.tally { font: 700 13px system-ui, sans-serif; margin-top: .35rem; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
@media (max-width: 480px) { .cols { grid-template-columns: 1fr; } }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Fixed coefficients, highest degree first: 2x^5 - 3x^4 + 0x^3 + 5x^2 - 1x + 4.
const COEFFS = [2, -3, 0, 5, -1, 4]; // 2x^5 - 3x^4 + 0x^3 + 5x^2 - 1x + 4
const N = COEFFS.length - 1; // degree

function renderPoly(){
  document.getElementById('poly').textContent =
    'p(x) = 2x^5 - 3x^4 + 0x^3 + 5x^2 - 1x + 4';
}

// Naive evaluation: for each term, rebuild x^power by repeated multiplication, then scale by its coefficient.
function naiveEval(x){
  let total = 0, mults = 0, adds = 0;
  const log = [];
  for (let j = 0; j <= N; j++){
    const power = N - j;
    let val = 1;
    for (let k = 0; k < power; k++) { val *= x; mults++; }
    const term = COEFFS[j] * val;
    if (power > 0) mults++; // one multiplication to scale the power by its coefficient
    total += term;
    adds++;
    log.push(fmt('coeff %coeff% * x^%power% = %term%', { coeff: COEFFS[j], power: power, term: term }));
  }
  return { total, mults, adds, log };
}

// Horner's method: start from the leading coefficient and repeatedly do result = result * x + next coefficient.
function hornerEval(x){
  let result = COEFFS[0];
  let mults = 0, adds = 0;
  const log = [fmt('start: result = %c0%', { c0: COEFFS[0] })];
  for (let i = 1; i < COEFFS.length; i++){
    const before = result;
    result = result * x + COEFFS[i];
    mults++; adds++;
    log.push(fmt('result = %before% * %x% + %coeff% = %after%', { before: before, x: x, coeff: COEFFS[i], after: result }));
  }
  return { result, mults, adds, log };
}

function setStatus(t, cls){
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

function run(){
  const x = Number(document.getElementById('xval').value) || 0;
  const naive = naiveEval(x);
  const horner = hornerEval(x);

  document.getElementById('naiveLog').textContent = naive.log.join('\n');
  document.getElementById('hornerLog').textContent = horner.log.join('\n');
  document.getElementById('naiveTally').textContent =
    fmt('%mults% multiplications, %adds% additions', { mults: naive.mults, adds: naive.adds });
  document.getElementById('hornerTally').textContent =
    fmt('%mults% multiplications, %adds% additions', { mults: horner.mults, adds: horner.adds });

  // Sanity check — both methods must land on the exact same value.
  if (naive.total === horner.result){
    setStatus(fmt('Both methods agree: p(x) = %value%. Horner used %saved% fewer multiplications.', { value: horner.result, saved: naive.mults - horner.mults }), 'ok');
    console.log('Match:', naive.total, horner.result);
  } else {
    setStatus('Something is wrong — the two results should always match.', '');
    console.log('Mismatch:', naive.total, horner.result);
  }
}

document.getElementById('run').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', () => {
  document.getElementById('xval').value = 3;
  document.getElementById('naiveLog').textContent = '';
  document.getElementById('hornerLog').textContent = '';
  document.getElementById('naiveTally').textContent = '';
  document.getElementById('hornerTally').textContent = '';
  setStatus('Pick a value of x and press Evaluate.', '');
});

renderPoly();
Result
Console

Watch the operation counters, not just the final number — both methods land on the same answer (evaluation is one of the easiest correctness checks in computer science), but Horner's sweep gets there using far fewer multiplications. Bump the degree up and the gap only grows.

The Real Complexity

How good is Horner's method, really? Not just "fast" — optimal.

  • Naive evaluation computes x2,x3,…,xnx^2, x^3, \dots, x^n and multiplies each by its coefficient: that alone is O(n2)O(n^2) multiplications if each power is computed from scratch, or O(n)O(n) multiplications if you cache the running power — but even the cached version still needs 2n−12n-1 multiplications (one to advance the power, one to scale by the coefficient) plus nn additions.
  • Horner's method needs only nn multiplications and nn additions — a full pass in O(n)O(n) time using O(1)O(1) extra memory beyond the running total.
  • It's optimal. In 1954, Alexander Ostrowski proved that no algorithm built only from ++, −-, and ×\times can evaluate a general degree-nn polynomial with fewer than nn multiplications, confirming that Horner's centuries-old trick already hits the floor. (Special polynomials with extra structure, like xn−1x^n - 1, can sometimes be evaluated with fewer multiplications, but a generic polynomial with independent coefficients cannot.)
  • Numerically it also behaves better: because it never separately forms huge intermediate powers like x20x^{20}, Horner's method tends to accumulate less floating-point rounding error than naive evaluation.

So this isn't merely "a clever shortcut" the way many algorithmic tricks are — it's a rare case where an ancient piece of arithmetic bookkeeping turns out to already be the best possible answer, matching a hard lower bound on algorithmic complexity.

Where It Matters

"Evaluate a polynomial" sounds academic, but it is one of the most repeated operations in computing:

  • Scientific and numerical computing: Taylor and Chebyshev series approximations of sin⁡\sin, cos⁡\cos, exp⁡\exp and log⁡\log are polynomials in disguise, and math libraries evaluate them with Horner's nested form for speed and numerical stability.
  • Root-finding: methods like Newton's method repeatedly evaluate a polynomial and its derivative; Horner's scheme (extended to also produce the derivative in the same pass) makes each iteration cheap.
  • Cryptography and hashing: many string hash functions and CRC checksums are literally "evaluate a polynomial at a fixed base," computed with a Horner-style running multiply-and-add over the input bytes.
  • Computer graphics: Bézier curves and splines are polynomials evaluated once per pixel or frame, so shaving multiplications matters at scale.

Learn Horner's method and you've learned the standard inner loop of numerical software — the same nested multiply-and-add pattern that shows up anywhere a polynomial needs a number plugged into it, fast and accurately.

Conclusion

Horner's method is deceptively small: just nest the multiplications instead of computing powers separately. But that one regrouping takes a polynomial evaluation down to nn multiplications and nn additions — and Ostrowski's 1954 proof shows nothing can do fewer for the general case.

It's a reminder that not every performance win needs a fancy data structure or a clever trick discovered last year. Sometimes the oldest piece of algebra in the book, done in the right order, is already the mathematically best you can do — a small, concrete instance of the P vs NP universe's gentler cousin: proving a lower bound and then meeting it exactly.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/horner-method/Content licensed under CC BY-NC 4.0.