Re:Testing for Divisibility by 19
by pinteresting on Monday November 23, 2020 @08:48AM
(#25186692)
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.
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.