Horner scheme

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Privacy policy

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) = a0 + a1T + ... + anT n, the Horner scheme computes the number

p(x) = a0 + a1x + a2x2 + ... + an xn

as well as a polynomial q(T) = b0 + b1T + ... + bn-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 bi := an
  3. if i < 0, stop; the result p(x) is in b-1.
  4. set i := i - 1
  5. set bi := bi+1 * x + ai+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 ai are the digits) and can also be used if x is a matrix, in which case the gain is even larger.