Addition vs multiplication on algorithm performance

Question

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.

My questions:

1. Do you find any other way to optimize this algorithm?
2. 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.)

• Joris Timmermans: Please only ask one question per, well, question ;-)
• TheSilverBullet: @MadKeithV, Gotto agree with you. Qn updated.

Answer 1

The standard solution is to notice that one has many multiplications with the same number x.

So instead of

p(x) = a_n*x^n + a_n−1*x^n−1 + . . . + a_1*x + a_0

one might write

p(x) = (...((a_n*x) + a_n−1)x + ... + a_1)*x + a_0

Perhaps easier to read:

p(x) := a_3*x^3 + a_2*x^2 + a_1*x + a_0
q(x) := ((a_3*x + a_2)*x + a_1)*x + a_0
p(x) == q(x)

We call such evaluation Horner's method. It translates to approximately:

p := a_n;
for i is n-1 to 0
 p := p*x + a_i

Horner's method has n multiplications and n additions and is optimal.