Carmack’s Fast Inverse Square Root
You don’t need to be an graphics expert to appreciate why square roots are so useful. It’s used in calculating distance, normalizing vectors, physics simulations, and all other Euclidean and Newtonian tomfoolery.
The number of CPU cycles required to calculate a square root is dozens of times more expensive than that is required to execute a simple math operation. A basic 3D engine can have tens-of-thousands of square root operations per update, so any opportunity to approximate the square root will save you a good number of frame rates.
The code below approximates 1/sqrt(x) using only multiplication and bit-shift operations. This code was heavily used in the Quake II engine:
float InvSqrt(float x) { float xhalf = 0.5f * x; int i = *(int*)&x; i = 0x5f3759d5 - (i >>; 1); x = *(float*)&i; x = x*(1.5f - xhalf*x*x); return x; }
For those who are mathematically curious: The code above approximates the inverse square root by using Newton’s method.
[ Reference ]
