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: