11

The fast inverse square root algorithm is probably best known for its use in Quake III Arena, the source code of which was released to the public a few years after its release. However, the algorithm was used much earlier than this - Wikipedia gives Gary Tarolli's implementation for the SGI Indigo as a possible earliest known use.

float fast_InvSqrt(float n) {
    union {float f; long l;} approx = n
    approx.l = 0x5f3759df - (approx.l >> 1); /* Fast inverse square root */
    approx.f = y * (1.5F - (0.5f * n * approx.f * approx.f)); /* Newton's method */
    return approx.f;
}

The Fast InvSqrt algorithm contains one or two iterations of Newton's method, but this question is asking mainly about the line approx.l = 0x5f3759df - (approx.l >> 1);.

Who first developed Fast InvSqrt()? Where did 0x5f3759df originally come from?

  • 2
    Checking Wiki will give an in depth description as well as information about early usage and development, including hints how the constant did evolve. --- P.S.: I wouldn't realy considere this a Retro Computing issue, as it's about a common algorithm still used and told in todays studies. – Raffzahn Aug 31 '17 at 12:53
  • 1
    Same question on StackOverflow but not any real good answers: stackoverflow.com/questions/1349542/… – Ross Ridge Aug 31 '17 at 18:21
  • 1
    The float number itself has exponent and mantissa. The operation could be seen as 1. exponent mangling as to calculate 1/sqrt(2^e) where e is the float exponent, 2. best linear approximation to 1/sqrt(m) where m is from 1 to 2 and is a mantissa from the float number. – lvd Sep 1 '17 at 17:05
12

As you mention, this algorithm was made famous by Quake III Arena; that implementation can now be found, preserved for posterity, in Software Heritage’s Archive.

Beyond3D published two articles by Rys Sommefeldt on exactly this topic in 2006 and 2007: part 1 and part 2. According to these, the fast inverse square root algorithm was invented in the late eighties by Greg Walsh, inspired by Cleve Moler. Greg was working at Ardent on the Titan graphics minicomputer, and came up with inverse square and cube root algorithms to help the computer live up to its performance claims. Cleve, one of the founders of MathWorks, and author of MatLab, was working with Greg at Ardent. Cleve had come across the basic idea behind the trick in code written by Velvel Kahan and K. C. Ng in 1986 at Berkeley.

From there, the algorithm came to Gary Tarolli’s attention; he was consulting for Kubota, the company funding Ardent at the time, and later went on to found 3Dfx. It appears Gary might have used the algorithm on SGI’s Indigo systems.

All this is also summarised in the Wikipedia article on the topic.

The code you list uses 0x5F3759DF, but Chris Lomont came to the conclusion that 0x5F375A86 provided more accurate results. The origin of the 0x5F3759DF value appears to be lost in the mists of time.

-1

Who developed the algorithm? That is in the comments of the code you have posted - Isaac Newton.

Newton's algorithm is a known mathematical iterative technique. To quote from Wolfram Alpha:


Newton's Iteration


This can be coded in a language like Mathematica (not exactly a RetroComputing language) using a simple construct such as:

Entity["MathWorld", "NewtonsIteration"]

The hex codes that you ask about are hard-coded representations of seed values into this algorithm.

  • 1
    I was more asking about the line commented /* Fast inverse square root */. – wizzwizz4 Aug 31 '17 at 13:59
  • 1
    @wizzwizz4: Yes, that is a coding trick to implement the algorithm. The 0x5f3759df would be a representation of the floating point seed values into the iteration. That's a common trick when trying to save memory. – Chenmunka Aug 31 '17 at 14:02
  • 1
    I don't understand what you mean by "seed values" - this is a way of generating an initial approximation that can then be used for Newton's method, but Newton's method is well known and (imo) not really a Retrocomputing topic. I'm much more interested in the history of Fast InvSqrt() than how the algorithm works, but a description of the algorithm is a bonus. To quote the question: "Who developed Fast InvSqrt()? Where did 0x5f3759df come from?" – wizzwizz4 Aug 31 '17 at 14:10
  • 2
    The question was about how the initial approximation was generated. Newton's Method is only applied after the initial approximation. – Ross Ridge Aug 31 '17 at 18:16
  • 5
    The core of the question is about the 0x5f3759df - (approx.l >> 1); line, and the fact that it gives such a good approximation that only one or two iterations of Newton's Method are needed to get an acceptable answer. Newton's Method is old, but the fast initial guess isn't. – Mark Aug 31 '17 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.