Testing for Divisibility by 19 | Hacker News Reader

Testing for Divisibility by 19

blog.plover.com

83 pointsweinzierl38 comments

Open articleView on HN

In 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.

The correct way would be to subtract multiple*diff from the answer of the first multiplication.

I couldn't point to a reason but I have been using this method since childhood without being taught :)

This is similar to Vedic math, right?

https://en.wikipedia.org/wiki/Vedic_Mathematics

Mark'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!

Similarly, 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)

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.

> 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

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.

You are absolutely right. I have corrected the article.

I wonder if it doubles the residue. 20 -> 2, 21 -> 4. But 18 -> 17. And 10 -> 1. So no.

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).

Well, it does double the residue:

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)

Divisibility by 13, 3 days ago : https://news.ycombinator.com/item?id=25165323

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.

https://en.wikibooks.org/wiki/Vedic_Mathematics/Sutras/Ekadh...

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.

I.e. (a * b * c) % N = (((a * b) % N) * c) % N

There's an interesting vsauce video on some divisibility rules: https://www.youtube.com/watch?v=f6tHqOmIj1E

I 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.

I like the novelty but since the introduction of calculators, memorizing tricks like these are a net loss.

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.

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, 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!

Multiplication patterns are how we used to do this on embedded compilers which didn’t have optimizers. For instance: (n * 85)>>8 to divide by 3.

Yeah if dividing by 19 became a common thing for programs to do, companies like intel or ARMvidia would add an optimized instruction for it.

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 may be misunderstanding - a bit mask only tells you if something is divisible by 16 or 256 (or any other power of 2)

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.

> 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.

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

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')

Examples:

0x3c (60) -> sum = 0xf (divisible)

0x2d (45) -> sum = 0xf (divisible)

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.

Computers benefit from different kinds of tricks.

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)

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.

Does it work with "1064"?

Great. 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.

Reply on news.ycombinator.com