3 ms·

Yeah, a more detailed description of this general method seems missing from the article. Anyone care to provide it?

chrchang523 6y ago
See the "Labor of Division" blog posts by the author of libdivide: https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html https://ridiculousfish.com/blog/posts/labor-of-division-epis... https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html https://ridiculousfish.com/blog/posts/labor-of-division-epis...
- joe_the_user 6y ago
  So basically calculating the multiplicative inverse of a number and storing it as something like a float (digits + exponent) with the digits and exponent stored separately to avoid overflow, underflow, accuracy issues. And it's faster if and only if you're repeating division by a single number since you're still doing the equivalent of divide to get the invest (but repeated division is actually quite common so this is useful).
  - yakubin 6y ago
    > And it's faster if and only if you're repeating division by a single number since you're still doing the equivalent of divide to get the invest This is done at compile-time by the compiler. We're talking about division by a constant, not by a variable. So it's always faster.
    - joe_the_user 6y ago
      Doing compile time is one way it is useful and I think that's the most common thing - that's why the tutorials show the resulting assembly instructions. However there are other ways the trick can be used. If the compiler (or the programmer) determines that the program will be doing repeated division by a single quantity (say in a loop), you substitution a calculation of the multiplicative inverse of the quantity first and then substitute multiplication by that inverse for the repeated for the divisions. So you can extend things beyond just division by a constant.
pkaye 6y ago
The book "Hackers Delight" goes over a lot of these kinds of software algorithms for integers.

See the "Labor of Division" blog posts by the author of libdivide: https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html https://ridiculousfish.com/blog/posts/labor-of-division-epis... https://ridiculousfish.com/blog/posts/labor-of-division-episode-iii.html https://ridiculousfish.com/blog/posts/labor-of-division-epis...

joe_the_user 6y ago
So basically calculating the multiplicative inverse of a number and storing it as something like a float (digits + exponent) with the digits and exponent stored separately to avoid overflow, underflow, accuracy issues. And it's faster if and only if you're repeating division by a single number since you're still doing the equivalent of divide to get the invest (but repeated division is actually quite common so this is useful).
- yakubin 6y ago
  > And it's faster if and only if you're repeating division by a single number since you're still doing the equivalent of divide to get the invest This is done at compile-time by the compiler. We're talking about division by a constant, not by a variable. So it's always faster.
  - joe_the_user 6y ago
    Doing compile time is one way it is useful and I think that's the most common thing - that's why the tutorials show the resulting assembly instructions. However there are other ways the trick can be used. If the compiler (or the programmer) determines that the program will be doing repeated division by a single quantity (say in a loop), you substitution a calculation of the multiplicative inverse of the quantity first and then substitute multiplication by that inverse for the repeated for the divisions. So you can extend things beyond just division by a constant.

pkaye 6y ago

The book "Hackers Delight" goes over a lot of these kinds of software algorithms for integers.