4 ms·

There's no specific optimisation for these specific numbers. There's a more general optimisation to turn division by a fixed number into a multiplication and sh

There's no specific optimisation for these specific numbers. There's a more general optimisation to turn division by a fixed number into a multiplication and shift where possible (because division is a lot slower than multiplication), and there is another optimisation that eliminates useless shifts. Combined they yield this result for these specific numbers.

joe_the_user 5y ago
Yeah, a more detailed description of this general method seems missing from the article. Anyone care to provide it?
- chrchang523 5y 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 5y 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 5y 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 5y 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 5y ago
  The book "Hackers Delight" goes over a lot of these kinds of software algorithms for integers.
nitrogen 5y ago
As an example of applicability, I used reciprocal multiplication and shifting, plus knowledge of how many bits of accuracy I didn't need, to get my old Kinect code for my former startup to run near 30fps instead of 2-3fps on hardware with no FPU and IIRC no divide instruction.

joe_the_user 5y ago

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

chrchang523 5y 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 5y 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 5y 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 5y 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 5y ago
The book "Hackers Delight" goes over a lot of these kinds of software algorithms for integers.

nitrogen 5y ago

As an example of applicability, I used reciprocal multiplication and shifting, plus knowledge of how many bits of accuracy I didn't need, to get my old Kinect code for my former startup to run near 30fps instead of 2-3fps on hardware with no FPU and IIRC no divide instruction.