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

Suppose one wished to evaluate the polynomial for multiple values of .

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

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

1) compute

2) compute

3) compute

4) compute

5) compute

On the other hand, it can be shown that can be expressed as follows:

.

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

1) compute

2) compute

3) compute

4) compute .

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.