Bit-shifting to multiply and divide?

[Nobody]

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?

 

[Peter Koch Larsen]

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

 

[Karthik Kumar]

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 Kumar]

Karthik Kumar wrote:

[snipped]

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

Oops .. Herez the right one.

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

 

[Method Man]

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.

 

[josh]

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

 

[Niels Dybdahl]

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