ENCYCLOPEDIA 4U .com

# Encyclopedia Home Page

 Web Encyclopedia4u.com

# 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) = 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 numeral 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.

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

p(x) = a0 + a1x + a2x2 + ... + an-1 xn-1 + an xn
= a0 + x(a1 + x(a2 + ... + x(an-1 + x(an)) ... ))
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 bn-1. The value of the expression in the second-to-innermost parentheses is bn-2, and so on until the value of the contents of the outermost parentheses is b0.

Content on this web site is provided for informational purposes only. We accept no responsibility for any loss, injury or inconvenience sustained by any person resulting from information published on this site. We encourage you to verify any critical information with the relevant authorities.

Copyright © 2005 Par Web Solutions All Rights reserved.
| Privacy

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Horner scheme".