11–20 of 42 posts
> The result will be a smaller number which has the same mod-19 residue. It seems to me that the procedure works only for numbers divisible by 19. If it's not divisible, the residue may change. Try 20 for example.
can this kind of trick be implemented in a compiler for any benefit?
Not really, first of all because the tricks are in base 10 But you can make tricks for base 16 or 256 if you really need to check for a certain divisibility multiple times
You don't need any tricks in that case since a simple bit mask (bit-wise AND) will do the trick then.
can this kind of trick be implemented in a compiler for any benefit?
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.
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.
can this kind of trick be implemented in a compiler for any benefit?
I don't think so. It's not really more efficient than long division, with the same number of operations for each digit of the big number. Most of the improvement for humans comes from the fact that you get to deal with smaller numbers (0-9) for a section of those operations than with the bigger range 0-19, but the computer generally doesn't find it easier to multiply by one 64-bit number than another. In any case, in…
> The result will be a smaller number which has the same mod-19 residue. It seems to me that the procedure works only for numbers divisible by 19. If it's not divisible, the residue may change. Try 20 for example.
I wonder if it doubles the residue. 20 -> 2, 21 -> 4. But 18 -> 17. And 10 -> 1. So no.
20 * 2 === 40 === 2 (mod 19)
21 * 2 === 42 === 4 (mod 19)
18 * 2 === 36 === 17 (mod 19), equivalently -1 * 2 === -2 === 17 (mod 19)
10 * 2 === 20 === 1 (mod 19), equivalently -9 * 2 === -18 === 1 (mod 19)
> The result will be a smaller number which has the same mod-19 residue. It seems to me that the procedure works only for numbers divisible by 19. If it's not divisible, the residue may change. Try 20 for example.
I wonder if it doubles the residue. 20 -> 2, 21 -> 4. But 18 -> 17. And 10 -> 1. So no.
Earlier quoted context omitted.
Not really, first of all because the tricks are in base 10 But you can make tricks for base 16 or 256 if you really need to check for a certain divisibility multiple times
> But you can make tricks for base 16 or 256 if you really need to check for a certain divisibility multiple times You don't need any tricks in that case since a simple bit mask (bit-wise AND) will do the trick then.
In this case (division by 3 in mod 16) is the same as base 10: if the sum of digits is divisible by 3 then it is divisible (and the "extra digits" are 'c' and 'f')
Examples:
0x3c (60) -> sum = 0xf (divisible)
0x2d (45) -> sum = 0xf (divisible)
Earlier quoted context omitted.
Not really, first of all because the tricks are in base 10 But you can make tricks for base 16 or 256 if you really need to check for a certain divisibility multiple times
> But you can make tricks for base 16 or 256 if you really need to check for a certain divisibility multiple times You don't need any tricks in that case since a simple bit mask (bit-wise AND) will do the trick then.
I think he's saying in base 16 you can make a trick to check divisibility by e.g. 15 in the same way you can check divisibility by 9 in base 10.
So is 0xE1 (225) divisible by 0xF (15)?
0xE + 0x1 = 0xF, so yes.