If anyone wants a fast atan2 that I wrote a while ago (2007), for making a microcontroller navigate, it's at <a href="http://robots-everywhere.com/portfolio/math/" rel="nofollow">http://robots-everywhere.com/portfolio/math/</a>
Tl;DR :<p>The fast inverse square root is based on the fact that the integer representation of a floating point number is a rough approximation of its logarithm.<p>So convert floating point to its integer representation. So now you have its approximate logarithm. Now take half of that and improve that with some Newton raphson.
I'm really impressed by the generalization to other powers, including the regular square root. It's the first time I've seen that hack (actually even the author mentions he found nothing on google). I think I could definitely have used that when I needed to compute square roots of fixedpoint numbers with no HW support, it looks very significantly faster than the iterative "by digit" method.
There is also a Wikipedia page for this:<p><a href="http://en.wikipedia.org/wiki/Fast_inverse_square_root" rel="nofollow">http://en.wikipedia.org/wiki/Fast_inverse_square_root</a>
I may be going on rampage here but "<i>It does contain a fair bit of math</i>" really grinds my gears!<p>Of course it does, it is about square roots and inversions.<p>In most of the cases, in order to optimize an algorithm or solve a problem, mathematics will do it for you, and that ranges from simple arithmetic properties to base changing theorems in linear algebra.<p>You just can not tackle such subjects without expecting it to <i>contain a fair bit of math</i> .