Fast inverse square root

A fast algorithm to calculate the inverse of a square root stolen from Quake III.

A fast yet slightly inaccurate algorithm to calculate the inverse square root of a float number. Alogrithm is taken from the game Quake III. Usefulness of the calculation is mostly given if you try to normalize a vector quickly.

float Q_rsqrt(const float inNum)
    long i;
    float x2, y;
    const float threehalfs = 1.5f;

    x2 = inNum * 0.5f;
    y = inNum;
    i = * (long *) &y;
    i = 0x5f3759df - (i >> 1);
    y = *(float *) &i;
    y = y * ( threehalfs - (x2 * y * y); // Newton step
    return y;

and here goes a slightly modified version of it with an explanation in this document

float Q_rsqrt(float inNum)
    float xhalf = 0.5f * inNum;
    int i = * (int *) &inNum; // get bits for floating value
    i = 0x5f375a86 - (i >> 1); // gives initial guess y0
    inNum = *(float *) &i; // convert bits back to float
    inNum = inNum * (1.5f - xhalf * inNum * inNum); // Newton step
    return inNum;

The last step of the operation is an error compensation term based on Newton’s method. typically the error should be below 1 % already after the first iteration but to increase the algorithms accuracy simply repeat the second last line.


Leave a Reply

Your email address will not be published. Required fields are marked *