Horner scheme

Helping orphans the way you would do it

In mathematics and computing, 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:

set i := n - 1
set b_i := a_n
if i < 0, stop; the result p(x) is in b_-1.
set i := i - 1
set b_i := b_i+1 * x + a_i+1
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 numeral 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 the value of the contents of the outermost parentheses is b₀.