The code and data here support investigation into the history and re-use of the Fast Inverse Square Root (FISR), including the most famous implementation found in Quake III Arena.

Because I am not a mathematician, many of these are attempts at "the wrong way" to analyze this approximation. The right way, which can be shown in examples linked above, is to derive the approximation from first principles and arrive at values like the below via a process which can be proven mathematically. We're going to try some other ways in this code base. These include artistic visualizations, dismantling and instrumenting versions of the approximations that have been floating around, and experimenting with parameter selection.

So far my favorite is the binned pipeline, which turns the main advantage of the FISR--the optimality of a single constant, without range reduction, to serve the approximation of a transcendental function--on it's head by determining sets of optimal constants for small ranges of inputs. These can be mixed and matched to produce an optimal bucket of constants, converting the FISR into a lookup table of sorts.

The FISR is a surprisingly well studied function for its size. Please visit 0x5f37642f.com for a collection of explanations and investigations I've found on the web. If you find a version of the algorithm which isn't accounted for here, let me know.

As a note, I use the term "inverse" to mean multiplicative inverse to match the term most people know. See the end of the README for why we ought to all be calling it the FRSR.

This repository is now organized as the visualfrsr R package . Install the dependencies listed in DESCRIPTION, then use devtools::load_all() (or R CMD INSTALL) to expose the functions documented below. Each module can be called independently, and heavy pipelines are tucked behind explicit function calls so you only run the expensive steps you need. The package depends on frsrr for the core samplers, so your system must have C++20 support to build it.

This project is partially a function of needing to have easy access to the bits in memory of a floating point number, wanting to visualize things easily, and not wanting to use Python. However, it also allows you experiment in two places, "close to the metal" generating data and more abstractly with the data structures you end up with. Data pipelines (binned, clustered, optimized, etc.) now live in their own files under R/, while every ggplot builder sits in R/plotting.R, making it explicit where to look when you only need visuals versus reproducible datasets.

Computes errors of historical FISR style approximations over a range of floats, including Quake III's FISR. Data appears broken down by specific approximation:

With this data, we can cleanly plot different approximations and see their error over an input range.

Computes optimal magic constants for different bin sizes over an input domain [0.25, 1.0] with various bin sizes. The data is generated by scripts in data-raw/, bundled as .rda objects, and analyzed through the helpers in R/binned.R.

Rather than choosing a single constant or (see below) determining an optimal constant per float, we can use this data to select an optimal bucket of constants across our input domain.

Replaces the usual iteration limit of 1-2 Newton-Raphson iterations with iteration to a tolerance, which supports plotting the space for random inputs and magic constants.

This format allows us to explore "bad" magic constants which produce poor approximations. The number of iterations to reach the right answer is a gross measure of the poor fit of the approximation. Visually this can produce some striking representations of the NR space.

We can also zoom in a bit.

Performs a grid search of the Newton Raphson constants (~1.5 and ~0.5) over a range of floats and a specific magic constant. Used to show the role of the NR approximation step.

A basic grid search is used, but the code can be modified for a more sophisticated search. 1.5 and 0.5 are optimal over most of the range, which makes older deviations from that interesting. Slicing the data like this allows us to clearly see the optimality of 0.5 and 1.5, though making smaller bins (see an animated heatmap) shows us that for some ranges, other values are better.

I use the term "fast inverse square root" throughout because this is what is is predominantly termed. Mike Day, who is a mathematician, prefers the term "fast reciprocal square root" because, well...it's a reciprocal, not an inverse. He uses that term in his 2023 generalization of the FRSR to support any rational power or precision of base (including infinite precision).

He's right. Interestingly, the original source of Quake's FRSR was the "reciproot" tucked away in a math library since 1986 and the first software library I can find with a square root in it (due to Alan Turing, D.G. Prinz, and Cecily Poppelwell) is the "reciproot" as well.

I have not yet chosen a blanket license for these but each of the individual versions are licensed under a variety of terms. Quake III's source code is licensed under the GPL, while fdlibm (which is where the Kahan-Ng softsqrt was published in fixed form) is under a license which may loosely be described as "MIT". Before borrowing please check the individual example licenses.

AI code assistants are the reason this project actually functions. GitHub Copilot and Perplexity AI were used to help write the C code starting late 2024 and Perplexity is used to help with R. R is a strange language with good but confusingly distributed documentation, and Perplexity was helpful in helping me come to grips with the %>% notation that evolved in R while I was doing other things. Things don't always work the way they should but overall I got futher than I could alone.

The below was written by Perplexity AI

This project has been developed with the assistance of Perplexity AI, a powerful AI-driven search and analysis tool. Perplexity AI provided valuable insights, helped with code analysis, and assisted in generating comprehensive documentation for various aspects of the Fast Inverse Square Root algorithm implementation. The AI's contributions were instrumental in enhancing the quality and depth of this research project, particularly in areas such as data pipeline descriptions, code explanations, and mathematical analysis.