Origin of Quake3's Fast InvSqrt()

geo writes "Beyond3D.com's Ryszard Sommefeldt dons his seersucker hunting jacket and meerschaum pipe to take on his secret identity as graphics code sleuth extraordinaire. In today's thrilling installment, the origins of one of the more famous snippets of graphics code in recent years is under the microscope — Quake3's Fast InvSqrt(), which has been known to cause strong geeks to go wobbly in the knees while contemplating its simple beauty and power." From the article: ""

Comments

What's with use of Pointers?

[MankyD]

Why does the coder use

int i = *(int*)

instead of just

int i = (int)x;

Can someone enlighten me?

Re:What's with use of Pointers?

[mark-t]

If the compiler is willing to hold the union in a register, then yes, using a union should almost certainly be faster... and would potentially save two 32-bit memory copy instructions. In fact, the biggest problem with the approach that the article mentions is that it uses the address-of operator, which generally implies to the compiler that the argument cannot be stored in a register, which would almost certainly prevent the compiler from using assorted possible optimizations.

Re:What's with use of Pointers?

[HTH NE1]

Because in C's own weird way, that's the only way of referring to a float as an int without changing the bits.

<yoda>No. There is another.</yoda>

You can also lie to va_arg() about the type of the argument to achieve the same thing, but it's not as efficient.

Re: A better question:

[Anonymous Coward]

Here's a more interesting question: "How does this function compute 1/x^(1/2)?"
I'm asking, because I have no idea how it works. ;)

hakmem

[trb]

The article barely mentions HAKMEM, but the invsqrt hack is reminiscent of the HAKMEM programming hacks, which were published in 1972. Several of these hacks use bit fiddling with magic constants to perform tasks in straight-line code, that you would ordinarily think of doing with iteration.

HAKMEM is classic bathroom reading for hackers. If you want to do it up old-school, print a copy from original scans, double-sided.

Re:And so why do we care?

[sootman]

Holy crap--you forgot the link but the mods followed your instructions anyway.

Mods: I want +5, Funny for this. No, no, wait: +5, Informative. No, wait, anyone can google something and be "informative." I want a +5, Interesting.

Thanks.

This was done in the 60's and 70's

[Anonymous Coward]

I know my Dad used this technique in the 60's or 70's for vector normalization. It was quite valuable on systems that had no hardware floating point divide (and nothing in that era had a hardware square-root).

Being non-iterative it also has a deterministic speed, which is valuable in
real-time applications.

Integer adds/subtracts on floating-point representations were also sometimes used to approximate multiplication and division (by adding/subtracting the
exponent)

Re:Bad programmer, no cookie

[DeadCatX2]

It is probably a premature optimization that will slow computations down. I imagine they ran some profiling tools and found that they were spending a substantial amount of time in calls to sqrt(), and figured that the division was also time-consuming and for an operation that is performed on so many pixels, it was worthwhile to optimize this particular routine.

This is John Carmack we're talking about. I imagine he knows how to use a code profiler.

The approximations it involve are likely to cause bugs. Floating point always involves approximations. If you don't like them, use a better approximation (double precision). But if you're just trying to, say, figure out which pixel to color, and you approximate the pixel to a few decimal places...I think you're good to go.

I mean, it's not like they're running scientific simulations with this. It's Quake3.

Furthermore, converting floating-points to integers and then doing calculations on them is a trick that has been known for years, long before Quake3. They weren't converting floats to ints. They manipulated the bitwise representation of the float. I'm not sure if that's what you meant, though.

Similar solution for x^(-1/4)

[jothaxe]

I think I have found a similar solution for the reciprocal of the FOURTH root. The code looks almost the same, but it requires a new constant and you shift the bits 2 places instead of just 1. float Inv4thrt(float x) { float x0 = x; int i = *(int*) // get bits for floating value i = 0x4F541EEF - (i>>2); // gives initial guess y0 x = *(float*) // convert bits back to float x = (x/4.0f)*(5 - x0 * x*x*x*x); // Newton step, repeating increases accuracy return x; } Note that the constant I have here is not very carefully tuned so the error may be slightly larger than with the sqrt. Pretty cool, I think.

Re:A famous quote

[KZigurs]

Not so much _faster_ than _guaranteed_ execution time for any given precision required (and if you have 480 pixels on axis on the screen you can play with that for quite a lot).

This is why console games (ps, ps2, xbx, 360, bla bla bla huj) actually stays competitive to PC (more powerful, of course) - since developers has a good idea about actual CPU/GPU available at any given moment, they can safely close to the border way more confidently than on pc. And on PC they usually resort to generic 'will give you the best that I can' routines anyway.

(at least that what I can say after observing xbox360 devel team for 6 months. scary stuff, they do, scary stuff.)

Doesn't work any more

[Markus Registrada]

Nowadays (e.g. since 3.x Gcc) that trick doesn't work any more, as written. To get reliable results you would need to say something more like

float inv_sqrt(float x) { /* death to StudlyCaps! */

float xhalf = 0.5f*x;
union { float x; int i; } ix;
ix.x = x;
ix.i = 0x5f3759df - (ix.i >> 1);
x = ix.x;
x *= 1.5f - xhalf * x * x;
return x;

}

The point is that pointer-based type punning isn't really allowed by the language definition. The optimizer can take advantage of that to emit simpler code that, in this case, produces the wrong answer. Using a union short-circuits that kind of optimization.

This isn't to say any particular Gcc produces wrong answers with the code as written, but if you complained about one that did, they would just laugh at you and (if they liked you enough) tell you to rewrite it like the above instead.