Cool blog post on the Fast Inverse Square Root

[Protonk]

Hi Francis!

I love the blog format. Thank you for writing about the FISR in 2024! You mention some of the history of the FISR, so I figured I'd let you know what else I've uncovered about it. I maintain a resource on the FISR at 0x5f37642f.com/ and I've collected pretty much everything I can find about the approximation. Not everything is on there, but most of the important pieces are.

The Wikipedia article has much of the story of how the approximation came to be, but it's not entirely clear in how it is worded. We know that Greg Walsh probably showed it to Gary Tarolli and it was Gary who used it at 3DFX, which is how it made its way to iD software. Cleve Moler found the idea for the technique from William Kahan (the "old man" of floating point) who showed the technique in an unpublished paper written with his grad student K-C Ng in 1986. This paper, which was also included in its entirety as a comment in fdlibm's square root code did something really cool. It took a double as an input and split it into an upper and lower 32 bit field. The upper field had the sign and exponents and some fraction bits and THAT was used to get a logarithmic approximation by converting it to an integer. You can see a breakdown of the Kahan-Ng code here--I don't include all the bit fiddling steps to get a correctly rounded result, but the core logic of the code is there.

It is likely that Moler (or Moler and Walsh) adopted this code, realized that it could apply not just to split doubles but to floats, and then they started experimenting with different restoring constants. We don't know for sure where the "magic" constant took shape, but my guess is before the code went to 3DFX, since it is the specific choice of constant which allows you to skip multiple rounds of Newton's method (and therefore give you a strong performance advantage). You can also see a 1997 article from Jim Blinn where he explains the process using a non-magic restoring content in Floating Point Tricks. Even though this was published in 1997, there's no indication that the code in Quake III had any relation to Blinn's article.

The 1986 paper wasn't the first time that this trick was shown in code. Noah Hellman, in a 2021 masters thesis, Mitchell-Based Approximate Operations on Floating-Point Numbers showed that the basic idea that a (positive, normal) floating point number offers a piecewise approximation of a logarithm if treated as an integer was first attested in print in 1962 with Computer Multiplication and Division Using Binary Logarithms! Interestingly, though Hellman asserts that Mitchell is a likely source of inspiration, Kahan was developing what became known as "Kahan's magic square root" at about the same time. It's possible that even in 1962 we had simultaneous discovery of this behavior.

I'm still working on putting the website together and I'm collecting blog posts and links about the FISR, so I'll be excited to add yours once that part of my site is up. Thanks again for writing this post!