Pelles C forum

C language => Tips & tricks => Topic started by: Madmanguruman on April 23, 2007, 06:08:00 PM

Title: The fast inverse square root
Post by: Madmanguruman on April 23, 2007, 06:08:00 PM

This is the somewhat-famous fast inverse square root approximation function that performs almost 4x faster than some stdlib versions of the actual square root function, and is reasonably accurate (good enough for games, etc...)

It uses Newton interpolation along with a magic number that is surprisingly accurate for a first guess.

Here's an authoritative article on the topic:
http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf (http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf)

And here's the code ... (additional Newton steps improves the accuracy)

Code: [Select]

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


Title: Re: The fast inverse square root
Post by: Ben_pcc on July 14, 2007, 07:36:19 AM

I was really excited about that back then as well, but I'm afraid that the built in SQRT instruction that basically all CPUs have nowadays is faster and essentially exact.

BTW, it's Newton Iteration, not interpolation.

For games, you'll be surprised how abused square rooting is. For example, suppose you want a character to grab an object when it's x distance away from it. Well, instead of comparing distances, compare square distance. ie, compare x*x to the square of distance.