Linear Algebra for Games - Game Programming Algorithms and Techniques - page 55

The Legendary “John Carmack Inverse Square Root”
In the 1990s, personal computers did not have processors that could ef-
ficiently perform mathematical operations on floating point numbers.
On the other hand, operations on integers were far more efficient.
This was a problem in 3D games, because almost all calculations are
done with floats instead of integers. This forced developers to come
up with clever ways to perform common operations. One such prob-
lem area was the square root, and specifically the inverse square root.
Why the inverse? When normalizing a vector, you can either divide
each component by a square root or multiply each component by one
over the square root. Multiplication was typically more efficient than
division, so that's why the inverse was chosen.
When the Quake III Arena source code was released, programmers no-
ticed it contained a rather impressive implementation of the inverse
square root. Here is the C code, presented with the actual comments
(certain colorful language has been censored):
Click here to view code image
float Q_rsqrt( float number)
{
int i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( int * ) &y; // evil floating
point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the
f***?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
// 1st iteration
return y;
}