Here’s a post to get this blog started.

In class we’ve been talking about root finding schemes such as the Bisection method, Newton’s method, etc., and how they can be used to evaluate functions such as sqrt(), invSqrt(), etc. That’s fine, but what would you use if you wanted a really fast implementation of invSqrt()?

Back when Quake3’s source code first became available, I remember seeing a number of interesting discussions about the where, why, how and who of a piece of Quake3 code that looked something like this:

float InvSqrt (float x){
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0×5f3759df - (i>>1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}

The last update of x is essentially a Newton step of the invSqrt iteration, however the really interesting and clever part is the initial guess and the nonobvious choice of the constant 0×5f3759df. While this function does not provide high accuracy, it was good enough for Quake3, and their implementation executes faster than 1f/fsqrt(x), which is impressive.If you’re interested in learning more, below are a number of informative and investigative articles.

Yours truly,

FantasticFloat

References:

• Beyond3D article: Origin of Quake3’s Fast InvSqrt() [Part1, Part2]
• CodeMaestro: Magical Square Root Implementation in Quake III
• Chris Lomont, “Fast Inverse Square Root,” 2003 (manuscript).
• Charles McEniry, “The mathematics behind the fast inverse square root function code,” August 2007 (manuscript).