Evaluation by Horner's Rule
Given a polynomial of degree n,
p(x) = anxn + an-1xn-1 + ... + a1x1 + a0
one might suspect that n+(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.
|