Discussion in 'C++' started by storyGerald@gmail.com, Dec 4, 2005.

1. ### Guest

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

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

Gerald

, Dec 4, 2005

2. ### Viktor PrehnalGuest

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

Viktor Prehnal, Dec 4, 2005

3. ### Guest

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

, Dec 5, 2005
4. ### Kai-Uwe BuxGuest

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
>
>
> inline int sum(int a[], size_t n, size_t k) {
> int sum = 0;
> while (n--) (sum <<= k) += a[n];
> return sum;
> }
>

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.

Huh?

Best

Kai-Uwe Bux

Kai-Uwe Bux, Dec 5, 2005
5. ### Guest

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

, Dec 5, 2005
6. ### Guest

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

, Dec 5, 2005
7. ### Guest

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

, Dec 5, 2005
8. ### Gernot FrischGuest

<> schrieb im Newsbeitrag
news:...
> 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

Gernot Frisch, Dec 5, 2005
9. ### Niklas NorrthonGuest

"" <> writes:

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

Niklas Norrthon, Dec 5, 2005
10. ### red floydGuest

Niklas Norrthon wrote:
> "" <> writes:
>
>
>>Recently, I'm interested in writing very efficient code.

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

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

red floyd, Dec 5, 2005
11. ### Guest

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
>
>
> inline int sum(int a[], size_t n, size_t k) {
> int sum = 0;
> while (n--) (sum <<= k) += a[n];
> return sum;
> }
>

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,