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