How can I write the most efficient code about this problem?

[storyGerald]

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?
And could you cite out your answer? Thank you!



Gerald

 

[Viktor Prehnal]

Hi,
I am not mathematician but I have doutbs your code will work.
I think 2^k can be factorised before the sum, so it should look like
(+ sum is defined (as code array) from 0...n-1)

inline int sum(int a[], size_t n, size_t k) {
int sum = 0;
while (n) sum += a[n--];
return sum << k;
}

Regards, Viktor

 

[storyGerald]

My code is absolutely correct, at least at VC6. Maybe you didn't
understand the problem. The coefficient of 2 is k * i, not k.

Would you please try it again? Thank you!

Regards, Gerald

 

[Kai-Uwe Bux]

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

 

[storyGerald]

I'm sorry to ask questions like that, because I can't use English
fluently. It's not my mother language.
If this sentence hurt somebody, I apologize ^_^.
That wasn't the meaning I want to express.

Regards

Gerald

 

[storyGerald]

I'm sorry to ask questions like that, because I can't use English
fluently. It's not my mother language.
If this sentence hurt somebody, I apologize ^_^.
That wasn't the meaning I want to express.

Regards

Gerald

 

[storyGerald]

I've improved my code now, Here's the improved code:

inline int sum1(int a[], size_t n, size_t k) {
int sum = a[--n];
while (n) (sum <<= k) += a[--n];
return sum;
}

Thank you for giving me suggestions!

Regards, Gerald

 

[Gernot Frisch]

I've improved my code now, Here's the improved code:

inline int sum1(int a[], size_t n, size_t k)
{
int sum = a[--n];
while (n) (sum <<= k) += a[--n];
return sum;
}

you could improve speed by loop-unrolling for the cases:
n==2,3,4,5,6 - test at which point it gets slower.
....and use a register for "sum".

-Gernot

 

[Niklas Norrthon]

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];

Modification of object twice without any sequence points in between.

/Niklas Norrthon

 

[red floyd]

Hoare's Law (also attributed to Knuth): Premature optimization is the
root of all evil.

My question is why? This sounds very much like homework. On modern
processors, assuming k and a) are integral, multiplication is very
efficient.

And the loss in readability/maintainability is not worth the few extra
CPU cycles. You can precalculate 2^k

long coeff = 1; // 2^k0 = 1
const long coeff_factor = 2 << k;
long sum = 0;
for (int i = 0 ; i < n; ++i)
{
sum += coeff * a;
coeff *= coeff_factor;
}

This is just off the cuff, but it's a heck of a lot more
readable/maintainable than your "no multiply" stuff. And a reasonably
intelligent compiler will recognize that you're multiplying coeff by a
power of 2 and optimize accordingly.

Worry about correctness and maintainablilty first, and then worry
about "optimizing" small stuff like this -- and only if an profiler
tells you that the code really is a a bottleneck.

 

[carlmuller]

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?
And could you cite out your answer? Thank you!

You should make it correct first before optimising it.
1. You are modifying the variable "sum" twice between sequence points,
which is not good in C or C++. So the answer may well be wrong,
depending on your compiler settings.
2. I also think it is bad style to have the function name and the local
variable using the same identifier.
3. The parameter a should be const as it is not modified; this will
allow its use in more situations.