Talk:Horner scheme
|
|
A notation for the Horner scheme
I posted the following in Talk:Ruffini's rule, but got no response. I'm reposting the content here, since it may be more relevant here:
My professor showed me this algorithm for evaluating polynomials (more) quickly, and it looks very much like synthetic division:
Suppose <math> f(x) = 3x^6 + 5x^3 + 2x^2 + 1 <math> (I just made it up), and I want to know what <math> f(2) <math> is. I setup the problem thusly,
2 | 3 0 0 5 2 0 1
|
| 6 12 24 58 120 240
|-------------------------------------------
3 6 12 29 60 120 241
The 2 at the very left is the parameter, and the rest of the first row is the coefficients of the polynomial. The first coefficient drops down directly. Then I multiply it by the parameter to get 6, which goes to 2nd row, 2nd column. I add the columns (0 + 6) and drop down the sum. Multiply it by the parameter again yields 12, which goes to 2nd row, 3rd column, ... Repeat until the last column, and the last sum is <math> f(2) <math>
This algorithm needed 7 multiplies and 6 adds. Computing <math> f(x) = 3(2)^6 + 5(2)^3 + 2(2)^2 + 1 <math> directly would need 14 multiplies and 4 adds.
Is this a variant of synthetic division, thus belongs to the aritcle? If not, where else is more appropriate? IMHO, it's pretty neat and deserves mention somewhere.
madoka 00:31, Oct 12, 2004 (UTC)
This is precisely the Horner scheme. The long-division-like notation, as far as I know, is your prof's idea.
Loisel 13:42, 14 Oct 2004 (UTC)
Old stuff
I think the first description is gibberish. I'll delete it unless someone protests. Loisel 05:17, 6 May 2004 (UTC)
- Done. Loisel 04:52, 11 May 2004 (UTC)