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

(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

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 ;-) – Joris Timmermans Feb 19 '13 at 10:35
  • @MadKeithV, Gotto agree with you. Qn updated. – TheSilverBullet Feb 19 '13 at 11:03

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.