History of Horner scheme

	Revision 4 . . December 10, 2001 6:39 am by AxelBoldt [also for long division]
	Revision 3 . . December 10, 2001 1:37 am by AxelBoldt [Also for matrices and number systems]
	Revision 2 . . December 10, 2001 1:34 am by AxelBoldt [Also for matrices]
	Revision 1 . . December 10, 2001 1:10 am by AxelBoldt [new]

---

Difference (from prior major revision) (no other diffs)

Changed: 1,7c1,11

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

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: # set i := n - 1 # set bi := an # if i < 0, stop; the result p(x) is in b-1.

Added: 8a13

# set bi := bi+1 * x + ai+1