I just bumped into a clever little code snippet used to find the inverse square root:
float InvSqrt(float x) { float xhalf = 0.5f * x; int i = *(int*)&x; // store floating-point bits in integer i = 0x5f3759d5 - (i >> 1); // initial guess for Newton's method x = *(float*)&i; // convert new bits into float x = x*(1.5f - xhalf*x*x); // One round of Newton's method return x; }
[ taken with comments from Kalid Azad @ BetterExpalined.com: Understanding Quake’s Fast Inverse Square Root. ]
Ok, it does not get the exact value but you get a good enough estimate, FAST!
There are two important things to note here:
- Newton’s method (also known as the Newton-Raphson method)
- The ‘magic number’: 0x5f3759d5, an optimized first guess
For a better explanation, I suggest reading Kalid Azad’s article and the paper by Charles McEniry.
Wait a minute, so why is this useful?
In graphics programming, this can be used to normalize vectors quickly. If you noticed the title on the first link, it’s used in the Quake 3 engine. So does that mean the legendary John Carmack wrote this code? If you’re interested, you can read the Origin of Quake3’s Fast InvSqrt() at Beyond3D.
What did I learn?
I usually forget one thing: there are times when speed trumps accuracy. A close quick estimate would be better and there are a number of optimations that can be made. Much thanks goes to Doc Mana who first introduced me to the Newton-Raphson method & how to apply it on code.
