maloki

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.

Filed under: Share, Technology, gaming by Loki