Horner's Method

Suppose you need the value of $p(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$ at some number $x$. The textbook way is to compute each power of $x$ separately and add up the terms — but computing $x^n$ from scratch, then $x^{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) = (\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 $x$, add the next coefficient, multiply by $x$ again, add the next one, and keep going. No power of $x$ is ever computed on its own — every multiplication does double duty, carrying forward all the work done so far.

The result is exactly $n$ multiplications and $n$ additions for a degree-$n$ 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.

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

<p class="hint">{{hint_para}}</p>
<div class="poly" id="poly"></div>
<div class="row">
  <label for="xval">{{x_label}}</label>
  <input id="xval" type="number" value="3" step="1" />
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="cols">
  <div class="col">
    <h4>{{naive_title}}</h4>
    <div class="log" id="naiveLog"></div>
    <div class="tally" id="naiveTally"></div>
  </div>
  <div class="col">
    <h4>{{horner_title}}</h4>
    <div class="log" id="hornerLog"></div>
    <div class="tally" id="hornerTally"></div>
  </div>
</div>
<div class="status" id="status">{{ready_hint}}</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; } }

// Code not found

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.

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

• Naive evaluation computes $x^2, x^3, \dots, x^n$ and multiplies each by its coefficient: that alone is $O(n^2)$ multiplications if each power is computed from scratch, or $O(n)$ multiplications if you cache the running power — but even the cached version still needs $2n-1$ multiplications (one to advance the power, one to scale by the coefficient) plus $n$ additions.
• Horner's method needs only $n$ multiplications and $n$ additions — a full pass in $O(n)$ time using $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-$n$ polynomial with fewer than $n$ multiplications, confirming that Horner's centuries-old trick already hits the floor. (Special polynomials with extra structure, like $x^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 $x^{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.

"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$, $\cos$, $\exp$ and $\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.

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 $n$ multiplications and $n$ 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.