Bit-shifting to multiply and divide?

Discussion in 'C++' started by Nobody, Nov 14, 2004.

  1. Nobody

    Nobody Guest

    I have some code that I am trying to optimize for speed...

    trying to squeeze every last CPU cycle out... I remembered an old trick
    where dividing & multiplying can be sped up by using bitshifts and addition
    / subtraction instead (doing this saved me about 11% time on my 2.26ghz P4).
    Really easy with powers of two. I implemented this last night when I was
    tired, and this morning, I realize it was not exactly right (values were
    slightly off)...

    I am trying to multiply / divide by 255.

    for some reason I thought:

    (x << 8) - 1 = x * 255
    (x >> 8) + 1 = x / 255

    like I said, late at night....

    seems like the correct formula is:

    (x << 8) - x = x * 255;

    but is it possible to do this for the division?
     
    Nobody, Nov 14, 2004
    #1
    1. Advertising

  2. "Nobody" <> skrev i en meddelelse
    news:kaQld.93842$G15.28203@fed1read03...
    >I have some code that I am trying to optimize for speed...
    >
    > trying to squeeze every last CPU cycle out... I remembered an old trick
    > where dividing & multiplying can be sped up by using bitshifts and
    > addition / subtraction instead (doing this saved me about 11% time on my
    > 2.26ghz P4).


    That 11% improvement you got must have been with code that wasn't compiled
    at max. level of optimization.
    > Really easy with powers of two. I implemented this last night when I was
    > tired, and this morning, I realize it was not exactly right (values were
    > slightly off)...
    >
    > I am trying to multiply / divide by 255.
    >
    > for some reason I thought:
    >
    > (x << 8) - 1 = x * 255
    > (x >> 8) + 1 = x / 255
    >
    > like I said, late at night....
    >
    > seems like the correct formula is:
    >
    > (x << 8) - x = x * 255;
    >
    > but is it possible to do this for the division?
    >


    It probably is (i haven't studied your code carefully). What is important
    here is that the compiler should know how to do it the best way, so just
    continue writing x/8 or x/255 or whatever.

    /Peter
     
    Peter Koch Larsen, Nov 14, 2004
    #2
    1. Advertising

  3. Nobody wrote:
    > I have some code that I am trying to optimize for speed...
    >
    > trying to squeeze every last CPU cycle out... I remembered an old trick
    > where dividing & multiplying can be sped up by using bitshifts and addition
    > / subtraction instead (doing this saved me about 11% time on my 2.26ghz P4).
    > Really easy with powers of two. I implemented this last night when I was
    > tired, and this morning, I realize it was not exactly right (values were
    > slightly off)...
    >
    > I am trying to multiply / divide by 255.
    >
    > for some reason I thought:
    >
    > (x << 8) - 1 = x * 255
    > (x >> 8) + 1 = x / 255
    >
    > like I said, late at night....
    >
    > seems like the correct formula is:
    >
    > (x << 8) - x = x * 255;


    This is possible since -
    x * 255 = x * (256 - 1 )
    = (x * 256) - x
    ^^^^^^^^
    Can be got by shifting to the left.

    And here you get rid of the solitary multiplication.
    As Peter had already mentioned - a smart compiler would
    do this for you anyway.

    x / 255 != x / 256 * ( 1 + 1/255)

    Not really sure if you want to express it this way.
    Still you can't get rid of the division as you can see..

    --
    Karthik.
    ' Remove _nospamplz from my email to mail me. '
     
    Karthik Kumar, Nov 14, 2004
    #3
  4. Karthik Kumar wrote:

    [snipped]
    >
    > x / 255 != x / 256 * ( 1 + 1/255)


    Oops .. Herez the right one.

    x / 255 = x / 256 * ( 1 + 1/255)



    --
    Karthik.
    ' Remove _nospamplz from my email to mail me. '
     
    Karthik Kumar, Nov 14, 2004
    #4
  5. Nobody

    Method Man Guest

    "Nobody" <> wrote in message
    news:kaQld.93842$G15.28203@fed1read03...
    > I have some code that I am trying to optimize for speed...
    >
    > trying to squeeze every last CPU cycle out... I remembered an old trick
    > where dividing & multiplying can be sped up by using bitshifts and

    addition
    > / subtraction instead (doing this saved me about 11% time on my 2.26ghz

    P4).
    > Really easy with powers of two. I implemented this last night when I was
    > tired, and this morning, I realize it was not exactly right (values were
    > slightly off)...
    >
    > I am trying to multiply / divide by 255.
    >
    > for some reason I thought:
    >
    > (x << 8) - 1 = x * 255
    > (x >> 8) + 1 = x / 255
    >
    > like I said, late at night....
    >
    > seems like the correct formula is:
    >
    > (x << 8) - x = x * 255;
    >
    > but is it possible to do this for the division?
    >
    >


    I was once asked in an interview how to efficiently divide by 7 without
    using division. I implemented it like so:

    unsigned div7(unsigned x) {
    long temp;
    temp = (x * 293) >> 11; /* 1/7 is approx. equal to 293/2048 */
    return (unsigned int) temp;
    }

    I am not sure if this helps (or is 100% correct), but you can use the same
    strategy to divide by 255.
     
    Method Man, Nov 14, 2004
    #5
  6. Nobody

    josh Guest

    Method Man wrote:
    > "Nobody" <> wrote in message
    > news:kaQld.93842$G15.28203@fed1read03...
    >
    >>I have some code that I am trying to optimize for speed...
    >>
    >>trying to squeeze every last CPU cycle out... I remembered an old trick
    >>where dividing & multiplying can be sped up by using bitshifts and
    >> addition / subtraction instead

    [...]
    >>but is it possible to do this for the division?

    >
    > I was once asked in an interview how to efficiently divide by 7 without
    > using division. I implemented it like so:
    >
    > unsigned div7(unsigned x) {
    > long temp;
    > temp = (x * 293) >> 11; /* 1/7 is approx. equal to 293/2048 */
    > return (unsigned int) temp;
    > }
    >
    > I am not sure if this helps (or is 100% correct), but you can use the same
    > strategy to divide by 255.


    This works. I personally would write it more like:

    unsigned div7(unsigned x)
    {
    return static_cast<unsigned>(
    static_cast<unsigned long>(x * (2048/7)) / 2048);
    }

    (of course, then this technically uses division... and has *slightly*
    higher error due to rounding)

    If your compiler doesn't know how to convert multiplication/division by
    powers of 2 into bit shifts, you need a better compiler. (are you sure
    you had optimizations turned on?)

    Division by 7, eg, is a different matter. The range where this method
    is valid isn't the same as the range where a simple divide by 7 is
    valid, so the compiler will probably not be able to do it automatically.

    You're essentially doing a fixed-point multiply by the reciprocal.

    -josh
     
    josh, Nov 15, 2004
    #6
  7. > x / 255 = x / 256 * ( 1 + 1/255)
    >
    > Not really sure if you want to express it this way.
    > Still you can't get rid of the division as you can see..


    And this is very close to:

    x / 256 * ( 1 + 1/256)=x/256+x/65536

    Niels Dybdahl
     
    Niels Dybdahl, Nov 15, 2004
    #7
    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. Replies:
    2
    Views:
    19,375
    Thomas Stanka
    Dec 15, 2005
  2. GGG
    Replies:
    10
    Views:
    12,737
    Donar
    Jul 6, 2006
  3. Replies:
    5
    Views:
    601
    Christian Bau
    Sep 1, 2005
  4. Replies:
    8
    Views:
    479
    osmium
    Oct 14, 2006
  5. Default User
    Replies:
    16
    Views:
    751
    James Kanze
    Jul 3, 2008
Loading...

Share This Page