Origin of Quake3's Fast InvSqrt(), for gaming and math geeks

[psi29a]

http://www.beyond3d.com/articles/fastinvsqrt/

Below a snippet of the article, and it goes on like geekier version of Dan Brown's Da Vinchi Code. Who exactly wrote this elegant bit of code?

To most folks the following bit of C code, found in a few places in the recently released Quake3 source code, won't mean much. To the Beyond3D crowd it might ring a bell or two. It might even make some sense.

Code: Select all

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

Finding the inverse square root of a number has many applications in 3D graphics, not least of all the normalisation of 3D vectors. Without something like the nrm instruction in a modern fragment processor where you can get normalisation of an fp16 3-channel vector for free on certain NVIDIA hardware if you're (or the compiler is!) careful, or if you need to do it outside of a shader program for whatever reason, inverse square root is your friend. Most of you will know that you can calculate a square root using Newton-Raphson iteration and essentially that's what the code above does, but with a twist.

Even John Carmack put in his 2 cents with this email:

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

This is an excellent read for anyone with an interest in programming, gaming, and just plain 'ol treasure hunting.

[MonkWren]

That just means so much to me. You really have no idea. Thank you.

[psi29a]

That just means so much to me. You really have no idea. Thank you.

Care to explain? Perhaps I should implement sarcasm bbcode.

[MonkWren]

Care to explain? Perhaps I should implement sarcasm bbcode.

That would be an excellent addition.

Actually, would someone mind explaining what this means, to me? I don't code, myself, but I find a lot of the underlying principles engaging and interesting. The technical stuff just tends to kinda float past my head.

By the way, I found the article itself very interesting. I just don't quite fully understand the significance of the code.

[arke]

It calculates the inverse square root of x, or 1/sqrt(x). This is extremely important in 3D games because you often need the unit vector, and I believe it's used to calculate the normal vector of things (which is used for when reflecting light). Although this function isn't needed as much anymore (due to FP units being quite speedy), it'll still allow you to do math using purely integer multiplication and addition (extremely fast) versus division and square roots (extremely slow).

[psi29a]

Back in the bad 'ol days (before 2000), when doing math on x86 (Intel chips on PCs), the floating point calculations where extremly slow. So going past the right of the decimal point took a lot of hardware and didn't perform very well, often making software developers who couldn't know what platform their software would run on, had to do all the calculations with 32 bits as a signed integer.

What this means is that, we had to emulate hardware to do fractions in the software. This is before we had powerful graphics graphics card, so there was still a lot of the 3D stuff still being done on the CPU.

So, someone somewhere came up with a trick that only works on 32bit hardware, where we only need precision up to say 8 decimal places.

Ordinarily, you can do a lot more decimal places with the older and more accurate method (in software or using existing hardware), but if you are just throwing up 3d vertices's for video games you don't need that kind of accuracy.

Since 3D games are nothing more than exercises in linear algebra, having an inverse square function that works uber fast, faster than hardware floating point (FP unit) can make or break your application. In a simulation, to calculate this stuff over and over again could takes seconds or longer, but we need to do better in a real-time video game. With this elegant 'hack' it can be done in milliseconds.

It worked quite well, because it was necessary to get the curved surfaces in Quake3 which was one of it's touted features.

I managed to compiled quake3 on my SGI machine (n32 and n64 for the curious), and I couldn't use this hack in n64. Things... went arry.

[Sortep]

wow.... psi has had his genius juice tonight... damn alcohol.. i'm never drinking again.. i'm having to really think about all of this

[psi29a]

wow.... psi has had his genius juice tonight... damn alcohol.. i'm never drinking again.. i'm having to really think about all of this

Killians Irish Red, I code better with Jager though.

[Shalabala]

I tested it on my slow laptop.

Code: Select all

Doing InvSqrt for 2 seconds..
Doing 1.0/sqrtf for 2 seconds..

Result

InvSqrt:   37194912
1.0/sqrtf: 23114018
ratio:     1.60919

1.6 times faster, quite good.

Edit: also tested it agains pow( .. , -0.5) where it was about 3 times faster.

[MonkWren]

Spiffiness. Thanks for the explanation, oh mighty founder!

[psi29a]

I tested it on my slow laptop.

Code:

Doing InvSqrt for 2 seconds..
Doing 1.0/sqrtf for 2 seconds..

Result

InvSqrt: 37194912
1.0/sqrtf: 23114018
ratio: 1.60919

1.6 times faster, quite good.

Edit: also tested it agains pow( .. , -0.5) where it was about 3 times faster.

Good to know there are people in the forums who also do empirical testing.

Spiffiness. Thanks for the explanation, oh mighty founder!

Everything was great up till the comma. Do you have a bone to pick? Cut the crap, please.

edit: if you are jesting, that is cool. Just say so and use emotions. It helps add the visual queue that is lacking in textual conversations.

[MrFelony]

I thought he was being serious....i think he's got a boner for you

[MonkWren]

I thought he was being serious....i think he's got a boner for you

Mmm, yes, I dream about psi all night long. [/sarcasm]

Oh wait, that hasn't been implemented yet.

And yes, it was a joke. I'm nowhere near that obsequious. Although the thanks were real.