I actually do know offhand that I use the Taylor series to calculate it, and that the Carmack method works by using a couple tricks of binary floating point format to do a really good starting point and then run the Taylor series through a single round of iteration. I've also implemented it myself before since library methods were too slow. This probably puts me in the top 0.001% of developers world wide in terms of what I happen to have memorized and from personal experience about square roots. However, I don't offhand remember the details at all and wouldn't pretend to. I would never use this an an interview question because it doesn't test for anything at all. 99% of candidates would have no clue regardless of skill level, and of the 1% who knew anything, most would be because they happened to study the right "interview tricks" site while cramming for the interview. So I still think these sorts of questions are absolutely terrible for the purpose of finding competent developers.
Fast inverse square root for computer graphics programming! [1] Popularized by leaked Quake III code (attributed to John Carmack), but dates back much further.
The key problem with inverse square root is the risk of having that code unmoored from a very well put together comment explaining the rationale for it, and perhaps a TODO in the backlog about re-evaluating when to get rid of it.
Without knowing that it's a fast inverse square root approximation using the Newton-Rhapson method with 1 iteration using some clever bit twiddling hacks and an initial guess chosen by experiment to be optimally efficient in terms of accuracy and especially for speed you can end up with a lot of problems. First, someone could look at it and spend a lot of time trying to figure out what it was doing before realizing what it did. Second, it could cause people to attempt to replace it without realizing the value of it, causing wasted effort. Third, it could cause people to try to improve it, spending time attempting to find a more optimal first guess, or adjusting the bit twiddling nature in some way. Fourth, and worst of all, it could develop a reputation as a bit of "deep magic" which shouldn't be touched because nobody knows exactly how it works, so nobody ever re-evaluates whether it's worth keeping. As it stands now it's obsolete code given that modern GPUs will perform the relevant calculation in hardware much faster.
Granted, in this specific case a lot of these problems are much diminished (since the company was small, the code and its rationale was well-known by the dev lead, and it's reasonably straightforward to reverse engineer the operation and rationale for the code with some investigation), however this might not be the case somewhere else with some other piece of comparatively magical code.
When you write a bit of WTF code that's actually worthwhile imagine that everyone that worked on the code is now dead and researchers are studying it, what information would those researchers want the most? Now put that in a comment.
P.S. Also, god help you if you happen to be lucky enough to have a chunk of poorly documented "deep magic" code that happens to have a defect in it.
Absolutely hilarious and amazingly magical method of algorithmically computing square roots. It right shifts a floating point number to essentially divide the exponent component by 2. Then it uses a weird magic number trick to get the correct result. Awesome random programming trivia.
Every time I read the headline for a fast algorithm for inverse square root I think "Well, yeah, you just multiply the input by itself. Can't get much faster to undo a square root than that." Silly me.
Cool. In the comments from that post, there's another article that traces that inverse square root implementation back even further - almost 20 years back at this point:
It's a shame you picked q3's fast inverse square root. It's not a great example as it turns out someone else implemented it in Quake 3 and someone else entirely devised the algorithm itself. Though you're right - he's a bit of a hero and deservedly so.
edit: however ... I've just read that article and it is actually the most in-depth and interesting analysis I've read on the subject so thanks!
We would also subject John Carmack to that technical monkey dance because we don't believe in free handouts.
reply