I am studying about optimizing alogrithms.(Prof. Skiena's Algorithm Guide book)
One of the exercises asks us to optimize an algorithm:
Suppose the following algorithm is used to evaluate the polynomial p(x) = a^(xn) + a^n−1(xn−1) + . . . + a(x) + a p := a0; xpower := 1; for i := 1 to n do xpower := x ∗ xpower; p := p + ai ∗ xpower end
(Here xn, xn-1... are the names given to distinct constants.)
After giving this some thought, the only way I found to possibly improve that algorithm is as follows
p := a0; xpower := 1; for i := 1 to n do xpower := x ∗ xpower; for j := 1 to ai p := p + xpower next j next i end
With this solution I have converted the second multiplication to addition in a for loop.
- Do you find any other way to optimize this algorithm?
- Is the alternative I have suggested better than the original? (Edit: As suggested in the comments, this question though related to the problem deserves another question of its own. Please ignore.)