Horner scheme
In
mathematics and
computing, the
Horner scheme is an
algorithm for the efficient evaluation of
polynomial functions. Even though William George Horner is credited in the name, 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.
Assume we want to evaluate the value of a polynomial:
That is, we want carry out this evaluation for given
x and coefficients. Additions are in general easier to perform than multiplications. Horner observed in
1819 that
p(
x) may be evaluated recursively using only
n multiplications and
n additions.
Given a number x and a polynomial p(T) = a0 + a1T + ... + anT n, first rewrite p with x factored out:
- p(x) = a0 + a1x + a2x2 + ... + an-1 xn-1 + an xn
- = a0 + x(a1 + x(a2 + ... + x(an-1 + x(an)) ... ))
then evaluate this expression in the obvious way, starting from the innermost parentheses and working out. I.e.:
- b0=anx+an-1
- \b1=b0x+an-2
- b2=b1x+an-3
- ...
- bn-1=bn-2x+a0=p(x)
This is the method of choice for evaluating polynomials; it is faster and more numerically stable than the "normal" method, which involves computing the powers of
x and multiplying them with the coefficients. The Horner scheme is often used to convert between different positional
numeral systems (in which case
x is the base of the number system, and the
ai 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.