Problem Detail: I have been trying to understand the difference between normal polynomial evaluation and horner’s method. usually it takes 3n-1 operations while horner’s method reduces it to 2n operations. I tried a couple of explanations but they were too theoritical. I would be glad if somebody comes up with a decent and simple explanation.
Asked By : user2512046
Answered By : Yuval Filmus
Let’s compute the polynomial $2+3x+x^2+15x^3$ using Horner’s method: $$ 2 + x(3 + x(1 + 15x)). $$ The complete set of steps is $$ begin{align*} &t_1 to 15 times x &t_2 to t_1 + 1 &t_3 to t_2 times x &t_4 to t_3 + 3 &t_5 to t_4 times x &t_6 to t_5 + 2 end{align*} $$ Compare this to the “trivial” method: $$ begin{align*} &t_1 to x times x &t_2 to t_1 times x &t_3 to 15 times t_2 &t_4 to 3 times x &t_5 to 2 + t_4 &t_6 to t_5 + t_1 &t_7 to t_6 + t_3 end{align*} $$ Here the idea is to compute the powers $1,x,x^2,x^3$ and then take the linear combination corresponding to the polynomial. Since one of the coefficients is $1$ (coefficient of $x^2$), we only need $7$ rather than $8$ operations.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23037
