4 ms·

Compilers have done this sort of thing for a very long time. Here is a well-known paper from 1994 that already tries to do it for more arbitrary constants. htt

by wbhart 12y ago

Compilers have done this sort of thing for a very long time. Here is a well-known paper from 1994 that already tries to do it for more arbitrary constants. https://gmplib.org/~tege/divcnst-pldi94.pdf https://gmplib.org/~tege/divcnst-pldi94.pdf

colanderman 12y ago
No, they haven't. This extends the algorithm you reference to cover the special case of certain "magic numbers" which don't fit nicely in a machine register. From the article: It does not seem to appear in the literature, nor is it implemented in gcc, llvm, or icc, so fish is optimistic that it is original.
- wbhart 12y ago
  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.
- wbhart 12y ago
  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.
  - colanderman 12y ago
    Thanks, that's a very detailed analysis.

by wbhart 12y ago

colanderman 12y ago

No, they haven't. This extends the algorithm you reference to cover the special case of certain "magic numbers" which don't fit nicely in a machine register. From the article: It does not seem to appear in the literature, nor is it implemented in gcc, llvm, or icc, so fish is optimistic that it is original.

wbhart 12y ago
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.
wbhart 12y ago
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.
- colanderman 12y ago
  Thanks, that's a very detailed analysis.