Polynomial ladders vs Horner's Scheme

jamix · #1 $Old$ August 31st, 2009, 06:02 AM

Thought I'd throw this out there, in case anyone wanted to try their hand on it.

Suppose one wished to evaluate the polynomial $P(x) = x^8 - 340x^6 + 34998x^4 - 1036660x^2 + 5x + 1002003$ for multiple values of $x$ .

A typical procedure here would be to apply Horner's Scheme by writing the polynomial as follows:

$P(x) = x^8 - 340x^6 + 34998x^4 - 1036660x^2 + 5x + 1002003$

$= (x^7 - 340x^5 + 34998x^3 - 1036660x + 5)x + 1002003$

$= ((x^6 - 340x^4 + 34998x^2 - 1036660)x + 5)x + 1002003$

$= (((x^4 - 340x^2 + 34998)x^2 + 1036660)x + 5)x + 1002003$

$= ((((x^2 - 340)x^2 + 34998)x^2 + 1036660)x + 5)x + 1002003$

To interpret the above in a more clear way, we would calculate the value of $P(x)$ , for a particular value of $x$ , in the following 5 steps

1) compute $x_1 = x^2 -340$

2) compute $x_2 = x_1*x^2 + 34998$

3) compute $x_3 = x_2*x^2 + 1036660$

4) compute $x_4 = x_3*x + 5$

5) compute $x_5 = x_4*x + 1002003$

On the other hand, it can be shown that $P(x)$ can be expressed as follows:

$((x^2 - 85)^2 - 4176)^2 - 2880^2 + 5x + 2$ .

Given the above, we could compute something like $P(x)$ even more rapidly than Horner's Scheme, using only 4 steps. Namely, we would compute $P(x)$ for particular values of $x$ , using these 4 steps.

1) compute $x_1 = x^2 - 85$

2) compute $x_2 = x_1^2 - 4176$

3) compute $x_3 = x_2^2 - 2880^2 + 2$

4) compute $x_4 = x_3 + 5x$ .

Can such methods like the above be used to achieve fast polynomial evaluations? In particular, is there a way to express an arbitrary polynomial as a sum of a small number of polynomial ladders?

Note: Keep in mind that for this, the ladders don't need to be a product of linear terms such as the ones being discussed in the other threads.