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).<p>If this was a universally effective optimization with no potential downside, it would already be built in to your standard math library...
Also see:
<a href="http://en.wikipedia.org/wiki/Fast_inverse_square_root" rel="nofollow">http://en.wikipedia.org/wiki/Fast_inverse_square_root</a><p>And for more analysis and improvements see those papers:<p><a href="http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf" rel="nofollow">http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf</a><p><a href="http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdf" rel="nofollow">http://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Roo...</a><p><a href="http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf" rel="nofollow">http://www.geometrictools.com/Documentation/FastInverseSqrt....</a>
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.
Obligatory XKCD reference:<p><a href="http://xkcd.com/664/" rel="nofollow">http://xkcd.com/664/</a><p>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.
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.
The most useful modern-day knowledge you could gain from this is here: <a href="http://www.sosmath.com/calculus/diff/der07/der07.html" rel="nofollow">http://www.sosmath.com/calculus/diff/der07/der07.html</a><p>(Newton-Raphson Method)
Relevant link for those who want to know more about who came up with the magic number. <a href="http://www.beyond3d.com/content/articles/15/" rel="nofollow">http://www.beyond3d.com/content/articles/15/</a>
Awesome writeup, thanks!<p>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.<p><a href="http://marathon.svn.sourceforge.net/viewvc/marathon/branches/aleph-source/Source_Files/Misc/world.cpp?revision=3&view=markup" rel="nofollow">http://marathon.svn.sourceforge.net/viewvc/marathon/branches...</a>
(look for isqrt())<p>There's a great explanation in the comments.<p>This code was most likely written by Jason, probably around '93-'94.
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.