Testing for Divisibility by 19
blog.plover.com
Testing for Divisibility by 19
1–10 of 42 posts
Re: Testing for Divisibility by 19
#2Great. Hope there is a simple math proof before someone write this into a cobol or s/370 assembler routine to save their time :-)
Re: Testing for Divisibility by 19
#3Similarly, for divisibility by 29:
- 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)
Re: Testing for Divisibility by 19
#4can this kind of trick be implemented in a compiler for any benefit?
Re: Testing for Divisibility by 19
#5Great. Hope there is a simple math proof before someone write this into a cobol or s/370 assembler routine to save their time :-)
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.
Re: Testing for Divisibility by 19
#6can 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, 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.
Re: Testing for Divisibility by 19
#7> 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.
Re: Testing for Divisibility by 19
#8can 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.
Re: Testing for Divisibility by 19
#9can 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
Re: Testing for Divisibility by 19
#10can this kind of trick be implemented in a compiler for any benefit?
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.