Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Your Answer


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.