6 ms·

It’s interesting how fairly complex bit twiddling hacks are well-known for integers, but even very simple but useful bit twiddles for floats (like this one) are

It’s interesting how fairly complex bit twiddling hacks are well-known for integers, but even very simple but useful bit twiddles for floats (like this one) are obscure enough to warrant their own article. Of course, the most famous bit manipulation of floats is the fast inverse square root trick [0]. The bits of a float as an integer literal are proportional to its log2 value (plus a constant), which is handy for computing a reciprocal square root in logspace, which when converted back to a float gets exponentiated, yielding the answer (after a couple more refinement steps). If you actually take the time to manually hammer out the bitwise manipulations, the fast inverse square root is quite simple, but it is nonetheless regarded as black magic, likely due to the totally non-explanatory comments in the Quake source code. Funnily enough, directly following the fast inverse square root in the Quake source code is a function to compute absolute values by zeroing the float sign bit [1], just as described in the article. [0] https://en.wikipedia.org/wiki/Fast_inverse_square_root#Aliasing_to_an_integer_as_an_approximate_logarithm https://en.wikipedia.org/wiki/Fast_inverse_square_root#Alias... [1] https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb10315479fc00086f08e25d968b4b43c49/code/game/q_math.c#L574-L578 https://github.com/id-Software/Quake-III-Arena/blob/dbe4ddb1...

Y_Y 5y ago
What if the twiddle wasn't obscure and the article was unwarranted?
- MontyCarloHall 5y ago
  Given the amount of discussion this article has sparked on HN, I’d argue that as obvious as it might be, the technique is nonetheless obscure. The amount of highly experienced and accomplished programmers I’ve encountered who have no idea how floating point numbers work is astoundingly high. If a similar article were written about how shifting an integer to the right by one bit is equivalent to dividing it by two, I highly suspect it would attract no attention on this site, aside from a couple dismissive comments grousing about why such a basic fact needs its own article.
  - jrochkind1 5y ago
    You can of course have some idea how floating point numbers work, but still not know how to bit twiddle abs(). I don't know what to take from the fact that Java stdlib didn't use it until Java 18? It does seem like it wasn't obvious to at least someone who knew something. > If a similar article were written about how shifting an integer to the right by one bit is equivalent to dividing it by two, I highly suspect it would attract no attention on this site, Nah, it would be full of comments of people saying "well of course I knew that! doesn't everyone who's anyone? I can't believe how many newbies don't though!" :)
HWR_14 5y ago
Well, with bit twiddling for floats, you have some very important questions. Like, do you maintain the distinct NaN values or are you okay with all NaNs producing a valid (but possibly different) NaN value.
kevin_thibedeau 5y ago
Bit twiddling integers doesn't require unsafe type punning like this. It's also largely safe to assume a nominal two's complement machine is all your code will ever run on. If not, you'll know to be careful. You can't make such blanket assumptions with floating point representations.
- MontyCarloHall 5y ago
  Great points. Out of curiosity, what are some examples of modern architectures that don’t use IEEE 754 floats? Realistically, how often would one ever write code that needs to be portable between an architecture that uses IEEE 754 and one that doesn’t? I could only imagine this ever being an issue for code that needs to be deployed to a wide variety of exotic embedded systems, which is an extremely niche case IMO.
  - Banana699 5y ago
    >what are some examples of modern architectures that don’t use IEEE 754 floats Mainstream? I can't think of one. Googling the question yields a stackoverflow question from 2010 that lists the 5 or 6 major architectures (x86, PowerPc, SPARC, Arm,.. ) and about a dozen more as supporting x86. So it's a fairly safe assumption to make. One area where vanilla IEEE754 isn't used that immediately came to my mind is high performance ML at companies like facebook and Google, the generic range-precision tradeoff that FP offers is inefficient and they ended up designing several new formats with smaller sizes or larger ranges. Googling "Alternatives to FP in ML" or "Custom FP format <company-name>" yields a lot. Another "niche" area is finance, insurance, taxes and anything nearby, fixed point in those area is, I hear, a must. Because all the usual invariants of high school algebra that FP breaks actually have significance. (imagine the well-known FP flaw "x+epsilon == x, with epsilon non-zero" playing out in these contexts.) In any case, number portability in a language like C++ is a breeze. You design a myNumber class and overload all relevant operators and that's it. Compiler will make sure to inline the calls if they're a one-line simple floating point operations, but otherwise you can freely change the implementation of the class and the calculations never look different.
colejohnson66 5y ago
> The bits of a float as an integer literal are proportional to its log2 value (plus a constant), … I watched a video[0] a while back about that. Once that coincidence(?) was explained, Q_rsqrt finally made sense. [0]: https://youtu.be/p8u_k2LIZyo https://youtu.be/p8u_k2LIZyo (~20 minutes)

Y_Y 5y ago

What if the twiddle wasn't obscure and the article was unwarranted?

MontyCarloHall 5y ago
Given the amount of discussion this article has sparked on HN, I’d argue that as obvious as it might be, the technique is nonetheless obscure. The amount of highly experienced and accomplished programmers I’ve encountered who have no idea how floating point numbers work is astoundingly high. If a similar article were written about how shifting an integer to the right by one bit is equivalent to dividing it by two, I highly suspect it would attract no attention on this site, aside from a couple dismissive comments grousing about why such a basic fact needs its own article.
- jrochkind1 5y ago
  You can of course have some idea how floating point numbers work, but still not know how to bit twiddle abs(). I don't know what to take from the fact that Java stdlib didn't use it until Java 18? It does seem like it wasn't obvious to at least someone who knew something. > If a similar article were written about how shifting an integer to the right by one bit is equivalent to dividing it by two, I highly suspect it would attract no attention on this site, Nah, it would be full of comments of people saying "well of course I knew that! doesn't everyone who's anyone? I can't believe how many newbies don't though!" :)

HWR_14 5y ago

Well, with bit twiddling for floats, you have some very important questions. Like, do you maintain the distinct NaN values or are you okay with all NaNs producing a valid (but possibly different) NaN value.

kevin_thibedeau 5y ago

Bit twiddling integers doesn't require unsafe type punning like this. It's also largely safe to assume a nominal two's complement machine is all your code will ever run on. If not, you'll know to be careful. You can't make such blanket assumptions with floating point representations.

MontyCarloHall 5y ago
Great points. Out of curiosity, what are some examples of modern architectures that don’t use IEEE 754 floats? Realistically, how often would one ever write code that needs to be portable between an architecture that uses IEEE 754 and one that doesn’t? I could only imagine this ever being an issue for code that needs to be deployed to a wide variety of exotic embedded systems, which is an extremely niche case IMO.
- Banana699 5y ago
  >what are some examples of modern architectures that don’t use IEEE 754 floats Mainstream? I can't think of one. Googling the question yields a stackoverflow question from 2010 that lists the 5 or 6 major architectures (x86, PowerPc, SPARC, Arm,.. ) and about a dozen more as supporting x86. So it's a fairly safe assumption to make. One area where vanilla IEEE754 isn't used that immediately came to my mind is high performance ML at companies like facebook and Google, the generic range-precision tradeoff that FP offers is inefficient and they ended up designing several new formats with smaller sizes or larger ranges. Googling "Alternatives to FP in ML" or "Custom FP format <company-name>" yields a lot. Another "niche" area is finance, insurance, taxes and anything nearby, fixed point in those area is, I hear, a must. Because all the usual invariants of high school algebra that FP breaks actually have significance. (imagine the well-known FP flaw "x+epsilon == x, with epsilon non-zero" playing out in these contexts.) In any case, number portability in a language like C++ is a breeze. You design a myNumber class and overload all relevant operators and that's it. Compiler will make sure to inline the calls if they're a one-line simple floating point operations, but otherwise you can freely change the implementation of the class and the calculations never look different.

colejohnson66 5y ago

> The bits of a float as an integer literal are proportional to its log2 value (plus a constant), … I watched a video[0] a while back about that. Once that coincidence(?) was explained, Q_rsqrt finally made sense. [0]: https://youtu.be/p8u_k2LIZyo https://youtu.be/p8u_k2LIZyo (~20 minutes)