A bit of hardcore programming

Last week Slashdot drew attention to an article about the origin of the fast approximation of the inverse square root in Quake 3. For anyone who likes obscure bits of code it is really quite interesting and I think really understanding the code does make you a better programmer even if you never use it.

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;
}

It computes the result using integer maths instead of floating point operations because back in the day that was faster. This function does the operation to an approximation which is fine when it is used in graphics where the human eye finds it impossible to differentiate small changes in colour. It is one of those functions where the more you iterate the more accurate the result it.

It works by reinterpreting the float bit pattern as an integer then using bit shifting to get at the mantissa. The "magic seed value" is an approximation of the result (it is easier to get a good approximation when the result is in a mostly predictable range).

Anyway a useful tome about this kind of trickery is HACKMEM, you can read it online here.

It would also be a good idea to check out Hacker's Delight.