
Evaluation by Horner's Rule
 Given a polynomial of degree n,

 p(x) = a_{n}x^{n} + a_{n1}x^{n1} + ... + a_{1}x^{1} + a_{0}

 one might suspect that (n1)+(n2)+...+1 = n(n1)/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_{n}x + a_{n1})x + a_{n2})x + ... a_{1})x + a_{0}

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

 12345 = 1*10^{4} + 2*10^{3} + 3*10^{2} + 4*10^{1} + 5*10^{0}
 = (((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.

