Magical Square Root Implementation In Quake III

One of the sites I regularly read is Worse Than Failure which looks at bizarre bits of code that programmers come across from time to time. (It used to be called WTF, short for "What the F...???", something that Rove has shortened to "What the?" and made a regular segment in his TV show.)

In the comments of one of the recent articles was this code snippet to calculate the square root of a number, which was originally written for Quake III.

float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;

x2 = number * 0.5F;
y  = number;
i  = * ( long * ) &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
// y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

#ifndef Q3_VM
#ifdef __linux__
 assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}

Try Goolging 0x5f3759df and you'll find lots of references. It turns out that the above routine implements a theory called Newton Approximation of roots. The square root of a number can be approximated using a certain calculation, and can be refined by repeating using the results of the previous calculation. The tricky part is the magic number, which generates an initial result which is very close to the actual result, good enough for the purpose.

John Carmack is the programmer who wrote this piece of code. A genius indeed.

Very cool.