# 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.

Share and Enjoy:
This entry was posted in Jack Handy. Bookmark the permalink.

Comments are closed.