Introduction
Note!
This article is a republishing of something I had up on my personal website a year or so ago before I joined Beyond3D, which is itself the culmination of an investigation started in April 2004. So if timeframes appear a little wonky, it's entirely on purpose! One for the geeks, enjoy.
Origin of Quake3's Fast InvSqrt()
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.
float InvSqrt (float x){
float xhalf = 0.5f*x;
int i = *(int*)
i = 0x5f3759df - (i>>1);
x = *(float*)
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.
How the code works
The magic of the code, even if you can't follow it, stands out as the i = 0x5f3759df - (i>>1); line. Simplified, Newton-Raphson is an approximation that starts off with a guess and refines it with iteration. Taking advantage of the nature of 32-bit x86 processors, i, an integer, is initially set to the value of the floating point number you want to take the inverse square of, using an integer cast. i is then set to 0x5f3759df, minus itself shifted one bit to the right. The right shift drops the least significant bit of i, essentially halving it.
Using the integer cast of the seeded value, i is reused and the initial guess for Newton is calculated using the magic seed value minus a free divide by 2 courtesy of the CPU.
But why that constant to start the guessing game? Chris Lomont wrote a paper analysing it while at Purdue in 2003. He'd seen the code on the gamedev.net forums and that's probably also where DemoCoder saw it before commenting in the first NV40 Doom3 thread on B3D. Chris's analysis for his paper explains it for those interested in the base math behind the implementation. Suffice to say the constant used to start the Newton iteration is a very clever one. The paper's summary wonders who wrote it and whether they got there by guessing or derivation.
So who did write it? John Carmack?
While discussing NV40's render path in the Doom3 engine as mentioned previously, the code was brought up and attributed to John Carmack; and he's the obvious choice since it appears in the source for one of his engines. Michael Abrash was mooted as a possible author too. Michael stands up here as x86 assembly optimiser extraordinaire, author of the legendary Zen of Assembly Language and Zen of Graphics Programming tomes, and employee of id during Quake's development where he worked alongside Carmack on optimising Quake's software renderer for the CPUs around at the time.
Asking John whether it was him or Michael returned a "not quite".
-----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*)
> i = 0x5f3759df - (i>>1);
> x = *(float*)
> 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?
No
If other country's speed cameras are anything like the UK, that could be a problem. If UK cameras can (they can and have) pick people up doing speeds approaching 500 mph in their cars then one wonders what inaccuracies there are on a smaller scale.
I feel that if any given application bombs in this rating system, it should really be branded a 'deferred success' rather than a 'failure'. Those 1337 hackers can be so hard on their programs.
when all you get when you send them scam emails is a form letter telling you that it is a scam email and how to retrieve your money if you lost anything from your PayPal account. I got that even when I worded it as so:
'[all the usual identifying scam guff + note that the date given was 3 months in the future, and I don't have an account] so I know this is a scam email. I'm sending it to you because you claim you're commited to eradicating these'
The death toll now stands at 49, with it expected to rise to above 50.
http://news.bbc.co.uk/1/hi/uk/4663931.stm
This was a horrible incident, I followed it from the minute I had my morning BBC News stream interrupted by a news flash to the minute I went to sleep.
How people can claim to do this in the name of any religion or cause is beyond me... They kill people regardless of any category which could be applied. The racist response against Muslims is unacceptable, with over 30,000 offensive emails being received by the Muslim Council within hours of the attacks.
Very detailed, Big Brother is coming. If Google has this detail and the government are 10 years ahead of whatever we have... I think I'll put a lead box around my farday cage encased, locked down computer with retina scan and audio recognition login. Oh yes, musn't forget the tin coat and hat.
This is a big step for Google, in 5, maybe 10 years I don't think we'll be able to recognise Google. At this rate, Microsoft will have nothing on them soon. I'll check out the free trial, I've played with NASA's application, but this seems to be far higher resolution. Will be very useful for creating high detailed scenery for games - EG: Flight simulator.
Slashdot Mirror
Posting to undo accidental mod.
Well, I made a mess of that. Poor formatting and not anonymous. I tried.
Introduction Note! This article is a republishing of something I had up on my personal website a year or so ago before I joined Beyond3D, which is itself the culmination of an investigation started in April 2004. So if timeframes appear a little wonky, it's entirely on purpose! One for the geeks, enjoy. Origin of Quake3's Fast InvSqrt() 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. float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*) i = 0x5f3759df - (i>>1); x = *(float*) 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. How the code works The magic of the code, even if you can't follow it, stands out as the i = 0x5f3759df - (i>>1); line. Simplified, Newton-Raphson is an approximation that starts off with a guess and refines it with iteration. Taking advantage of the nature of 32-bit x86 processors, i, an integer, is initially set to the value of the floating point number you want to take the inverse square of, using an integer cast. i is then set to 0x5f3759df, minus itself shifted one bit to the right. The right shift drops the least significant bit of i, essentially halving it. Using the integer cast of the seeded value, i is reused and the initial guess for Newton is calculated using the magic seed value minus a free divide by 2 courtesy of the CPU. But why that constant to start the guessing game? Chris Lomont wrote a paper analysing it while at Purdue in 2003. He'd seen the code on the gamedev.net forums and that's probably also where DemoCoder saw it before commenting in the first NV40 Doom3 thread on B3D. Chris's analysis for his paper explains it for those interested in the base math behind the implementation. Suffice to say the constant used to start the Newton iteration is a very clever one. The paper's summary wonders who wrote it and whether they got there by guessing or derivation. So who did write it? John Carmack? While discussing NV40's render path in the Doom3 engine as mentioned previously, the code was brought up and attributed to John Carmack; and he's the obvious choice since it appears in the source for one of his engines. Michael Abrash was mooted as a possible author too. Michael stands up here as x86 assembly optimiser extraordinaire, author of the legendary Zen of Assembly Language and Zen of Graphics Programming tomes, and employee of id during Quake's development where he worked alongside Carmack on optimising Quake's software renderer for the CPUs around at the time. Asking John whether it was him or Michael returned a "not quite". -----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*) > i = 0x5f3759df - (i>>1); > x = *(float*) > 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? No
Of course, any decent compiler would optimise that away to a NOP. ;)
I can't believe you wasted a whole half second of my life reading that. Lawsuit! (Made in Scotland, From Girders)
If other country's speed cameras are anything like the UK, that could be a problem. If UK cameras can (they can and have) pick people up doing speeds approaching 500 mph in their cars then one wonders what inaccuracies there are on a smaller scale.
In other news, Microsoft and Google simaultaneously attempted a hostile takeover of Yahoo.
I feel that if any given application bombs in this rating system, it should really be branded a 'deferred success' rather than a 'failure'. Those 1337 hackers can be so hard on their programs.
when all you get when you send them scam emails is a form letter telling you that it is a scam email and how to retrieve your money if you lost anything from your PayPal account. I got that even when I worded it as so: '[all the usual identifying scam guff + note that the date given was 3 months in the future, and I don't have an account] so I know this is a scam email. I'm sending it to you because you claim you're commited to eradicating these'
The death toll now stands at 49, with it expected to rise to above 50. http://news.bbc.co.uk/1/hi/uk/4663931.stm This was a horrible incident, I followed it from the minute I had my morning BBC News stream interrupted by a news flash to the minute I went to sleep. How people can claim to do this in the name of any religion or cause is beyond me... They kill people regardless of any category which could be applied. The racist response against Muslims is unacceptable, with over 30,000 offensive emails being received by the Muslim Council within hours of the attacks.
I'm almost certain the really secure networks can neither confirm nor deny their own presence.
I'm sorry, but I'll have to wipe your memory now.
Very detailed, Big Brother is coming. If Google has this detail and the government are 10 years ahead of whatever we have... I think I'll put a lead box around my farday cage encased, locked down computer with retina scan and audio recognition login. Oh yes, musn't forget the tin coat and hat.
This is a big step for Google, in 5, maybe 10 years I don't think we'll be able to recognise Google. At this rate, Microsoft will have nothing on them soon. I'll check out the free trial, I've played with NASA's application, but this seems to be far higher resolution. Will be very useful for creating high detailed scenery for games - EG: Flight simulator.