# Efficient divisibility testing

### The example

Here is a low computational cost method to test if an integer $x$ is divisible by another integer $d$, useful in C-like languages (assembly included). It replaces a possibly costly **modulus** `%`

operation with a usually lower cost **multiplication** `*`

.

Here is an example illustrating the method for divisibility by 5:

1 2 3 4 5 6 7 8 9 10 11 12 |
uint32_t x = ... // common method if ((x%5) == 0) { // do something } // cheaper method, completely equivalent if (x * 3435973837U <= 858993459U) { \\ do something } |

What trickery is this? How does it work? Where do the constants **3435973837U** and **858993459U** come from?

Note the magic numbers depend on the type of $x$. The above example requires $x$ is an unsigned 32 bit integer, and the language has multiplication overflow computed modulus 32. Many common languages (C,C++,C#,Java, ..) do this.

Efficient divisibility testing full post

(595 words, estimated 2:23 mins reading time)