18

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?

Improve this question
3
  • 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
    Commented Aug 31, 2017 at 12:53
  • 1
    Same question on StackOverflow but not any real good answers: stackoverflow.com/questions/1349542/…
    – user722
    Commented Aug 31, 2017 at 18:21
  • 2
    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
    Commented Sep 1, 2017 at 17:05

2 Answers 2

Reset to default
20

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.

Improve this answer
-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.

Improve this answer
4
  • 3
    I was more asking about the line commented /* Fast inverse square root */.
    – wizzwizz4 ♦
    Commented Aug 31, 2017 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 ♦
    Commented Aug 31, 2017 at 14:02
  • 2
    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 ♦
    Commented Aug 31, 2017 at 14:10
  • 4
    The question was about how the initial approximation was generated. Newton's Method is only applied after the initial approximation.
    – user722
    Commented Aug 31, 2017 at 18:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .