Horner's rule

<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 (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:

<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

• Numerical analysis
• Polynomial