Efficient divisibility testing
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:
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.