Which is the best way, in C, to see if a number is divisible by another?

Question

Which is the best way, in C, to see if a number is divisible by another? I use this:

if (!(a % x)) {
// this will be executed if a is divisible by x
}

Is there anyway which is faster? I know that doing, i.e, 130 % 13 will result into doing 130 / 13 per 10 times. So there are 10 cycles when just one is needed (I just want to know if 130 is divisible by 13).

Thanks!

Solution 1

I know that doing, i.e, 130 % 13 will result into doing 130 / 13 per 10 times

Balderdash. % does no such thing on any processor I've ever used. It does 130/13 once, and returns the remainder.

Use %. If your application runs too slowly, profile it and fix whatever is too slow.

Solution 2

For two arbitrary numbers, the best way to check is to check whether a % b == 0. The modulus operator has different performance based on the hardware, but your compiler can figure this out much better than you can. The modulus operator is universal, and your compiler will figure out the best sequence of instructions to emit for whatever hardware you're running on.

If one of the numbers is a constant, your compiler might optimize by doing some combination of bit shifts and subtractions (mostly for powers of two), since hardware div/mod is slower than addition or subtraction, but on modern processors the latency (already only a few nanoseconds) is hidden by tons of other performance tricks, so you needn't worry about it. No hardware computes modulus by repeated division (some old processors did division by repeated bit shifts and subtraction, but they still used specialized hardware for this, so it's still faster to have the hardware do it than to try to emulate it in software). Most modern ISAs actually compute both division and remainder in one instruction.

The only optimization that might be useful is if the divisor is a power of two. Then you can use & to mask the low-order bits (by divisor - 1) and check the result against zero. For example, to check if a is divisible by 8, a & 7 == 0 is equivalent. A good compiler will do this for you, so stick with just stick with %.

Solution 3

In the general case, using the modulo operator is likely to be the fastest method available. There are exceptions, particularly if you are interested in whether numbers are divisible by powers of two (in which case bitwise operations are available), but the compiler should choose them automatically for you if you just use %. You are unlikely to be able to do any better for arbitrary values such as 13.

Also, what do you mean by "doing 130 / 13 per 10 times"? It does 130 / 13 once. Which is exactly what is required.

Solution 4

If x is a constant, then yes:

if (a * 0x4ec4ec4ec4ec4ec5 < 0x13b13b13b13b13b2) {
    // this will be executed if a is divisible by 13
}

0x4ec4ec4ec4ec4ec5 is the modular multiplicative inverse of 13 (modulo 2⁶⁴), so if a is really a multiple of 13 then the product will be less than (2⁶⁴/13). (Because a is 13 times some integer n, and n must have fit into a 64-bit word which implies that it was less than 2⁶⁴.)

This only works for odd values of x. For even numbers (i.e. multiples of 2^y for y>0) you can combine this test with a bitwise-AND test (the last y bits of a should be zero. If they are then divide a by 2^y and proceed with the multiplication test.)

This is only worthwhile if x is a constant, because computing the multiplicative inverse is more expensive than integer division.

---

Edit: I am also assuming a and x are unsigned.

View more solutions

Comments

[Michael Burr]

Compilers know how to do this, too. Take a look at the optimized output of (x % 13) in GCC or MSVC and you'll see part of your magic number in use (0x4ec4ec4e + 1) as well as no actual division operation. See stackoverflow.com/questions/2580680/… for more details.

[Joseph]

Good point! But they're both positive, always. Thanks anyway :(

[allonhadaya]

A neat explanation of this exact idea: math.stackexchange.com/questions/1251327/…