News for hackers. Stuff that matters.
Re:Magical Square Root Implementation In Quake III by Carmack by valarauca1 on Friday February 21, 2014 @09:54AM (#7277197)
Horrible article.

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.

Re:Magical Square Root Implementation In Quake III by Carmack by ColinWright on Friday February 21, 2014 @09:56AM (#7277210)
In case this doesn't get many up votes, and not much discussion, it's worth understanding that this story has been submitted and discussed many, many, many times in the past. It's a wonderful hack, using techniques and skills of which the vast majority of programmers these days have no experience.

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.

Re:Magical Square Root Implementation In Quake III by Carmack by cwyers on Friday February 21, 2014 @10:10AM (#7277263)
Here's a much better article on the same topic:

http://www.beyond3d.com/content/articles/8

Re:Magical Square Root Implementation In Quake III by Carmack by rys on Friday February 21, 2014 @10:49AM (#7277479)
Crikey, over 7 years since I did the investigation (basic email, didn't try that hard) for that article. Time flies!
Re:Magical Square Root Implementation In Quake III by Carmack by theophrastus on Friday February 21, 2014 @11:06AM (#7277555)
It ought to be pointed out that this method (and many others even more cunning) are detailed in the delightful tome "Hacker's Delight" (ISBN 978-0-201-91465-8) by Henry S. Warren

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."

Re:Magical Square Root Implementation In Quake III by Carmack by krisdol on Saturday February 22, 2014 @01:21AM (#7281156)
I don't know why, but I'm supremely bothered by the author getting the name of Carmack's company wrong so many times. It's "Id" (or "id") Software, not "ID" Software. It's not pronounced "eye dee".
Re:Magical Square Root Implementation In Quake III by Carmack by rcfox on Friday February 21, 2014 @11:11AM (#7277581)
I wish the myriad articles about this interesting hack would bother to mention that it relies on undefined behaviour. Any time you find yourself doing this:

    *(foo*)
you're probably breaking the strict aliasing rule.
[deleted]
Re:Magical Square Root Implementation In Quake III by Carmack by figglesonrails on Friday February 21, 2014 @11:31AM (#7277703)
FWIW, memcpy(&anInt, &aFloat, sizeof(int)) achieves the same thing, is not turned in a real call to memcpy(), and doesn't not break the strict aliasing rule, and does not cause incorrect code to be generated with using `gcc -fstrict-aliasing`.
Re:Magical Square Root Implementation In Quake III by Carmack by deletes on Friday February 21, 2014 @12:35PM (#7278113)
The behavior is defined, if you disable the rule or your compiler doesn't follow it.
Re:Magical Square Root Implementation In Quake III by Carmack by rcfox on Friday February 21, 2014 @12:54PM (#7278253)
That's the opposite of "defined", in the context of a language discussion.
Re:Magical Square Root Implementation In Quake III by Carmack by deletes on Friday February 21, 2014 @01:02PM (#7278307)
It is a good thing that actual results rely on the compiler implementation, not the language.
Re:Magical Square Root Implementation In Quake III by Carmack by rcfox on Friday February 21, 2014 @01:17PM (#7278413)
Sure, your code will work today, with your compiler. But will it work tomorrow? Or what if your client wants to compile it on their machine, in a different operating system, with a compiler that you've never tried?
Re:Magical Square Root Implementation In Quake III by Carmack by deletes on Friday February 21, 2014 @01:23PM (#7278448)
Readme, documentation, makefile(??)
Re:Magical Square Root Implementation In Quake III by Carmack by boroadlkjq on Friday February 21, 2014 @11:11AM (#7277586)
Are there other weird number hacks like this one?
Re:Magical Square Root Implementation In Quake III by Carmack by matwood on Friday February 21, 2014 @11:22AM (#7277648)
Look at the hashCode() implementations in http://grepcode.com/file/repository.grepcode.com/java/root/j...

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;
    }
Re:Magical Square Root Implementation In Quake III by Carmack by snotrockets on Friday February 21, 2014 @01:45PM (#7278580)
Why is this weird? It's the textbook method for doing hashes.
Re:Magical Square Root Implementation In Quake III by Carmack by matwood on Friday February 21, 2014 @05:15PM (#7279822)
It is textbook, but the poster asked for seemingly random numbers in code. Based on all the places the invsqrt method has popped up, it also was a textbook method for doing it quickly.