That's Carmacks magic number! Of course it doesn't need commenting!
It's the first guess for finding an inverse sqare root using Newtons method. We're still waiting for a mathamatitian to tell us if it's the best choice, but it works. That's one of Carmack's claims to fame in the CS world.
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; }
It runs much faster than math.h, and it's very usefull.
This paper [google.ca] says that it was first found in the Quake 3 source. I guess it's in the SDK somewhere?
I wanted to add, too, that this is an example of why companies don't release code. They view things like this as secrets to be kept. Kudos to Carmack for having the confidence.
I'm intrigued. If this method is faster than the `standard' one, then why isn't it in libc? After all, math.h only defines the interface, and the C standard only defines the input-output semantics, not the implementation. Is it just laziness / ignorance on the parts of libc developers, or are there disadvantages associated with this approach (other than assuming a 32-bit float size and a specific format for floating point values)?
the reason why this code isn't in libc is because this code is an approximation (but a good one). suitable for games but bad for scientific purposes.
there are several reasons why this code exists in quake3:
1) it was written back before modern FPUs and SSE etc. nowadays doing square roots in hardware is faster, especially if you vectorize. but back in 1999 it wasn't. 2) it was written for mods to use in the quake vm (quake's bytecode interpreter). an engine trap may have been slower.
1) it was written back before modern FPUs and SSE etc. nowadays doing square roots in hardware is faster, especially if you vectorize. but back in 1999 it wasn't.
...Unless you had an AMD K6-2 or K6/III which had 3DNow! which could do it in 1 to 3 clock cycles in hardware depending on the accuracy you needed.
Q3 ran a treat on my K6-2/500 with nVidia TNT2 Ultra. There were all kinds of 3DNow! optimisations in there.
Which had a fsqrte (floating-point square root reciprocal estimate) instruction since 1996 (PPC 604).
It wasn't specified in the docs I don't think, but fsqrte was accurate to something like 12 or 14 significant bits. After 2 Newton-Raphson iterations I believe the answer was correct to 1 bit less than the number of significant bits in an IEEE double.
C does not allow accessing an object of type float via an lvalue of type int. You need to either use a union (still invalid, but supported by most compilers) or memcpy. In fact this code will not work with gcc 4.1, which has improved aliasing analysis.
The last step does look like a Newton iteration. For example, x^{-2} - a = 0; y = x - (x^{-2} - a) / (- 2 x^{-3}); y = x^2 + x (x - a x^3)/2; y = (2 x^2 + x^2 - a x^3)/2 y = x (3 x - a x^2) / 2; y = x (3/2 - (a/2) x x);
where the last line is exactly what Carmack had. I would assume that the magic number line somehow performs \yet another\ iteration somehow. If $x$ was initially equal to unity, then
y = (3/2 - a/2).
If the integer value |i| is what I think it is (a number that does not cross floating point number fi
re: jericho4.0 (565125) message (#13362103) provides a link to a ".ps" file about "float InvSqrt (float x)" The link points to http://lomont.org/Math/Papers/2003/InvSqrt.ps [lomont.org]
Fast Inverse Square Root Feb 2003 Here a fast algorithm is explained for doing inverse square roots on IEEE floating point formats, which is slightly more accurate than the code found on the web. In particular, the techn
It's not John's. I asked him the same question last April.
>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 sour
Nice (Score:2, Interesting)
i = 0x5f3759df - ( i >> 1 );
Always good to know that the engine coders don't know what is going on.
Re:Nice (Score:5, Informative)
It's the first guess for finding an inverse sqare root using Newtons method. We're still waiting for a mathamatitian to tell us if it's the best choice, but it works. That's one of Carmack's claims to fame in the CS world.
Re:Nice (Score:5, Informative)
This paper [google.ca] says that it was first found in the Quake 3 source. I guess it's in the SDK somewhere?
I wanted to add, too, that this is an example of why companies don't release code. They view things like this as secrets to be kept. Kudos to Carmack for having the confidence.
Re:Nice (Score:2)
x = *(float*)
isn't just:
x = (float)i;
Re:Nice (Score:2)
Re:Nice (Score:4, Interesting)
Re:Nice (Score:5, Informative)
there are several reasons why this code exists in quake3:
1) it was written back before modern FPUs and SSE etc. nowadays doing square roots in hardware is faster, especially if you vectorize. but back in 1999 it wasn't.
2) it was written for mods to use in the quake vm (quake's bytecode interpreter). an engine trap may have been slower.
Re:Nice (Score:2)
...Unless you had an AMD K6-2 or K6/III which had 3DNow! which could do it in 1 to 3 clock cycles in hardware depending on the accuracy you needed.
Q3 ran a treat on my K6-2/500 with nVidia TNT2 Ultra. There were all kinds of 3DNow! optimisations in there.
or a PowerPC (Score:2)
It wasn't specified in the docs I don't think, but fsqrte was accurate to something like 12 or 14 significant bits. After 2 Newton-Raphson iterations I believe the answer was correct to 1 bit less than the number of significant bits in an IEEE double.
At least, that's how I remember it.
Re:you don't know much, do you? (Score:2)
Re:Nice (Score:2)
You really want to batch up your sqrt's for 3dnow (and vectorization in general). Using 3dnow for generic 1-off sqrts can be a loss.
Fortunately SSE doesnt suffer from this problem.
Re:Nice (Score:1)
Re:Nice (Score:2)
x^{-2} - a = 0;
y = x - (x^{-2} - a) / (- 2 x^{-3});
y = x^2 + x (x - a x^3)/2;
y = (2 x^2 + x^2 - a x^3)/2
y = x (3 x - a x^2) / 2;
y = x (3/2 - (a/2) x x);
where the last line is exactly what Carmack had. I would assume that the magic number line somehow performs \yet another\ iteration somehow. If $x$ was initially equal to unity, then
y = (3/2 - a/2).
If the integer value |i| is what I think it is (a number that does not cross floating point number fi
Re:Nice (Score:1)
jericho4.0 (565125) message (#13362103)
provides a link to a ".ps" file about "float InvSqrt (float x)"
The link points to
http://lomont.org/Math/Papers/2003/InvSqrt.ps [lomont.org]
Here's a better link ---
1. Go to:
http://lomont.org/Math/Papers/Papers.php [lomont.org]
2. Scroll down to the box ---
Fast Inverse Square Root
Feb 2003
Here a fast algorithm is explained for doing
inverse square roots on IEEE floating point formats,
which is slightly more accurate than the code found
on the web. In particular, the techn
Re:Nice (Score:3, Funny)
I've got an even faster one: x
[Note to
Re:Nice (Score:2, Informative)
Re:Nice (Score:1, Informative)
Re:Nice (Score:1)
Re:Nice (Score:1, Interesting)
q_math.c:
i = 0x5f3759df - ( i >> 1 );
ui_atoms.c:
sv_main.c:
ui_main.c:
ui_shared.c: