I am studying about optimizing alogrithms.(Prof. Skiena’s Algorithm Guide book)
One of the exercises asks us to optimize an algorithm:
<code>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
</code>
<code>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
</code>
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
<code>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
</code>
<code>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
</code>
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:
- 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.)
2
The standard solution is to notice that one has many multiplications with the same number x.
So instead of
<code>p(x) = a_n*x^n + a_n−1*x^n−1 + . . . + a_1*x + a_0
</code>
<code>p(x) = a_n*x^n + a_n−1*x^n−1 + . . . + a_1*x + a_0
</code>
p(x) = a_n*x^n + a_n−1*x^n−1 + . . . + a_1*x + a_0
one might write
<code>p(x) = (...((a_n*x) + a_n−1)x + ... + a_1)*x + a_0
</code>
<code>p(x) = (...((a_n*x) + a_n−1)x + ... + a_1)*x + a_0
</code>
p(x) = (...((a_n*x) + a_n−1)x + ... + a_1)*x + a_0
Perhaps easier to read:
<code>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)
</code>
<code>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)
</code>
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:
<code>p := a_n;
for i is n-1 to 0
p := p*x + a_i
</code>
<code>p := a_n;
for i is n-1 to 0
p := p*x + a_i
</code>
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.
0