Bit-shifting to multiply and divide?

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?

re: Bit-shifting to multiply and divide?

"Nobody" <nobody@cox.net> skrev i en meddelelse
news:kaQld.93842$G15.28203@fed1read03...[color=blue]
>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).[/color]

That 11% improvement you got must have been with code that wasn't compiled
at max. level of optimization.[color=blue]
> 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?
>[/color]

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

re: Bit-shifting to multiply and divide?

Nobody wrote:[color=blue]
> 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;[/color]

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

re: Bit-shifting to multiply and divide?

Karthik Kumar wrote:

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

Oops .. Herez the right one.

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



--
Karthik.
' Remove _nospamplz from my email to mail me. '

re: Bit-shifting to multiply and divide?

"Nobody" <nobody@cox.net> wrote in message
news:kaQld.93842$G15.28203@fed1read03...[color=blue]
> 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[/color]
addition[color=blue]
> / subtraction instead (doing this saved me about 11% time on my 2.26ghz[/color]
P4).[color=blue]
> 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?
>
>[/color]

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.

re: Bit-shifting to multiply and divide?

Method Man wrote:[color=blue]
> "Nobody" <nobody@cox.net> wrote in message
> news:kaQld.93842$G15.28203@fed1read03...
>[color=green]
>>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[/color][/color]
[...][color=blue][color=green]
>>but is it possible to do this for the division?[/color]
>
> 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.[/color]

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

re: Bit-shifting to multiply and divide?

> x / 255 = x / 256 * ( 1 + 1/255)[color=blue]
>
> Not really sure if you want to express it this way.
> Still you can't get rid of the division as you can see..[/color]

And this is very close to:

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

Niels Dybdahl