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) = c_{0} |
---|---|
Linear Function: | f(x) = c_{1} x + c_{0} |
Quadratic Function: |
f(x) = c_{2} x^{2} + c_{1} x + c_{0}
f(x) = ( c_{2} x + c_{1} ) x + c_{0} |
Cubic Function: |
f(x) = c_{3} x^{3} + c_{2} x^{2} + c_{1} x + c_{0}
f(x) = ( c_{3} x^{2} + c_{2} x + c_{1} ) x + c_{0} f(x) = ( ( c_{3} x + c_{2} ) x + c_{1} ) x + c_{0} |
Quartic Function: |
f(x) = c_{4} x^{4} + c_{3} x^{3} + c_{2} x^{2} + c_{1} x
+ c_{0}
f(x) = ( c_{4} x^{3} + c_{3} x^{2} + c_{2} x + c_{1} ) x + c_{0} f(x) = ( (c_{4} x^{2} + c_{3} x + c_{2} ) x + c_{1} ) x + c_{0} f(x) = ( ( (c_{4} x + c_{3} ) x + c_{2} ) x + c_{1} ) x + c_{0} |
etc. | |
In general, |
f(x) = c_{n} x^{n} + c_{n–1} x^{n–1} + c_{n–2}
x^{n–2} + . . . + c_{2} x^{2} + c_{1} x + c_{0}
f(x) = ( c_{n} x^{n–1} + c_{n–1} x^{n–2} + c_{n–2} x^{n–3} + . . . + c_{2} x + c_{1} ) x + c_{0} f(x) = ( ( c_{n} x^{n–2} + c_{n–1} x^{n–3} + c_{n–2} x^{n–4} + . . . + c_{2} ) x + c_{1} ) x + c_{0} f(x) = ( . . .( ( c_{n} x^{2} + c_{n–1} x + c_{n–2} ) x + . . . + c_{2} ) x + c_{1} ) x + c_{0} f(x) = ( ( . . .( ( c_{n} x + c_{n–1} ) x + c_{n–2} ) x + . . . + c_{2} ) x + c_{1} ) x + c_{0} |
EXAMPLE: |
f(x) = 2x^{5}– 3x^{4} + 5x^{3}– 8x^{2} + 12x – 17
f(x) = ( 2x^{4}– 3x^{3} + 5x^{2}– 8x + 12 ) x – 17 f(x) = ( (2x^{3}– 3x^{2} + 5x – 8 ) x + 12 ) x – 17 f(x) = ( ( ( 2x^{2}– 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.