http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

> Recently, I'm interested in writing very efficient code.

>

> Problem:

> there is a sequence { a(0), a(1), ..., a(n-1) } and a very small

> positive integer k, write an algorithm without using multiply to

> calculate the following formula:

> n-1

> _____

> \

> \ ki

> / 2 * a(i)

> /_____

> i = 0

>

> My answer is following:

>

> inline int sum(int a[], size_t n, size_t k) {

> int sum = 0;

> while (n--) (sum <<= k) += a[n];

> return sum;

> }

>

> would you please point out if my answer is the best answer?
I think, it is pretty close: you are using the Horner scheme to evaluate the

polynomial, and you realize multiplication by powers of 2 by means of bit

shifting. The only wasted instruction that I see is a redundant initial bit

shift of sum at a point where it is known to be 0. Probably, the compiler

can optimize that away.

Keep in mind, however, that efficiency is hard to argue without reference to

a specific platform. On the other hand, platform specific questions are off

topic in this group.

> And could you cite out your answer?
Huh?

Best

Kai-Uwe Bux