Re:How do compilers optimize divisions?
by conistonwater on Monday February 20, 2017 @06:32PM
(#13691977)
That's pretty cool, although it ought to be mentioned that x must be a uint32. Here's a proof:
Are you sure it doesn't work for other factors? It seems it works for 7, 9, and 11.
So a is equal to 7^{-1} mod 2^16, and b to ceil((2^16-1)/7), etc.
[ Parent
| on HN ]
Re:How do compilers optimize divisions?
by raphlinus on Monday February 20, 2017 @07:30PM
(#13692250)
Duh, you're right on both counts. It should work for any odd divisor, I was just computing the inverse in a dumb way when I tried out other divisors. And I should have stated u32 wrapping arithmetic.
And for even divisors you can separate the divisor into a power of two, and an odd part. The odd part is checked as before, and the power of two is checked with an and mask.
Re:How do compilers optimize divisions?
by raphlinus on Tuesday February 21, 2017 @01:54PM
(#13698313)
An even trickier way to do this is to rotate right by the power of two factor between doing the multiply and the compare.
Re:How do compilers optimize divisions?
by im3w1l on Thursday February 23, 2017 @02:17AM
(#13712246)
That wouldn't work, because a number that is bigger than the threshold could become smaller than it after the rotation.
Wow, that's really cool! Looks like this is a Haskell library: https://hackage.haskell.org/package/sbv-5.15/docs/Data-SBV.h...
Re:How do compilers optimize divisions?
by conistonwater on Monday February 20, 2017 @07:19PM
(#13692194)
Yes, it's really good! Makes it feasible to "sat first, ask questions later", especially for bit trickery.