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 n+(n1)+(n2)+...+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_{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.
