The
Horner scheme is an
algorithm for the efficient evaluation of
polynomial functions. Given a
number x and numbers
a0,
a1, ... ,
an, the Horner scheme computes the expression
- a0 + a1x + a2x2 + ... + an xn
as follows:
- set r := an
- set i := n-1
- if i < 0, stop; the result is in the variable r.
- set r := r * x + ai
- set i := 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.