Magical Square Root Implementation In Quake III by Carmack
codemaestro.com
codemaestro.com
First the implementation solves for the 'Inverse Square Root', not the square root. [1] Secondly the algorithm's author isn't actually known but the earliest person it can be traced too is Gary Tarolli [1].
[1] https://en.wikipedia.org/wiki/Fast_inverse_square_root
It really bothers me when people write something and their own sources differ from what their writing let alone wikipedia.
It's worth reading, learning, and understanding, if only to be grateful that most of your life you'll never have to resort to such tricks. Sadly, that also means you'll never get the chance to experience the sheer joy of creating something like this.
Having said that, this article is actually really, really poor, and most of its value lies in the references provided by people in the comments. Many of the other submissions here on HN are much better.
on about page 481 or so:
"The Newton step is a standard Newton-Raphson calculation for the reciprocal square root function (see Appendix B). Simply repeating this step reduces the relative error to the range 0 to -0.0000047. The optimal constant for this is 0x5F37599E."
*(foo*)
For example:
public static int hashCode(double a[])
{
if (a == null) return 0;
int result = 1;
for (double element : a) {
long bits = Double.doubleToLongBits(element);
result = 31 * result + (int)(bits ^ (bits >>> 32));
}
return result;
}