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.