xkcd: the magic of 0x5f375a86

Just the urls, ma'am.
Post Reply
VLSmooth
Tenth Dan Procrastinator
Posts: 3055
Joined: Fri Jul 18, 2003 3:02 am
Location: Varies
Contact:

xkcd: the magic of 0x5f375a86

Post by VLSmooth »

http://xkcd.com/664/

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">
Google Search for "0x5f375a86" (link)

Fast Inverse Square Root - Chris Lomont (2003 Math Paper, pdf)
(note, he starts with 0x5f3759df then mentions 0x5f375a86 on page 10/12)
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?
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).

Edit: In retrospect, I'm might have seen a similar approach for sqrt() in production code that's over 20 years old...

Post Reply