Saturday, May 17, 2008

The Lore of the Inverse Square Root function


This one is for all the 3D geeks!

I had posted some useful optimizations for Graphic programmers earlier, and one of the optimizations I had suggested was one I saw in the Quake 3 source code, which performs the inverse square root, i.e 1 / sqrt(x). In 3D Graphics, the question of who came up with the 'magic' constant
0x5f3759df continues to be a question that 3D geeks still seek to answer! Most attribute it to the legendary programmer John Carmack, the man behind the Quake, Doom and all id Software Game Engines. However there are several other people attributed to it, and John himself refused to take claim for the creation of the constant in the mail:

-----Original Message-----
From: John Carmack
Sent: 26 April 2004 19:51
Subject: Re: Origin of fast approximated inverse square root

At 06:38 PM 4/26/2004 +0100, you wrote:

>Hi John,
>
>There's a discussion on Beyond3D.com's forums about who the author of
>the following is:
>
>float InvSqrt (float x){
> float xhalf = 0.5f*x;
> int i = *(int*)&x;
> i = 0x5f3759df - (i>>1);
> x = *(float*)&i;
> x = x*(1.5f - xhalf*x*x);
> return x;
>}
>
>Is that something we can attribute to you? Analysis shows it to be
>extremely clever in its method and supposedly from the Q3 source.
>Most people say it's your work, a few say it's Michael Abrash's. Do
>you know who's responsible, possibly with a history of sorts?

Not me, and I don't think it is Michael. Terje Matheson perhaps?

John Carmack

Why this is so important could be understood by the fact that Chris Lomont, a professor at Purdue took up the task of deriving that constant by mathematical means for the initial approximation of the Newton Raphson method (that the magic code uses), and his 'mathematically and theoretically' brilliant approximation constant turned out to perform WORSE than the constant found in the Quake III source code. So the question that arises is how John Carmack, or the author who originally wrote the code managed to figure out the magic approximation. That could be pretty useful I think for designing other fast mathematical functions.

So this article on Beyond3D.com does a great job of tracing down the original author, or atleast a major contributor, after a great deal of digging around. Check it out:
Origin of Quake III's Fast Inverse Sqrt()

2 comments:

Anonymous said...

For a better explanation, check out http://www.mceniry.net/papers/Fast%20Inverse%20Square%20Root.pdf

Shashank Shekhar said...

Thanks, was an interesting paper. I haven't tried out the speed tests on the derived constant yet, but what's pretty useful is the constant for double-precision floating-point numbers too.

Shashank