What could be cuter than the infamous fast inverse square root function used in the Quake 3 engine:
The interesting part is the calculation of the initial approximation, splitting this down into the basic steps, we have:
To get some insight into what’s going on here, we need to look at the representation of floating point numbers. An IEEE-754 float consists of a sign bit, an exponent value, and a mantissa. The exponent is an 8-bit value, the mantissa has 23 bits, both unsigned. As usual, a suitable notation is key: simplifying a little (specifically, ignoring NaNs, infinities and denormalized numbers), we shall write a float of the form
m a real in the range
[0,1), and this represents
2e-127(1+m), negated if the sign bit is 1.
To warm up, it’s helpful to look at a simpler example:
View original post 659 more words