 music |
 | OSdata.com |
Horner’s Method
summary
This subchapter looks at using Horner’s Method to reduce the computational overhead for evaluating a polynomial function.
free computer programming text book projecttable of contents
|
music |
| OSdata.com |
This subchapter looks at using Horner’s Method to reduce the computational overhead for evaluating a polynomial function.
free computer programming text book projecttable of contents
|
This subchapter looks at using Horner’s Method to reduce the computational overhead for evaluating a polynomial function.
Consider the polynomail function:
ƒ(x) = 8x5 + 5x4 - 3x3 + 9x2 + 2x -7
Assuming that the exponentiation is performed by repeated multiplication (that is, 3x3 is the same as 3 · x · x · x, which is four multiplications), then there are a total of 6 + 4 + 3 + 2 +1 or 15 multiplications and five (5) additions.
We can use Horner’s Method to successively factor out x as follows:
ƒx) = 8x5 + 5x4 - 3x3 + 9x2 + 2x -7
= (8x4 + 5x3 - 3x2 + 9x + 2)x -7
= ((8x3 + 5x2 - 3x + 9)x + 2)x -7
= (((8x2 + 5x - 3)x + 9)x + 2)x -7
= ((((8x + 5)x - 3)x + 9)x + 2)x -7
The new form of the polynomial only requires five multiplcations and five additions,.
This is an improvement from N(N +1)/2 multiplications and N additions to N multiplications and N additions.
We can use a simple loop to do the steps in this process.
…
{numbers will be entered in the order x, -7, 2, 9, -3, 5, 8}
writeln('enter x: ');
read(x);
lower := 1;
upper := 5;
subtotal := 0;
writeln('enter coefficients right to left:');
for counter := lower to higher
do begin
writeln('enter next coefficient ');
read(n);
subtotal := subtotal * x + n;
end; {for}
writeln('the answer is',subtotal);
…
Note that we can slightly increase efficiency by moving the first coefficient out of the loop (because we don’t really need to multiply by zero):
…
{numbers will be entered in the order x, -7, 2, 9, -3, 5, 8}
writeln('enter x: ');
read(x);
lower := 2;
upper := 5;
writeln('enter coefficients right to left:');
writeln('enter first coefficient ');
read(subtotal);
for counter := lower to higher
do begin
writeln('enter next coefficient ');
read(n);
subtotal := subtotal * x + n;
end; {for}
writeln('the answer is',subtotal);
…
It should be easy to write a short program that can evaluate a polynomial of any degree. And that is left as a problem for the student.
The next refinement to our sample code is to get the information from arrays rather than from user input.
…
{array has the numbers in the order x, -7, 2, 9, -3, 5, 8}
{x is set to the value to be evaluated}
lower := 2;
upper := 5;
subtotal := n[1];
for counter := lower to higher
do begin
writeln('enter next coefficient ');
subtotal := subtotal * x + n[counter];
end; {for}
writeln('the answer is',subtotal);
…
Coding example: I am making heavily documented and explained open source code for a method to play music for free — almost any song, no subscription fees, no download costs, no advertisements, all completely legal. This is done by building a front-end to YouTube (which checks the copyright permissions for you).
View music player in action: www.musicinpublic.com/.
Create your own copy from the original source code/ (presented for learning programming).
return to table of contents
free downloadable college text book
Because I no longer have the computer and software to make PDFs, the book is available as an HTML file, which you can convert into a PDF.
|
|
| previous page | next page |
| Tweets by @osdata |
free computer programming text book projectBuilding a free downloadable text book on computer programming for university, college, community college, and high school classes in computer programming. If you like the idea of this project, Supporting the entire project: If you have a business or organization that can support the entire cost of this project, please contact Pr Ntr Kmt (my church) free downloadable college text book on computer programming. |
This web site handcrafted on Macintosh 
computers using Tom Bender’s Tex-Edit Plus 
and served using FreeBSD 
.
†UNIX used as a generic term unless specifically used as a trademark (such as in the phrase “UNIX certified”). UNIX is a registered trademark in the United States and other countries, licensed exclusively through X/Open Company Ltd.
Names and logos of various OSs are trademarks of their respective owners.
Copyright © 2010 Milo
Created: November 23, 2010
Last Updated: November 23, 2010
return to table of contents
free downloadable college text book
|
|
| previous page | next page |
