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:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Saturday, 17-Aug-2019 21:50:40 EDT.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.