Encyclopedia > Horner's rule

  Article Content

Horner's rule

When numerically computing values of polynomials, Horner's rule (or Horner's method, Horner's Schema) is one of the first basic computation rules one must learn. Assume you want to evaluate the value of a polynomial:

<math>p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots + a_nx^n</math>

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:

<math>p(x) = a_0 + ( \cdots (((a_nx + a_{n-1})x + a_{n-2})x + a_5)x \cdots + a_1)x</math>

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

Historical Notice

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.

See Also



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Quadratic formula

... equation <math>ax^2+bx+c=0</math> in terms of the coefficients a, b and c, which are assumed to be real (but see below for generalizations) with a being ...

 
 
 
This page was created in 37.9 ms