Home » Uncategorized » Fast inverse square root

# Fast inverse square root

What could be cuter than the infamous fast inverse square root function used in the Quake 3 engine:

http://en.wikipedia.org/wiki/Fast_inverse_square_root

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 `{sign:1;exponent:8;mantissa:23}` as `(s,e,m)`, with `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:

Here we…

View original post 659 more words