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.