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)
      return p

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
Canadian Music Hall of Fame

... Inductees 1978 Guy Lombardo 1978 Oscar Peterson 1979 Hank Snow 1980 Paul Anka 1981 Joni Mitchell 1982 Neil Young 1983 Glenn Gould 1986 Gordon Lightfoot ...

This page was created in 34 ms