Talk:Horner scheme

From Wikipedia, the free encyclopedia

1 A notation for the Horner scheme
2 Numerical efficiency
3 Old stuff
4 error in formula

[edit] 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 $f (x) = 3 x 6 + 5 x 3 + 2 x 2 + 1$ (I just made it up), and I want to know what $f (2)$ 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 $f (2)$

This algorithm needed 7 multiplies and 6 adds. Computing $f (x) = 3(2) 6 + 5(2) 3 + 2(2) 2 + 1$ 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)

Actually, I was taught this table layout by a classical mathematician of the first order. He mentioned that people use this method in Europe. I assume from his background that he meant Eastern Europe. Tparameter 18:29, 9 November 2006 (UTC)

It would be nice to see synthetic division written somewhere in this article.. not everyone knows it as Ruffini's rule. Or maybe an example in the typical notation used with synthetic division. Otherwise great article! :-)

[edit] Numerical efficiency

Horner's scheme is more efficient than naive evaluation since it requires less operations. I have always read that it is also more convenient from the floating-point arithmetic point of view, but I don't see why. Can someone provide an easy example of a polynomial and a number where Horner's scheme performs better (in the sense of the relative error) than naive evaluation. Just a little example where I can follows the calculations by hand.