 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);
…
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 |
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, At the time I write this message I am a few days from becoming homeless. That will greatly interfere with my ability to create this project, which can help nearly 20 million U.S. college students and more than 150 million students world-wide. I am looking for 30 rich people or corporations willing to donate $10 a month to my church so that the church can provide a place indoors for me to continue work. If you want to donate, please see help project. Thanks much. 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. |
I do the news as an unpaid volunteer for KOCI 101.5 FM, Newport Beach/Costa Mesa (also available on the web)
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 |
