A while back, my friend Yannick showed me that the source code for Return to Castle Wolfenstein had been made public.

The part that interested him the most was the way they (he knew the name of the developer, I forgot it, sorry) calculated square roots.

I’ll let you have a look at it first:

/*
** float q_rsqrt( float number )
*/
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 fuck?
	y  = *( float * ) &i;
	y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//	y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

	return y;
}

The first thing you may notice is that this looks like it doesn’t make any sense…

The second thing you might notice is that this is in O(1) order, which is very peculiar.

The third thing you probably notice is that comment saying what the fuck?

It took my quite some time to understand what was being done in that method, but it became pretty clear that it is loosely based on Newton’s method, which works by providing an estimate on the resulting value

As an example, consider the following line of python:

a = a - ((a ** 2 - o)/(2 * a))

This is the basic implementation of Newton’s method (considering a the estimate and o the number from which we want the square root), and usually, with about 5 iterations, you get the correct value at 8 or 10 digits:

>>> o = 612.0
>>> a = 10.0
>>> a = a - ((a ** 2 - o)/(2 * a)) ; print a
35.6
>>> a = a - ((a ** 2 - o)/(2 * a)) ; print a
26.395505618
>>> a = a - ((a ** 2 - o)/(2 * a)) ; print a
24.7906354925
>>> a = a - ((a ** 2 - o)/(2 * a)) ; print a
24.7386882941
>>> a = a - ((a ** 2 - o)/(2 * a)) ; print a
24.7386337538
>>> a = a - ((a ** 2 - o)/(2 * a)) ; print a
24.7386337537
>>> a = a - ((a ** 2 - o)/(2 * a)) ; print a
24.7386337537

With the example above, you can see that in 4 iterations, we have a correct value up until the 7th digit, and by the fifth iteration we are correct up to the 10th digit!

Now the really puzzling part about the implementation in Return to Castle Wolfenstein is that the guess is so accurate (for the values commonly passed), that only one iteration is enough.

Pretty cool, isn’t it?