[deleted]
Testing for Divisibility by 19
21–30 of 42 posts
Re: Testing for Divisibility by 19
#22I used to love these kinds of strategies as a kid. I often wished I'd been in an abacus class as an elementary school student.
Re: Testing for Divisibility by 19
#23can 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.
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.
Re: Testing for Divisibility by 19
#24can 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…
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!
Re: Testing for Divisibility by 19
#25Mark's earlier post [1] which covered divisibility much more extensively mentioned a division algorithm that I've never learned: short division.
Also, that earlier post introduces a graph-/regex-/dfa-based solution for solving divisibility that reminds me of [2].
Re: Testing for Divisibility by 19
#26One 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.
I.e. (a * b * c) % N = (((a * b) % N) * c) % N
Re: Testing for Divisibility by 19
#27Mark's earlier post [1] which covered divisibility much more extensively mentioned a division algorithm that I've never learned: short division. 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
The second part of [1] with the graphs/diagrams is pretty interesting, thanks for sharing!
Re: Testing for Divisibility by 19
#28> 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.
Well there are two parts to it really.
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
1 * 10^2 + 2 * 10 + 3
1 * 10^2 + (2+3*2) * 10
1 * 10^2 + 8 * 10
(1+8*2) * 10^2
17 * 10^2
Re: Testing for Divisibility by 19
#29Reminded 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.
https://en.wikibooks.org/wiki/Vedic_Mathematics/Sutras/Ekadh...
Re: Testing for Divisibility by 19
#30In some cases its quicker to think of a larger number that's a multiple of 20, then subtract the multiple,
E.g. 228? 240 = 12x20, 240-12 = 228.
2337? 2360 = 118x20.