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:

You see that in order to carry out this evaluation for a given and given coefficients , you need to perform multiplications and additions, given that you preserve the powers of between the additions. (Else it will demand something like (n²+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 may be evaluated recursively using only multiplications and 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.

Horner's rule

Historical Notice

See Also