Commissioned for this museum · after the Quake III Arena source, 1999

The Number Nobody Could Explain

C·1999·21 lines·589 bytes

/*
 * One over the square root of a number, to about two decimal places,
 * without a square root and without a division.
 */
float Q_rsqrt(float number)
{
    long  i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;

    i  = *(long *) &y;                  /* read the float as an integer   */
    i  = 0x5f3759df - (i >> 1);         /* what the ... ?                 */
    y  = *(float *) &i;                 /* read it back as a float        */

    y  = y * (threehalfs - (x2 * y * y));   /* one step of Newton-Raphson */

    return y;
}

Curator’s note

The comment in the original says what the ...?, and it was left in the shipped source. Nobody who found this file could explain the constant either.

The trick rests on what a floating-point number actually is in memory: a sign, an exponent, and a fraction, laid out in that order. Read those bits as an ordinary integer instead and you get, near enough, a scaled version of the *logarithm* of the number. And the logarithm of one-over-a-square-root is just the logarithm halved and negated — which in integer arithmetic is a shift and a subtraction. So i >> 1 halves the logarithm, and subtracting from a constant negates it and corrects the offset the exponent format introduces. Reading the bits back as a float undoes the logarithm. What comes out is a first guess, good to about one per cent.

The last line is one step of Newton–Raphson, which turns one per cent into about a sixth of one per cent and then stops, because that was accurate enough to light a room in a video game and a second step would have cost more than it was worth.

The constant is not derived anywhere in the source. It is close to, but not equal to, the value the algebra suggests — somebody searched for a better one and never wrote down how.

Measured across values from 0.01 to 1000, the worst error is 0.175 per cent.