## Polynomial ladders vs Horner's Scheme

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

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

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

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

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

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

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

$\displaystyle = ((((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 $\displaystyle P(x)$, for a particular value of $\displaystyle x$, in the following 5 steps

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

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

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

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

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

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

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

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

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

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

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

4) compute $\displaystyle 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.