Re:Testing for Divisibility by 19
by isaacimagine on Monday November 23, 2020 @06:07AM
(#25185548)
Other similar compiler optimizations do exist, for, for example, reducing a multiplication by a constant into a series of additions and bit-shifts. It might be possible to reduce divisibility checks for constants in binary at compile time in a similar manner, but no existing work comes to mind.
[ Parent
| on HN ]
There's a way for odd divisors, since they have a multiplicative inverse mod 2^n.
For example, the inverse of 3 modulo 2^32 is 0xAAAAAAAB. If you multiply an unsigned number x by 0xAAAAAAAB, the result is less than or equal to 0xFFFFFFFF/3 if and only x is divisible by 3.
Of course this is only possible for non-bignum computations.
But there are other tricks for bignums, for example the number of even set bits in a multiple of three is equal to the number of odd set bits, because 4*n+k = n+k (mod 3) and the property is true for 0 and 3 but not 1 and 2.
There's an extensive section in Hacker's Delight (https://en.wikipedia.org/wiki/Hacker%27s_Delight) that derives 32-bit constants that, when used with 32x32 -> 32 multiplication, produce division by small constants.