Actually, looking more carefully at the Fish webpage I think they cite 7 as an example because 7 does not divide 2^32+/-1 (or indeed 2^64+/-1). If it did, the q

Actually, looking more carefully at the Fish webpage I think they cite 7 as an example because 7 does not divide 2^32+/-1 (or indeed 2^64+/-1). If it did, the quotient would be a "magic number". However, 7 does divide 2^33 - 1. This "magic number" does fit in a 32 bit word. It's just that division by 2^33 - 1 isn't as trivial as division by 2^32 +/- 1 (it's not much worse though). Multiplication by/storage of a 33 bit number also isn't a problem anyway, because you can use the "IEEE trick" of storing the leading 1 bit implicitly. Multiplication by such a number can be done with one multiply and one addition. Not that you actually need to do this for the divisor 7. The original Montgomery-Granlund work (apparently the basis of GCC division by invariant integers for quite a while) was to always find a quasi-"magic number" which fits in a word. So that was definitely not the innovation of Fish. The followup paper of Moller-Granlund does even better by using a mullow instead of a full mul or mulhigh, which is usually available sooner on modern processors. Fish seem to have found some highly optimised sequences. I'm not entirely clear on how new the ideas themselves are. It's clearly not the same as Montgomery-Granlund, but Montgomery-Granlund use (B^2 - 1)/d (where admittedly d has to be first "normalised"), Fish uses (2^p*B)/d where they fiddle the dividend and do some post-shifting. I'm not even sure if Fish is better than Moller-Granlund, though the latter was 2009, not 1994. I don't want to take away from the contribution of Fish. But it just needs to be viewed in the context of rather a lot of previous work.