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.