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.

Links: