The Lounge is rated PG. If you're about to post something you wouldn't want your
kid sister to read then don't post it. No flame wars, no abusive conduct, no programming
questions and please don't post ads.
There was a question on That Other Site about checking for divisibility by 5 without using the % or / operators, and it had to be as fast as possible.
In proper "That Other Site"-style, the question was immediately closed for not including anything the OP tried, but had the OP done that, I'm sure the OP would have been lambasted for premature optimization.
But whatever. The real point is, the obligatory "you can't beat the compiler" comment was made.
And that turns out to be wrong - here[^]'s the proof. apparently that link doesn't work. Nice job implementing permalinks there. Well just paste this code into this[^]:
Actually yes. I've posted about that before, as you may recall.
In arithmetic modulo 2n, multiplying a number by an odd number is reversible - you can take the multiplicative inverse of the odd number and then multiply by it to get the original number back. Put differently, the function f(x) = x * k (for k odd) is a bijection.
Modular multiplication is associative, so a multiple of k, say n * k, multiplied by inv(k) (the multiplicative inverse of k), is n, because
(n * k) * inv(k) =
// use associativity
n * (k * inv(k)) =
// use definition of multiplicative inverse
n * 1 =
// multiplicative identity
That means that in x * inv(k), the multiples of k "use up" the results from 0 through (232-1)/k, they can't be used twice because it's a bijection, leaving just the numbers bigger than (232-1)/k for non-multiples-of-k.
So it's proven, and for good measure I tried it for all x just to be absolutely certain.
0xCCCCCCCD is, of course, the multiplicative inverse of 5 (modulo 232) and 0x33333333 is (232 - 1)/5
So there, the compiler has been beaten, once again disproving the "the Compiler is a God"-theory. It does use a closely related trick, namely dividing by 5 without a division (then it multiplies by 5 and compares that to the input), and that trick is pretty good too. Compilers are good - putting blind faith in them is not.