0x5f375a86

Okay, so, yeah: XKCD. The mouseover text for that one reads:

Some engineer out there has solved P=NP and it’s locked up in an electric eggbeater calibration routine. For every 0x5f375a86 we learn about, there are thousands we never see.

This is a reference to a neat floating point hack, to which I provide some references below.

Puzzlement

I confess that the significance of the number 0x5f375a86 escaped me. It turns out (thanks, GOOG) to be associated with some (pretty famous) code from Quake3 that computes a reciprocal square root unusually quickly. Reciprocal square roots (often called “inverse square roots” – “inverse” is an abbreviation of “multiplicative inverse”) are extremely useful in many applications, including computer graphics, in which context they must be computed quickly, but need not be computed particularly accurately. The InvSqrt function below trades some accuracy (about 1%) for a 2x – 3x speedup vs. a naive floating point implementation:

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;
}

(Note that this code uses a slightly different magic number; there is some dispute over which is the “best” constant.)

References

Some references for the curious: Here are part 1 and part 2 of an investigation into the origins and author of this code, and here is a discussion of the math behind this hack.