6 ms·

Quake's Fast Inverse Square Root

107 points by pjin 15y ago

0x12 15y ago
http://news.ycombinator.com/item?id=419166 http://news.ycombinator.com/item?id=419166
ch0wn 15y ago
This is the kind of article I come to Hacker News for. A clever hack for a real-world problem with an excellent explanation.
- Radim 15y ago
  You might also be interested in the previous HN discussions of the same topic, then: http://news.ycombinator.com/item?id=896092 http://news.ycombinator.com/item?id=896092 (yes, this "trick" has been making rounds for a decade now; I predict another HN article within 6 months)
rogerallen 15y ago
Relevant link for those who want to know more about who came up with the magic number. http://www.beyond3d.com/content/articles/15/ http://www.beyond3d.com/content/articles/15/
mtklein 15y ago
Every time I read the headline for a fast algorithm for inverse square root I think "Well, yeah, you just multiply the input by itself. Can't get much faster to undo a square root than that." Silly me.
- pestaa 15y ago
  My native language isn't English, and I made the very same mistake like 50 times already. Sometimes I still forget what inverse means in math. I would instantly understand "reciprocal" though, which is the name I learnt for this operation.
  - feral 15y ago
    >Sometimes I still forget what inverse means in math. I think your interpretation is actually the more correct one, here. Squaring and square-rooting are the inverse of each other. They are really talking about calculating the reciprocal of the square root of X. They are calling it the 'inverse square root', but thats just them abusing terminology, which people do all the time, rightly or wrongly. But you weren't wrong to be initially confused by this abuse of terminology, and it doesn't have anything to do with your native language not being English.
    - alecbenzer 15y ago
      I thought the same thing. I guess the confusion comes from thinking of the inverse of the function square root instead of the multiplicative inverse of the value of the square root function. Technically I suppose the terminology is a bit hand-wavy, since you could have also been referring to the additive inverse, but I think it's fairly common to talk about "inverses" of members of a field and assume that people know you mean multiplicative inverses. But that's exactly what isn't a safe assumption here, since you could be thinking about a function (which seems like the more natural interpretation), as opposed to a number.
achille 15y ago
Also see: http://en.wikipedia.org/wiki/Fast_inverse_square_root http://en.wikipedia.org/wiki/Fast_inverse_square_root And for more analysis and improvements see those papers: http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Roo... http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf http://www.geometrictools.com/Documentation/FastInverseSqrt....
bermanoid 15y ago
This is a good thing to know about, but bear in mind that these days it's often slower than just using whatever built in square root you have access to. Especially beware in languages where you need to do something more than a cast to get the raw bits out of the floating point number, oftentimes that alone is enough to kill any performance gains you might otherwise see. Profile your code before and after, and make sure you've got an easy way to switch back if you realize that you've gone and made things slower (or worse, too inaccurate for your use case). If this was a universally effective optimization with no potential downside, it would already be built in to your standard math library...
- deleted 15y ago
  [deleted]
- jforman 15y ago
  This isn't a universally effective optimization. It's an exquisite optimization for when a little imprecision is tolerable. Micro-optimizations like this are rarely worth the increase in cognitive complexity of the code, but Quake had to do a lot of math in very little time on 1996 hardware, so I'll trust Carmack (whose programming skills are legendary if you aren't familiar with him).
  - deleted 15y ago
    [deleted]
  - lawnchair_larry 15y ago
    Carmack didn't write that code. It was written by Greg Walsh.
- Geee 15y ago
  It's an approximation, and thus does not comply with the IEEE floating-point standard. That is, numerical results of the operations should be correct up to the precision of the floating-point number. There's lots of optimizations possible with floating-point math if speed/energy-efficiency is prioritized over accuracy or standard compliance.
aw3c2 15y ago
Not Quake, but Quake 3. That's one and half generation of engines ahead.
palish 15y ago
The most useful modern-day knowledge you could gain from this is here: http://www.sosmath.com/calculus/diff/der07/der07.html http://www.sosmath.com/calculus/diff/der07/der07.html (Newton-Raphson Method)
psykotic 15y ago
Huh. The only really interesting part of the algorithm is the initial guess with the magic number, and he doesn't go into that part at all. Read Chris Lamont's paper if you care enough to want to understand it. The only downside to Lamont's paper is that it's a post mortem analysis rather than a pedagogical derivation. I worked out a step-by-step development of the algorithm last year, but I've never gotten around to writing it up in tutorial form.
thret 15y ago
Obligatory XKCD reference: http://xkcd.com/664/ http://xkcd.com/664/ Image text: Some engineer out there has solved P=NP and it's locked up in an electric eggbeater calibration routine. For every 0x5f375a86 we learn about, there are thousands we never see.
derwiki 15y ago
I love that this comes up regularly in this community. It's one of those things that everyone seems to discover at some point.
mathattack 15y ago
Which came first? Quake 3 or the papers? This defines how interesting it is. I've seen a lot of folks working through Quake's code lately. Hard to tell if they are originators or appliers, but either way it's much more interesting than reading bland examples from a book.
ajessup 15y ago
Awesome writeup, thanks! Came across something similar a couple of days ago while browsing the source code of Marathon (one of the early games of Jason Jones and Bungie, later of Halo fame). At the time, Bungie were the Mac equivalent of id software, and Jason Jones the equivalent of John Carmack. http://marathon.svn.sourceforge.net/viewvc/marathon/branches/aleph-source/Source_Files/Misc/world.cpp?revision=3&view=markup http://marathon.svn.sourceforge.net/viewvc/marathon/branches... (look for isqrt()) There's a great explanation in the comments. This code was most likely written by Jason, probably around '93-'94.

107 points by pjin 15y ago

0x12 15y ago

http://news.ycombinator.com/item?id=419166 http://news.ycombinator.com/item?id=419166

ch0wn 15y ago

This is the kind of article I come to Hacker News for. A clever hack for a real-world problem with an excellent explanation.

Radim 15y ago
You might also be interested in the previous HN discussions of the same topic, then: http://news.ycombinator.com/item?id=896092 http://news.ycombinator.com/item?id=896092 (yes, this "trick" has been making rounds for a decade now; I predict another HN article within 6 months)

rogerallen 15y ago

Relevant link for those who want to know more about who came up with the magic number. http://www.beyond3d.com/content/articles/15/ http://www.beyond3d.com/content/articles/15/

mtklein 15y ago

Every time I read the headline for a fast algorithm for inverse square root I think "Well, yeah, you just multiply the input by itself. Can't get much faster to undo a square root than that." Silly me.

pestaa 15y ago
My native language isn't English, and I made the very same mistake like 50 times already. Sometimes I still forget what inverse means in math. I would instantly understand "reciprocal" though, which is the name I learnt for this operation.
- feral 15y ago
  >Sometimes I still forget what inverse means in math. I think your interpretation is actually the more correct one, here. Squaring and square-rooting are the inverse of each other. They are really talking about calculating the reciprocal of the square root of X. They are calling it the 'inverse square root', but thats just them abusing terminology, which people do all the time, rightly or wrongly. But you weren't wrong to be initially confused by this abuse of terminology, and it doesn't have anything to do with your native language not being English.
  - alecbenzer 15y ago
    I thought the same thing. I guess the confusion comes from thinking of the inverse of the function square root instead of the multiplicative inverse of the value of the square root function. Technically I suppose the terminology is a bit hand-wavy, since you could have also been referring to the additive inverse, but I think it's fairly common to talk about "inverses" of members of a field and assume that people know you mean multiplicative inverses. But that's exactly what isn't a safe assumption here, since you could be thinking about a function (which seems like the more natural interpretation), as opposed to a number.

achille 15y ago

Also see: http://en.wikipedia.org/wiki/Fast_inverse_square_root http://en.wikipedia.org/wiki/Fast_inverse_square_root And for more analysis and improvements see those papers: http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Roo... http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf http://www.geometrictools.com/Documentation/FastInverseSqrt....

bermanoid 15y ago

This is a good thing to know about, but bear in mind that these days it's often slower than just using whatever built in square root you have access to. Especially beware in languages where you need to do something more than a cast to get the raw bits out of the floating point number, oftentimes that alone is enough to kill any performance gains you might otherwise see. Profile your code before and after, and make sure you've got an easy way to switch back if you realize that you've gone and made things slower (or worse, too inaccurate for your use case). If this was a universally effective optimization with no potential downside, it would already be built in to your standard math library...

deleted 15y ago
[deleted]
jforman 15y ago
This isn't a universally effective optimization. It's an exquisite optimization for when a little imprecision is tolerable. Micro-optimizations like this are rarely worth the increase in cognitive complexity of the code, but Quake had to do a lot of math in very little time on 1996 hardware, so I'll trust Carmack (whose programming skills are legendary if you aren't familiar with him).
- deleted 15y ago
  [deleted]
- lawnchair_larry 15y ago
  Carmack didn't write that code. It was written by Greg Walsh.
Geee 15y ago
It's an approximation, and thus does not comply with the IEEE floating-point standard. That is, numerical results of the operations should be correct up to the precision of the floating-point number. There's lots of optimizations possible with floating-point math if speed/energy-efficiency is prioritized over accuracy or standard compliance.

aw3c2 15y ago

Not Quake, but Quake 3. That's one and half generation of engines ahead.

palish 15y ago

The most useful modern-day knowledge you could gain from this is here: http://www.sosmath.com/calculus/diff/der07/der07.html http://www.sosmath.com/calculus/diff/der07/der07.html (Newton-Raphson Method)

psykotic 15y ago

Huh. The only really interesting part of the algorithm is the initial guess with the magic number, and he doesn't go into that part at all. Read Chris Lamont's paper if you care enough to want to understand it. The only downside to Lamont's paper is that it's a post mortem analysis rather than a pedagogical derivation. I worked out a step-by-step development of the algorithm last year, but I've never gotten around to writing it up in tutorial form.

thret 15y ago

Obligatory XKCD reference: http://xkcd.com/664/ http://xkcd.com/664/ Image text: Some engineer out there has solved P=NP and it's locked up in an electric eggbeater calibration routine. For every 0x5f375a86 we learn about, there are thousands we never see.

derwiki 15y ago

I love that this comes up regularly in this community. It's one of those things that everyone seems to discover at some point.

mathattack 15y ago

Which came first? Quake 3 or the papers? This defines how interesting it is. I've seen a lot of folks working through Quake's code lately. Hard to tell if they are originators or appliers, but either way it's much more interesting than reading bland examples from a book.

ajessup 15y ago

Awesome writeup, thanks! Came across something similar a couple of days ago while browsing the source code of Marathon (one of the early games of Jason Jones and Bungie, later of Halo fame). At the time, Bungie were the Mac equivalent of id software, and Jason Jones the equivalent of John Carmack. http://marathon.svn.sourceforge.net/viewvc/marathon/branches/aleph-source/Source_Files/Misc/world.cpp?revision=3&view=markup http://marathon.svn.sourceforge.net/viewvc/marathon/branches... (look for isqrt()) There's a great explanation in the comments. This code was most likely written by Jason, probably around '93-'94.