You see that in order to carry out this evaluation for a given <math>x</math> and given coefficients <math>a_i</math>, you need to perform <math>2n+1</math> multiplications and <math>n</math> additions, given that you preserve the powers of <math>x</math> between the additions. (Else it will demand something like (n2+n)/2 multiplications!)
William George Horner[?] observed in 1819 (columbi egg[?]) that as additions are easier to perform than multiplications (especially if you want to compute this using a computer), if you rewrite the polynomial evaluation as follows:
then <math>p(x)</math> may be evaluated recursively using only <math>n</math> multiplications and <math>n</math> additions. This may be easily implemented in a computer program where a[] is a vector of the coefficients, with the most significant coefficient first, thusly (pseudo code):
procedure horner(a[],x) { integer n = length(a)-1 p = a[1] for i = 1 to n p = p*x+a(i+1) end return p end
Even though William George Horner[?] is credited with this rule, the same rule was invented by Isaac Newton in 1669 and actually the first person to describe it was the Chinese mathematician Ch'in Chiu-Shao[?] in the 1200s.
Search Encyclopedia
|
Featured Article
|