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.