Řrřola (a famous demoscene coder [1]) found a far better constant than the original (a 2.7-fold accuracy improvement) by using an optimisation algorithm over all three constants present in the original inverse square hack.<p>His algorithm and the result (along with a plot of relative error) can be found on his blog [2].<p>[1]: See, for example, this 256-byte raycaster <a href="https://www.youtube.com/watch?v=R35UuntQQF8" rel="nofollow">https://www.youtube.com/watch?v=R35UuntQQF8</a><p>[2]: <a href="http://rrrola.wz.cz/inv_sqrt.html" rel="nofollow">http://rrrola.wz.cz/inv_sqrt.html</a>
There is an amazing, easy to use peice of software for doing stuff like this called Eureqa (<a href="http://www.nutonian.com/products/eureqa/" rel="nofollow">http://www.nutonian.com/products/eureqa/</a>). I've used it to find approximations for a lot of different functions.
This reminds of another trick on the C64 to multiply two 8 Bit numbers
a*b = [ ((a+b)/2)^2 - ((a-b)/2)^2 ]<p>more or less:
one 8 bit additon, one 8 bit subtraction, two table lookups for the squares and one 16 bit subtraction.
Hacker's Delight [1][2] is an amazing book dedicated to discussing about all kinds of bit hacking, including fast integer square root, cube root calculation.<p>[1]: <a href="http://www.hackersdelight.org/" rel="nofollow">http://www.hackersdelight.org/</a><p>[2]: <a href="http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/dp/0321842685" rel="nofollow">http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/d...</a>
Shameless plug some of you might like to read: <a href="http://www.flipcode.com/tpractice/" rel="nofollow">http://www.flipcode.com/tpractice/</a><p>(I used to be really into game programming when I was in my teens.)
With fast native code its more than practical to search the entire space of floating point numbers and guarantee that you find the optimal magic number:<p><a href="http://jheriko-rtw.blogspot.co.uk/2009/04/understanding-and-improving-fast.html" rel="nofollow">http://jheriko-rtw.blogspot.co.uk/2009/04/understanding-and-...</a><p>As already mentioned in another comment it has been taken further by Řrřola who has optimised a version with the newton step including the constants involved in that.<p><a href="http://rrrola.wz.cz/inv_sqrt.html" rel="nofollow">http://rrrola.wz.cz/inv_sqrt.html</a>
For a moment I thought this was a way to workaround any patents with this hack, by rediscovering the hack dynamically; but I could be remembering a different patented technique.
Oh, I thought this gonna be like regex golf:<p><a href="http://xkcd.com/1313/" rel="nofollow">http://xkcd.com/1313/</a><p>Misleading title.