Home > Horner scheme

1 History

Even though it is named after William George Horner, who described the algorithm in 1819, it was already known to Isaac Newton in 1669 and even to the Chinese mathematician Ch'in Chiu-Shao around 1200s.

2 Basic idea

Assume we want to evaluate the polynomial in the monomial form

for given a₀,...,a_n. That is we want to know

for a given x. When using the monomial form of the polynomial we we need n additions and n²+n/2 multiplications for the calculation of p(x). Our aim is to decrease the number of multplications because they are slow and numerically instable compared to the additions. The Horner algorithm rearranges the polynomial into the recursive form

and then evalutes the polynomial recursivly using only n additions and n mulitplications. Additionally it is numerically more stable because we eliminated some multiplications. Alternatively it could be computed with n fused multiply-adds.

3 Horner algorithm

Given the polynomial

we rearrange it into

Then starting from the innermost parentheses and working outwards we define

If we put the b_n in the polynomial we see that

so b₀ is the is the value of the polynomial p at x.

4 Application

The Horner scheme is often used to convert between different positional numeral systemA numeral is a symbol or group of symbols that represents a number. Numerals differ from numbers just as words differ from the things they refer to. The symbols "11", "eleven" and "XI" are different numerals, all representing the same number. This articles (in which case x is the base of the number system, and the a_i are the digits) and can also be used if x is a matrix, in which case the gain is even larger.

The Horner scheme can also be viewed as a fast algorithm for dividing a polynomial by a linear polynomial (see Ruffini's ruleIn mathematics, Ruffini's rule allows the rapid division of any polynomial by a binomial of the form x − r''. It was described by Paolo Ruffini in 1809. Ruffini's rule is a special case of long division when the divisor is a linear factor. Ruffini's).

5 See also

• Clenshaw algorithmIn the mathematical subfield of numerical analysis the Clenshaw algorithm is a recursive method to evaluate polynomials in Chebyshev form. Polynomial in Chebyshev form A polynomial of degree N in Chebyshev form is a polynomial p ''x of the form : where T to evaluate polynomials in Chebyshev form
• De Casteljau's algorithmIn the mathematical subfield of numerical analysis the de Casteljau's algorithm named after its inventor Paul de Casteljau, is a recursive method to evaluate polynomials in Bernstein form or Bezier curves. Although the algorithm is slower for most archite to evalute polynomials in Bézier form