Hacker News Reader

Comment by polyterative | Hacker News Reader

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.

Reply on news.ycombinator.com