Evaluation by Horner's Rule

Given a polynomial of degree n,

 

p(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₁x¹ + a₀

 

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) = (((a_nx + a_n-1)x + a_n-2)x + ... a₁)x + a₀

 

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

 

12345 = 1*10⁴ + 2*10³ + 3*10² + 4*10¹ + 5*10⁰

= (((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.