3 ms·
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 improvemen
by 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 agoYeah 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 agoThat'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 agoMultiplication 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.