### Polynomials

 LA home Computing Algorithms  glossary  Numerical   Num.Errors   Polynomials   Stirling   Mean&S.D.   Segmentation   Superposition   Integration   Matrices   Eigen v.   Polynomials

#### Evaluation by Horner's Rule

Given a polynomial of degree n,

p(x) = anxn + an-1xn-1 + ... + a1x1 + a0

one might suspect that (n-1)+(n-2)+...+1 = n(n-1)/2 multiplications would be needed to evaluate p(x) for a given x. However Horner's Rule shows that it can be rewritten so that only n multiplications are needed:

p(x) = (((anx + an-1)x + an-2)x + ... a1)x + a0

Incidentally, this is exactly the way that integer constants are evaluated from strings of characters (digits):

12345 = 1*104 + 2*103 + 3*102 + 4*101 + 5*100
= (((1*10 + 2)*10 + 3*10 + 4)*10 + 5

-- just think of the digit values as the coefficients and the ‘base’ of the number system as x.

Horner's rule also pops up for calculating the "rolling hash value" in Rabin's string searching algorithm.
-- 1999 L.A.
www:
 The C++ Cookbook mastering the language
 ↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated). Created with "vi (Linux)",  charset=iso-8859-1,   fetched Wednesday, 11-Dec-2019 03:29:22 EST. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.