HORNER'S METHOD

Please note that the material on this website is not intended to be exhaustive.
This is intended as a summary and supplementary material to the required textbook.

One concern a programmer should have is the elimination of the recalculation of values that have already been calculated.

Horner's Method is a way of expressing a polynomial f(x) which eliminates all exponentiations.  By eliminating exponentiations, we eliminate re–doing some calculations.

Constant Function: f(x) = c0
 
Linear Function: f(x) = c1 x + c0
 
Quadratic Function: f(x) = c2 x2 + c1 x + c0
f(x) = ( c2 x + c1 ) x + c0
 
Cubic Function: f(x) = c3 x3 + c2 x2 + c1 x + c0
f(x) = ( c3 x2 + c2 x + c1 ) x + c0
f(x) = ( ( c3 x + c2 ) x + c1 ) x + c0
 
Quartic Function: f(x) = c4 x4 + c3 x3 + c2 x2 + c1 x + c0
f(x) = ( c4 x3 + c3 x2 + c2 x + c1 ) x + c0
f(x) = ( (c4 x2 + c3 x + c2 ) x + c1 ) x + c0
f(x) = ( ( (c4 x + c3 ) x + c2 ) x + c1 ) x + c0
 
etc.
 
In general, f(x) = cn xn + cn–1 xn–1 + cn–2 xn–2 + . . . + c2 x2 + c1 x + c0
f(x) = ( cn xn–1 + cn–1 xn–2 + cn–2 xn–3 + . . . + c2 x + c1 ) x + c0
f(x) = ( ( cn xn–2 + cn–1 xn–3 + cn–2 xn–4 + . . . + c2 ) x + c1 ) x + c0
f(x) = ( . . .( ( cn x2 + cn–1 x + cn–2 ) x + . . . + c2 ) x + c1 ) x + c0
f(x) = ( ( . . .( ( cn x + cn–1 ) x + cn–2 ) x + . . . + c2 ) x + c1 ) x + c0
 
EXAMPLE: f(x) = 2x5– 3x4 + 5x3– 8x2 + 12x – 17
f(x) = ( 2x4– 3x3 + 5x2– 8x + 12 ) x – 17
f(x) = ( (2x3– 3x2 + 5x – 8 ) x + 12 ) x – 17
f(x) = ( ( ( 2x2– 3x + 5 ) x – 8 ) x + 12 ) x – 17
f(x) = ( ( ( ( 2x – 3 ) x + 5 ) x – 8 ) x + 12 ) x – 17

PROBLEM:   Develop an algorithm, expressed as a NSD, for evaluating any given polynomial f(x) using Horner's Method.


© 1994-07-23 cad rcm cpsm; last update 2010-06-30 20:06