◄ WORLD V · SONNY 5DART 167 · a helldive at the net

HORNER’S METHOD nest the polynomial; one multiply and add per term

Evaluate 2x³ − 6x² + 2x − 1 the obvious way and you recompute powers of x over and over. Horner’s method rewrites it as a nest — ((2x − 6)x + 2)x − 1 — so a degree-n polynomial costs exactly n multiplies and n adds, the fewest possible, and it is numerically more stable too. The oldest trick in numerical computing, and still the one every library uses.

THE TECHNIQUE n mults, n adds; provably minimal

Fold the coefficients from the highest down: start with the leading coefficient, then repeatedly multiply by x, add the next coefficient. Watch the nest evaluate and the multiply count fall to the degree: live demo







  
HISTORY & CREDIT Qin 1247; Newton before Horner 1819

  
“Horner invented Horner’s method.” — no. Qin Jiushao gave it in China in 1247, and Newton used the same nesting around 1669, both well before Horner’s 1819 paper. It is a textbook case of Stigler’s law — the name commemorates the popular expositor, not the inventor. cited

  
1247 · Qin Jiushao — the nesting scheme in “Mathematical Treatise in Nine Sections”, five centuries before Horner.
~1669 · Isaac Newton — uses the same nested evaluation in his root-finding work.
1804 / 1819 · Paolo Ruffini (1804) and William George Horner (1819) — rediscover and publish it; Horner’s exposition made it famous, so his name stuck.

  
That degree-n evaluation needs at least n multiplications was proved by Pan (1966), and at least n additions by Ostrowski (1954) — so Horner’s method is not just economical, it is optimal in both. Qin Jiushao, 1247






  
RECOMMEND FOR I-13 the nest, computed

  
The nested evaluation of 2x³−6x²+2x−1 at x=3 runs on the canonical compiler:

  
$ i13 run horner.i13   # coeffs [2,-6,2,-1]; acc = acc*x + c[i]
p3 = 5   -- ((2*3 - 6)*3 + 2)*3 - 1 = 5, in 3 multiplies (= the degree)

  
Recommend: Horner’s method is LIT and belongs in the I-13 stdlib — verified p(3)=5 for 2x³−6x²+2x−1 by the fold acc = acc*x + c[i] over a coefficient array (native f64 + array + recursion). It is the minimal-cost, most-stable way to evaluate any polynomial — every Taylor series in the I-13 transcendental library (dart 033, the exp/sin/cos sums) should be summed this way, not by recomputing powers. Three multiplies for a cubic, n for degree n, provably fewest.