Horner scheme

The Horner scheme is an algorithm for the efficient evaluation of polynomial functions. Given a number x and numbers a₀, a₁, ... , a_n, the Horner scheme computes the expression

a₀ + a₁x + a₂x² + ... + a_n xⁿ

as follows:

1. set r := a_n
2. set i := n-1
3. if i < 0, stop; the result is in the variable r.
4. set r := r * x + a_i
5. set i := 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.