Answer to C game Programming Puzzle

In the C Programming Puzzle, commenters correctly spotted that it was a square root function albeit rather mysterious in how it works. To stop anyone finding it easily by searching on the web I factorized 0x5f3759df ( 1597463007₁₀ ) into 21*76069667₁₀. If you search for 0x5f3759df, you'll find plenty of references on the web.

This code was used in Quake III to return the inverse square root of a float. I inverted the value to return the square root. The algorithm was about 4 x faster than floating point square roots back in the early 90s when it was devised. It uses the Babylonian method (also known as Newton's method) to get the square root of a number N. It's really simple, you start with a guess. Say we want the square root of 49 and we guess 5. The formula is guess = (guess + n/guess)/2. So the next guess = (5 + 49/5)/2 = 7.4. then the next guess = (7.4 + 49/7.4 ) / 2 = 7.0108. It is rapidly converging on 7 the real answer.

The genius behind the code I showed you is the line 0x5f3759df - ( c >> 1 ); (as it originally was before I obfuscated it!). This makes such a good guess that the whole algorithm comes up with a pretty decent stab in one iteration. It also does float <> int conversion using pointers which is definitely not too portable! This paper (pdf link) is a look by a mathematician Chris Lomont at Fast Inverse Square roots and shows where the magic number 0x5f3759df came from. Generally programming isn't quite this mathematical but sometimes...