Horner scheme

The Horner scheme is an algorithm for the efficient evaluation of polynomial functions, and for dividing polynomials by linear polynomials.

Given a number x and a polynomial p(T) = a₀ + a₁T + ... + a_nT ⁿ, the Horner scheme computes the number

p(x) = a₀ + a₁x + a₂x² + ... + a_n xⁿ

as well as a polynomial q(T) = b₀ + b₁T + ... + b_n-1T ^n-1 such that

p(T) = (T - x) · q(T) + p(x).

The algorithm works as follows:

1. set i := n - 1
2. set b_i := a_n
3. if i < 0, stop; the result p(x) is in b_-1.
4. set i := i - 1
5. set b_i := b_i+1 * x + a_i+1
6. Go to step 3.

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 number systems (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.

There is another way to describe the Horner scheme. Given the a_i coefficients and the number x, first rewrite p with x factored out:

p(x) = a₀ + a₁x + a₂x² + ... + a_n-1 x^n-1 + a_n xⁿ

= a₀ + x(a₁ + x(a₂ + ... + x(a_n-1 + x(a_n)) ... ))

then evaluate this expression in the obvious way, starting from the innermost parentheses and working out. The value of the expression in the innermost parentheses is b_n-1. The value of the expression in the second-to-innermost parentheses is b_n-2, and so on until until the value of the contents of the outermost parentheses is b₀.