Code: Select all
<img src="http://imgs.xkcd.com/comics/academia_vs_business.png" title="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." alt="Academia vs. Business">
Fast Inverse Square Root - Chris Lomont (2003 Math Paper, pdf)
(note, he starts with 0x5f3759df then mentions 0x5f375a86 on page 10/12)
I'm feeling an odd case of deja vu (I probably read about this in the past and forgot about it); in any case, mind is (re)blown by the practical application of known concepts (namely the floating point specification and Newton approximation).Chris Lomont wrote:The interesting part was the constant 0x5f3759df: where did it
come from and why does the code work? Some quick testing in Visual
C++.NET [2] showed the code above to be roughly 4 times faster than
the naive (float)(1.0/sqrt(x)), and the maximum relative error
over all floating point numbers was 0.00175228, so the method seems
very useful. Three immediate questions were: 1) how does it work, 2)
can it be improved, and 3) what bit master designed such an incredible
hack?
Edit: In retrospect, I'm might have seen a similar approach for sqrt() in production code that's over 20 years old...