The main idea behind it is that adding 19 to a number is the same as adding 20, then subtracting one.
So, most of the time, it adds 2 to the ‘tens’ column, and subtracts 1 from the units column. Twice that -1 plus that 2 equals zero, which is divisible by 19.
When it doesn’t, it adds 1 to the tens column and 9 to the ones column. Twice that 9 plus that 1 equals 19, which also is divisible by 19.
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, integer division and modulus are implemented at the hardware level. I think tricks like this could improve the modulus operation if the processor vendors wanted to add additional dedicated instruction codes for say, divide19. For most workloads this will not be a useful thing to do. But you can't rule it out: before Bitcoin existed nobody built processors which were optimized for calculating millions of SHA-256 hashes in parallel.
That's not correct. In compiled languages, if for example denominator can be computed at compile time, it will almost certainly be optimized to use tricks, the easiest one is to just convert it to a multiply.
A division instruction can take a variable length of cycles to solve depending on the complexity of the division, it has terrible throughput and can be 100x slower than something like an addition, and that's on modern architectures!
Did you ever notice how a calculator can sometimes take a visible amount of time to compute something, and sometimes it was instant? Some instructions are more expensive than others!
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.
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.
No bitmask will give you divisibility by 3 in base 16
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')
Unless your hardware implements BCD arithmetic, this method is pretty much guaranteed to be slower than just applying the MOD directly:
Direct calculation: 1 division
Proposed method: 1 division plus 1 bit shift plus 1 addition (per digit) plus 1 intermediate register
finally one division
It doesn't matter whether division is implemented in hardware. On machines with BCD support, benchmarking would be required to see whether this method is beneficial.
The key difference is that computers don't have any trouble adding/subtracting arbitrary 8/16/32/64 numbers, but human performance gets much worse when there's more than 1 or 2 non-zero or carrying. So while humans like to find ways to round things off, computers care more about minimizing the number of additions and multiplications, but don't have much preference for the (small, constant) complexity of each operation. (Except multiplying/dividing by powers of 10 -- both humans and computers prefer that)
It does double the residue, but modulo 19. 2 * 18 = 36 = 17 (mod 19) and 2 * 10 = 20 = 1 (mod 19). The reason is that the method consists essentially of two steps. (1) Subtract a suitable multiple of 19 to make the number a multiple of 10. (2) Divide by 10. And dividing by 10 is the same as multiplying by 2, since 2 * 10 = 20 = 1 (mod 19).
Now heres the part where we do change the residue. We note that 10 and 19 are coprime. So 17 * 10^2 is divisible by 19 if and only if 17 is. So replacing 17 * 10^2 with 17 might change residue, but wont change divisibility.
It's a net loss if you just memorise them as isolated curiosities and use them to do a job that a calculator could do better, but it's a net gain (I'd argue even an absolute gain) if it introduces you to the idea, all the more relevant in the age of high-powered, fast computers, that sometimes there's a cleverer way to do something than brute force.
One other neat trick that I like is that calculating the N modulus after multiplying a series of numbers together can be done by applying the modulus to a running accumulator after each term in the series is multiplied. So if you have a series that will definitely overflow an IEEE float, you can keep the operation in bounds without using a BigNumber structure.
Reminded me of the example in "Vedic mathematics" - the "ekadhikena purvena" ("one more than the previous one") sutra using which 1/19 was expanded into decimals. For 19, "one more than the previous one" is 1+1=2 so doubling and adding becomes the rule. For 29, it is 2+1=3, so tripling and adding.
Analogous rules can be made for every divisor, but at any rate, here's how it works:
10 is 1/2 in mod 19 world (that is, 10 * 2 = 1 in mod 19 world). So if you have a number ABCD, which means A * 10^3 + B * 10^2 + C * 10 + D, that turns into A / 2^3 + B / 2^2 + C / 2 + D in mod 19 world.
If that's zero, your original number was divisible by 19, otherwise it wasn't. More generally, this would have the same remainder modulo 19 as the original number.
Just as well, instead of looking at ABCD, we can divide it through by 10^3 and look at A.BCD = A + B / 10 + C / 10^2 + D / 10^3. This amounts to starting with D, dividing by 10 and adding C, then dividing by 10 again and adding B, etc.
In mod 19 world, A.BCD = A + B * 2 + C * 2^2 + D * 2^3, and amounts to starting with D, then doubling it and adding C, then doubling that and so on. Again, if the result is zero, the original number was divisible by 19, otherwise it wasn't.
In general, this "Go from least significant digit to most significant digit, constantly doubling and adding the next digit" process will yield as its result 2^(number of digits - 1) * the original number, in mod 19 world.
41 comments
[ 2.9 ms ] story [ 87.5 ms ] threadSo, most of the time, it adds 2 to the ‘tens’ column, and subtracts 1 from the units column. Twice that -1 plus that 2 equals zero, which is divisible by 19.
When it doesn’t, it adds 1 to the tens column and 9 to the ones column. Twice that 9 plus that 1 equals 19, which also is divisible by 19.
- Triple the last digit and add the next-to-last.
- Triple that and add the next digit over.
- Repeat until you've added the leftmost digit.
(Spot the pattern? Even works for divisibility by 09, where one has to multiply by one each time)
In any case, integer division and modulus are implemented at the hardware level. I think tricks like this could improve the modulus operation if the processor vendors wanted to add additional dedicated instruction codes for say, divide19. For most workloads this will not be a useful thing to do. But you can't rule it out: before Bitcoin existed nobody built processors which were optimized for calculating millions of SHA-256 hashes in parallel.
A division instruction can take a variable length of cycles to solve depending on the complexity of the division, it has terrible throughput and can be 100x slower than something like an addition, and that's on modern architectures!
Did you ever notice how a calculator can sometimes take a visible amount of time to compute something, and sometimes it was instant? Some instructions are more expensive than others!
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.
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)
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.
Yeah - I misunderstood there and thought they meant divisibility by 16 or 256 not in base 16 or 256. Should've had my morning coffee first :D
Direct calculation: 1 division
Proposed method: 1 division plus 1 bit shift plus 1 addition (per digit) plus 1 intermediate register finally one division
It doesn't matter whether division is implemented in hardware. On machines with BCD support, benchmarking would be required to see whether this method is beneficial.
The key difference is that computers don't have any trouble adding/subtracting arbitrary 8/16/32/64 numbers, but human performance gets much worse when there's more than 1 or 2 non-zero or carrying. So while humans like to find ways to round things off, computers care more about minimizing the number of additions and multiplications, but don't have much preference for the (small, constant) complexity of each operation. (Except multiplying/dividing by powers of 10 -- both humans and computers prefer that)
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.
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)
Take a number say 123. Write it as 1 * 10^2 + 2 * 10 + 3.
In the first step we multiply parts of this expression by 20. This doesn't change the residue since 20 = 1 mod 19
Now heres the part where we do change the residue. We note that 10 and 19 are coprime. So 17 * 10^2 is divisible by 19 if and only if 17 is. So replacing 17 * 10^2 with 17 might change residue, but wont change divisibility.Also, that earlier post introduces a graph-/regex-/dfa-based solution for solving divisibility that reminds me of [2].
[1]: https://blog.plover.com/math/divisibility-by-7.html
[2]: https://codegolf.stackexchange.com/a/75326
I.e. (a * b * c) % N = (((a * b) % N) * c) % N
https://en.wikibooks.org/wiki/Vedic_Mathematics/Sutras/Ekadh...
E.g. 228? 240 = 12x20, 240-12 = 228.
2337? 2360 = 118x20.
https://en.wikipedia.org/wiki/Vedic_Mathematics
I couldn't point to a reason but I have been using this method since childhood without being taught :)
10 is 1/2 in mod 19 world (that is, 10 * 2 = 1 in mod 19 world). So if you have a number ABCD, which means A * 10^3 + B * 10^2 + C * 10 + D, that turns into A / 2^3 + B / 2^2 + C / 2 + D in mod 19 world.
If that's zero, your original number was divisible by 19, otherwise it wasn't. More generally, this would have the same remainder modulo 19 as the original number.
Just as well, instead of looking at ABCD, we can divide it through by 10^3 and look at A.BCD = A + B / 10 + C / 10^2 + D / 10^3. This amounts to starting with D, dividing by 10 and adding C, then dividing by 10 again and adding B, etc.
In mod 19 world, A.BCD = A + B * 2 + C * 2^2 + D * 2^3, and amounts to starting with D, then doubling it and adding C, then doubling that and so on. Again, if the result is zero, the original number was divisible by 19, otherwise it wasn't.
In general, this "Go from least significant digit to most significant digit, constantly doubling and adding the next digit" process will yield as its result 2^(number of digits - 1) * the original number, in mod 19 world.