4 ms·

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

dmurray 6y ago
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.
- est31 6y ago
  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 6y ago
    [deleted]
- pinteresting 6y ago
  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!
  - thechao 6y ago
    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.
isaacimagine 6y ago
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.
- bonzini 6y ago
  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.
- al2o3cr 6y ago
  There's an extensive section in Hacker's Delight (https://en.wikipedia.org/wiki/Hacker%27s_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.
raverbashing 6y ago
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
- qayxc 6y ago
  > 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.
  - raverbashing 6y ago
    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)
  - rjmunro 6y ago
    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.
    - qayxc 6y ago
      > 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
qayxc 6y ago
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.
alisonkisk 6y ago
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)

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.

est31 6y ago
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 6y ago
  [deleted]
pinteresting 6y ago
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!
- thechao 6y ago
  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.

isaacimagine 6y ago

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.

bonzini 6y ago
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.
al2o3cr 6y ago
There's an extensive section in Hacker's Delight (https://en.wikipedia.org/wiki/Hacker%27s_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.

raverbashing 6y ago

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

qayxc 6y ago
> 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.
- raverbashing 6y ago
  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)
- rjmunro 6y ago
  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.
  - qayxc 6y ago
    > 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

qayxc 6y ago

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.

alisonkisk 6y ago

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)