Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.)
share|improve this question
    
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
add comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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