Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > How can I write the most efficient code about this problem?

Reply
Thread Tools

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

 
 
storyGerald@gmail.com
Guest
Posts: n/a
 
      12-04-2005
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

 
Reply With Quote
 
 
 
 
Viktor Prehnal
Guest
Posts: n/a
 
      12-04-2005
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
 
Reply With Quote
 
 
 
 
storyGerald@gmail.com
Guest
Posts: n/a
 
      12-05-2005
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

 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      12-05-2005
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
 
Reply With Quote
 
storyGerald@gmail.com
Guest
Posts: n/a
 
      12-05-2005
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

 
Reply With Quote
 
storyGerald@gmail.com
Guest
Posts: n/a
 
      12-05-2005
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

 
Reply With Quote
 
storyGerald@gmail.com
Guest
Posts: n/a
 
      12-05-2005
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

 
Reply With Quote
 
Gernot Frisch
Guest
Posts: n/a
 
      12-05-2005

<(E-Mail Removed)> schrieb im Newsbeitrag
news:(E-Mail Removed) oups.com...
> 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


 
Reply With Quote
 
Niklas Norrthon
Guest
Posts: n/a
 
      12-05-2005
"(E-Mail Removed)" <(E-Mail Removed)> 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
>
> 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
 
Reply With Quote
 
red floyd
Guest
Posts: n/a
 
      12-05-2005
Niklas Norrthon wrote:
> "(E-Mail Removed)" <(E-Mail Removed)> 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 answer is following:


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
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
efficient way to write multiple loops code friend.05@gmail.com Perl Misc 18 10-10-2008 08:51 AM
Most Efficient Way of Exporting CSV data from page Peter ASP .Net 1 11-09-2004 10:41 PM
What is most efficient? OnItemDataBound or using a function Anders ASP .Net 4 07-19-2004 11:29 AM
What is the most efficient way to access common fcts on asp.net pages when using user controls? Brent Minder ASP .Net 3 12-28-2003 02:28 PM



Advertisments