Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Testing for Divisibility by 19

blog.plover.com

Post reply on HN
Print view View original

31–40 of 42 posts

Re: Testing for Divisibility by 19

#31

Post by [deleted] »

est31 wrote: post #15
dmurray wrote: post #6

Earlier quoted context omitted.

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…

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.

[deleted]

Re: Testing for Divisibility by 19

#32

Post by JadeNB »

pearjuice wrote: post #18

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.

Re: Testing for Divisibility by 19

#33

Post by thechao »

pinteresting wrote: post #24
dmurray wrote: post #6

Earlier quoted context omitted.

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…

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.

Re: Testing for Divisibility by 19

#35

Post by alisonkisk »

polyterative wrote: post #4

can this kind of trick be implemented in a compiler for any benefit?

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)

Re: Testing for Divisibility by 19

#36

Post by onlyrealcuzzo »

8bitsrule wrote: post #30

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.

This is similar to Vedic math, right?

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

Re: Testing for Divisibility by 19

#37

Post by imheretolearn »

8bitsrule wrote: post #30

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

Re: Testing for Divisibility by 19

#38

Post by mjd »

cousin_it wrote: post #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.

You are absolutely right. I have corrected the article.

Re: Testing for Divisibility by 19

#39

Post by Chinjut »

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.

Re: Testing for Divisibility by 19

#40

Post by qayxc »

rjmunro wrote: post #20
qayxc wrote: post #12

Earlier quoted context omitted.

> 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

Post reply on HN