Re:Testing for Divisibility by 19
by bonzini on Monday November 23, 2020 @06:27AM
(#25185633)
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.
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.