Quake 3′s Fast Inverse Square Root Function

Note: This is not meant to be an authoritative mathematical description, and I’m pretty late to the party.. I was experimenting with the code, and am scratching an itch. For a far superior description, please look at Chris Lomont’s excellent analysis.

The Infamous Code

x2 = number * 0.5F;
y  = number;
i  = * ( long * ) &y;
i  = 0x5f3759df - ( i >> 1 );
y  = * ( float * ) &i;
y  = y * ( threehalfs - ( x2 * y * y ) );
// y  = y * ( threehalfs - ( x2 * y * y ) );

The Function to Model

How Did the Authors Think of This?

Interestingly, this method is nearly identical to one from a mathematical text called “An Introduction to Numerical Analysis“, where there is an application exercise to compute the square root of a function, taking advantage of the storage of floating point numbers.

My Numerical Methods book for this semester contains the full derivation of the method from “An Introduction to Numerical Analysis” that uses linear interpolation for an initial guess to Newton’s Method that gives the accuracy of the function to provably under 4.7E-14 for four iterations. Chris Lomont’s paper goes into much more detail about the method for choosing a suitable constant that the “Quake 3″ authors likely used. Linear interpolation gives a fairly good guess, but it’s possible to take advantage of the way the constant is stored to give us a much better guess. As you can see below, the guess isn’t linear, but actually fits the curve very well without any iterations of the Newton-Rhapson method.

The initial guess is very good. How good? It nearly overlaps the function. The guess is added in red:

I was going to compare the output of the Quake 3 method with the real output, but it was difficult finding a view where there was any very noticeable difference at all, so suffice it to say that it is very close.

Some of the Math

We are trying to find a quick approximation for the function . This can be rearranged as . We want to find the roots of this function for , which are +/- . Note that .

Newton-Raphson Method

Back in the days of Newton, all math had to be calculated by hand. Since it was often impossible to calculate the exact value of many results, approximations were needed.

The Newton-Raphson method is used to quickly approximate function roots. The basic idea is that we start off with a guess that we think is very close to the value of the root. We then take the tangent line at the function f(x). Provided that f(x) is continuous, we follow the tangent line to the X-axis. We then take the derivative at this point and follow the tangent line to the function to the X-axis. Rinse and repeat until you get the precision you need.

It is important to note that this method doesn’t always work: it is not guaranteed to converge, and in fact, you could continue calculating intersections ad infinitum and never get any closer to having the right answer! Therefore, it is important in this instance to try to optimize the initial guess to have as little error as possible.

As with all good methods, this one has an easy-to-remember formula. For a current approximation, , we find by:

For those interested, the derivation can be found here. For the mildly interested, it is derived by taking the first few terms of the Taylor Series of the function.

So to do the Newton-Raphson approximation on a differentiable function, we need one thing:

1. An initial guess of the root. The closer, the better.

Actual Iterative Derivation

One small nit pick I had with Chris Lomont’s paper was that it skipped the actual derivation of the iterative function, so here it is:

When we substitute “” for “” and ““, (Since the function uses the same variable to store the current and next guess), we find the following:

x = x * (1.5 - (x/2) * x * x)

Which looks awfully familiar.

Popularity: 77% [?]