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

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

    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
     
    , Dec 4, 2005
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  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
    #3
  4. Kai-Uwe Bux 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
    >
    > 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
     
    Kai-Uwe Bux, Dec 5, 2005
    #4
  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
    #5
  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
    #6
  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
    #7
  8. <> 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
    #8
  9. "" <> 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
     
    Niklas Norrthon, Dec 5, 2005
    #9
  10. red floyd Guest

    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 answer is following:


    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.
     
    red floyd, Dec 5, 2005
    #10
  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
    >
    > 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.
     
    , Dec 6, 2005
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brent Minder
    Replies:
    3
    Views:
    417
    Brent
    Dec 28, 2003
  2. Anders
    Replies:
    4
    Views:
    521
    Greg Burns
    Jul 19, 2004
  3. H.MuthuKumaraRajan
    Replies:
    3
    Views:
    490
    H.MuthuKumaraRajan
    Feb 4, 2004
  4. xkenneth
    Replies:
    8
    Views:
    367
    Bruno Desthuilliers
    Feb 6, 2008
  5. Tim Chase
    Replies:
    0
    Views:
    107
    Tim Chase
    Dec 16, 2013
Loading...

Share This Page