What's the fastest way to divide an integer by 3?

int x = n / 3;  // <-- make this faster

// for instance

int a = n * 3; // <-- normal integer multiplication

int b = (n << 1) + n; // <-- potentially faster multiplication

Solution 1:

The guy who said "leave it to the compiler" was right, but I don't have the "reputation" to mod him up or comment. I asked gcc to compile int test(int a) { return a / 3; } for an ix86 and then disassembled the output. Just for academic interest, what it's doing is roughly multiplying by 0x55555556 and then taking the top 32 bits of the 64 bit result of that. You can demonstrate this to yourself with eg:

$ ruby -e 'puts(60000 * 0x55555556 >> 32)'
20000
$ ruby -e 'puts(72 * 0x55555556 >> 32)'
24
$ 

The wikipedia page on Montgomery division is hard to read but fortunately the compiler guys have done it so you don't have to.

Solution 2:

This is the fastest as the compiler will optimize it if it can depending on the output processor.

int a;
int b;

a = some value;
b = a / 3;

Solution 3:

There is a faster way to do it if you know the ranges of the values, for example, if you are dividing a signed integer by 3 and you know the range of the value to be divided is 0 to 768, then you can multiply it by a factor and shift it to the left by a power of 2 to that factor divided by 3.

eg.

Range 0 -> 768

you could use shifting of 10 bits, which multiplying by 1024, you want to divide by 3 so your multiplier should be 1024 / 3 = 341,

so you can now use (x * 341) >> 10
(Make sure the shift is a signed shift if using signed integers), also make sure the shift is an actually shift and not a bit ROLL

This will effectively divide the value 3, and will run at about 1.6 times the speed as a natural divide by 3 on a standard x86 / x64 CPU.

Of course the only reason you can make this optimization when the compiler cant is because the compiler does not know the maximum range of X and therefore cannot make this determination, but you as the programmer can.

Sometime it may even be more beneficial to move the value into a larger value and then do the same thing, ie. if you have an int of full range you could make it an 64-bit value and then do the multiply and shift instead of dividing by 3.

I had to do this recently to speed up image processing, i needed to find the average of 3 color channels, each color channel with a byte range (0 - 255). red green and blue.

At first i just simply used:

avg = (r + g + b) / 3;

(So r + g + b has a maximum of 768 and a minimum of 0, because each channel is a byte 0 - 255)

After millions of iterations the entire operation took 36 milliseconds.

I changed the line to:

avg = (r + g + b) * 341 >> 10;

And that took it down to 22 milliseconds, its amazing what can be done with a little ingenuity.

This speed up occurred in C# even though I had optimisations turned on and was running the program natively without debugging info and not through the IDE.

Solution 4:

See How To Divide By 3 for an extended discussion of more efficiently dividing by 3, focused on doing FPGA arithmetic operations.

Also relevant:

• Optimizing integer divisions with Multiply Shift in C#