Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)

 storyGerald@gmail.com 12-04-2005 02:15 PM

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

 Viktor Prehnal 12-04-2005 02:35 PM

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@gmail.com 12-05-2005 01:42 AM

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 12-05-2005 03:20 AM

storyGerald@gmail.com 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

 storyGerald@gmail.com 12-05-2005 07:40 AM

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@gmail.com 12-05-2005 07:41 AM

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@gmail.com 12-05-2005 08:18 AM

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 12-05-2005 08:44 AM

<storyGerald@gmail.com> schrieb im Newsbeitrag
> 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 12-05-2005 10:40 AM

"storyGerald@gmail.com" <storyGerald@gmail.com> 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

 red floyd 12-05-2005 05:57 PM

Niklas Norrthon wrote:
> "storyGerald@gmail.com" <storyGerald@gmail.com> 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[i]) 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[i];
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.

All times are GMT. The time now is 02:19 AM.