You don't need the numbers to fit into a register to use the results from the paper I referenced. The same is true of the followup paper https://gmplib.org/~teg

You don't need the numbers to fit into a register to use the results from the paper I referenced. The same is true of the followup paper https://gmplib.org/~tege/division-paper.pdf https://gmplib.org/~tege/division-paper.pdf I agree compilers have not used such algorithms for numbers bigger than a register "for a long time". But bignum libraries certainly have. Note that I did not say "compilers implemented precisely what fish implemented" for a long time, but compilers did "this sort of thing" for a long time. There's another paper referred to by the original one I cited, namely this one http://dl.acm.org/citation.cfm?id=4990 http://dl.acm.org/citation.cfm?id=4990 (1985) which gives lots of algorithms for division by specific integers. Alverson also developed algorithms for division by more problematic divisors in 1991: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1710 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1... This was in fact implemented in hardware in the 64 bit Terra computer and was the work that inspired Montgomery and Granlund. In about 1994 they implemented their algorithms in gcc. The important point I was making is that the Montgomery-Granlund work does not rely on "magic numbers" (divisors of 2^B +/- 1). In fact, in a certain sense, such "algorithms" go back hundreds of years. If you look in Dixon's History of Number Theory under "divisibility rules", you'll essentially find dozens of rules, which can be adapted for any base (where "base" could mean 2^32, 2^64, 2^128, 2^(32*n), etc.). Many divisibility rules basically just consist of an algorithm for computing the remainder quickly and computing the quotient quickly, using a small number of additions, subtractions and multiplications by small constants. That's what I was referring to when I said "this sort of thing". I give a bunch of such rules here: http://wbhart.github.io/SimpleMath/divisrules.html http://wbhart.github.io/SimpleMath/divisrules.html where obviously there I give the rules for base 10. But some of them were even originally stated for general bases.