Addition vs multiplication on algorithm performance

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.)
• Please only ask one question per, well, question ;-) Commented Feb 19, 2013 at 10:35
• @MadKeithV, Gotto agree with you. Qn updated. Commented Feb 19, 2013 at 11:03

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

``````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
``````

``````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.