Why was the fast inverse square root algorithm so ingenious?

Question

In 2005 ID software open source the game Quake 3 Arena. When they did it was discovered was an algorithm that was so ingenious and all it did was calculate the inverse of a square root.

The easy way to calculate the inverse of a square root being

float y = 1 / sqrt(x);

But then again this functionality has already been figured out and can be used with the #include <math.h> directive.

The code from the game being...

 float InvSqrt(float x){
    float xhalf = 0.5f * x;
    int i = *(int*)&x;            
    i = 0x5f3759df - (i >> 1);    
    x = *(float*)&i;              
    x = x*(1.5f - xhalf*x*x);     
    return x;
}

So what exactly is the purpose of calculating the inverse of a square root in a non-standard way. Also, why would a game engine be interested in calculating the inverse of a square root anyway?

Answer 1

Inverse square root is used a lot for vector normalisation :

$$xn = \frac{x }{ \sqrt{x^2 + y^2 + z^2}}$$

Which has many uses in computer graphics, such as calculating illumination.

With a traditional FPU, even a good one, this is a very time consuming operation : the multiplications and additions are fast (and some can be paralleled) but division is slow (tens of cycles), square root is slower (or just as slow as division).

$\frac{1 }{ \sqrt{x}}$ can be calculated directly (instead of square root then division) by using the Newton-Raphson root finding method, that converges quite fast with this function.

While floating-point units offers great precision, computer graphics don't need that much, as everything is constrained into a few thousands pixels and hundreds of colours hues.

So, here is the need of a quick algorithm that gives a good enough value. And this is the brilliant solution.

There are two parts :

float xhalf = 0.5f * x;
int i = *(int*)&x;            
i = 0x5f3759df - (i >> 1);    
x = *(float*)&i;

This first part calculates an approximate value, it does floating point calculations using integers, using some tricks. Floating point numbers have a exponent part 2^N and a mantissa between 1.0 and 1.9999. An integer shift does something like a square root for the exponent part ($\frac{1 }{ \sqrt{2^N}} = 2^{-N/2}$) : This is what does "-(i >> 1)" part above. The 0x5f3759df constant does a good enough interpolation for the mantissa.

x = x*(1.5f - xhalf*x*x);     
return x;

The second part is a application of the Newton-Raphson algorithm, to add more precision to the result. It can be repeated for even more accurate results. But, again, for graphics, it's good enough.

Answer 2

A simple reason for wanting this non-standard way is to think about how many operations you would need to do in finding sqrt(x), and by extension 1/sqrt(x).

One approach to finding sqrt(x) is as follows: you have to establish a lower bound, an upper bound, and a guess. You can start with lower bound is 0, upper bound is max(x,1), and your guess can be any number between your lower and upper bounds. You could choose a default guess "g" that's the minimum of 2^n for some fixed number n and the average of your bounds. Now you need to compute g^2 and compare that with x and adjust a lower or upper bound accordingly and repeat the process. Next update g and repeat. Do this loop over and over again until g^2 is sufficiently close to x. And then you can compute 1/g to get 1/sqrt(x).

How many times will you have to do this loop? If you got a lucky number, maybe less than a handful. If you got an unlucky number, 10s or even 100s of times. Clearly this is rarely if ever as quick as the fast inverse square root function.

Why would a game engine need this? Games use graphics, and graphics use the pythagorean theorem for computing distances, which implies the use of square roots.

Answer 3

What you can take away from this: When you are given a problem, it is often possible to solve the problem, without solving obvious sub-problems. Like here, where you can calculate 1/sqrt(x) significantly faster than calculating the square root, and dividing 1 by the square root. ( On many implementations it is actually so fast, if you need a square root, the fastest known way is to calculate 1/sqrt(x) with this method and multiplying by x).

Another problem: Determine the number of primes from 1 to 10^20. The obvious way is finding primes and counting them. Not much slower than O(N). But who said we want to know the primes? Nobody said that. What we want is the number of primes. And that can be found in about O(N^(2/3)). (There are two simple algorithms that calculate the number of primes <= N in O(N / log N) and O(N / log^2 N)).

Simpler case: we want the 10 largest elements of an array. Obviously you sort it and take the last 10 elements. But nobody asked you to sort the array, and you can find the largest 10 elements a lot faster.

Answer 4

Why would you need 1 / sqrt(x) ?

If you try calculating sqrt(x) and 1 / sqrt(x) using Newton iteration, you’ll find that the first requires a division in each iteration step, while the latter can be done using only multiplications. And multiplications are _ a lot_ faster than divisions. So 1 / sqrt(x) is a lot faster to calculate than sqrt(x) using Newton iteration. So much faster that on many processors x * sqrt(1/x) is faster to calculate than sqrt(x).

Sometimes you need y / sqrt(x), so you change this to y * sqrt(1/x). x^1.5 is x^2 * sqrt(1/x). y / sqrt(x^1.5) = y * (1 / sqrt(x^3)). Each of these is much faster to calculate.

Note that a similar method allows calculating 1/x using Newton iteration without any divisions.