Inverse square root revisited

A few years ago the algorithm included in Quake III Arena to calculate a quick approximation of the inverse square root became a common topic in blogs. This inverse square root is useful for calculating the angles of incidence and reflection of lighting and shader effects.

In fact a lot has already been written about this topic so, in order to save you some time, I want to start commenting that there is a machine instruction in the SSE (Streaming SIMD Extensions) set that should be much faster. This instruction is the rsqrt, in fact if we do not seek an exact square root the calculation of rsqrt (x) * x should be faster than the sqrt instruction, although the latter has more precision. Anyway, it is always better to test things out.

If you want to pursue the subject, the algorithm is discussed in this research paper from 2003.

float fastInvSqrt(float x) {
    float xhalf = 0.5f * x;
    int i = *(int *)&x; // Cast the number to integer
    i = 0x5f3759df - (i >> 1); // Magic number
    x = *(float*)&i; // Cast result back to float
    x = x*(1.5f-(xhalf*x*x)); // Apply one iteration of the Newton's method
    return x;
}

The magic number allows to approximate the inverse square root using integer arithmetic. In order to obtain it properties of logarithms and changes of representation between integer and floating point are used. At the end one iteration of Newton's method is applied.

The explanation is here.

Related entries:

Counting bits