← All articles

The famous inverse square root

I’ve already mentioned before that you can approximate divisions using a division-free Newton-Raphson approximation. You can also use the Newton-Raphson method for approximating the square root and the inverse square root function.

But first, what do we actually use inverse square root and square root for? A lot really – everything that uses a normalized vector; collision responses, lighting and reflection to mention a few. It is an important part of any game and the operation has to be as fast as possible. Back in the day when computers had weaker CPUs and no specialized hardware to handle floating point operations (Today we even have specialized physics cards and specialized lighting circuits), some steps had to be taken to compute the inverse square root a million times each second as quickly as possible.

And here it is, for positive, finite, normalized float inputs. Enable unsafe compilation to compile this example, and compare its speed and accuracy with 1 / sqrt(x) on your target hardware:

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

I could go into details on how this works, but I think it has been described sufficiently on Wikipedia's article Fast inverse square root. Suffice to say that the line with 0x5f3759df is the interesting one; its historical origin is uncertain, but its mathematical role has been analyzed. Several different papers have been written to try and explain how this magic hex code produces the initial approximation.

I included this fast inverse square root function in the Approx.net library (C#).

More in Algorithms

All 25 Algorithms articles →