Book contents
Contents
raw Math
RAW Book Algorithms Numerical Methods

Introduction to the Fast Inverse Square Root Algorithm

Robert Eisele

The Fast Inverse Square Root algorithm is one of the most famous numerical methods in computer science, gaining legendary status for its crucial role in real-time 3D graphics. It was popularized by its use in the 1999 video game Quake III Arena, where it was employed to perform rapid vector normalization.

What is the Fast Inverse Square Root Algorithm?

The Fast Inverse Square Root algorithm provides an efficient method to compute \( \frac{1}{\sqrt{x}} \), a calculation that is typically resource-intensive. By combining bitwise manipulations with a refinement step using Newton’s method, the algorithm achieves a fast and remarkably accurate approximation.

The Importance of Inverse Square Root in 3D Graphics

In 3D graphics, vector normalization is essential. It involves scaling a vector so that its magnitude is 1, which is critical for lighting calculations, reflections, and geometric operations. Normalization is achieved by dividing each component of a vector by its length:

\[ \hat{\mathbf{v}} = \frac{\mathbf{v}}{\|\mathbf{v}\|} = \mathbf{v} \times \frac{1}{\sqrt{v_x^2 + v_y^2 + v_z^2}} \]

where the Fast Inverse Square Root algorithm is used to quickly compute \( \frac{1}{\sqrt{x}} \) with \(x=v_x^2 + v_y^2 + v_z^2\).

Newton’s Method and Bitwise Operations

The algorithm's efficiency stems from two key components: an initial approximation using bitwise operations and a refinement using Newton’s method.

Newton’s Method

To find \( y=\frac{1}{\sqrt{x}} \Leftrightarrow \frac{1}{y^2} - x = 0 \), we reformulate the problem as finding the root of the function:

\[ f(y) = \frac{1}{y^2} - x \]

Using Newton’s method and the derivative \(f'(y) = -\frac{2}{y^3}\), the iterative formula for improving our guess \( y_n \) is:

\[ y_{n+1} = y_n - \frac{f(y_n)}{f'(y_n)} = y_n \left(\frac{3}{2} - \frac{x y_n^2}{2}\right) \]

This formula quickly converges to the true value of \( \frac{1}{\sqrt{x}} \), especially when the initial guess \( y_0 \) is close to the actual solution.

Initial Approximation and Floating-Point Representation

The algorithm starts with an initial guess \( y_0 \), derived from the floating-point representation of \( x \) based on the IEEE 754 standard.

Floating-Point Representation

Encoding a non-zero real number \(x\) as a single precision float, the first step is to write \(x\) as a normalized binary number:

\[x = \pm 1.b_1 b_2 b_3... \cdot 2^{e}\]

with \(b_1 b_2 b_3...\) being the binary digits of the significand and \(e\) being the integer exponent. Since the leading 1 bit is always 1, it is not stored and therefore a single-precision floating-point number \( x \) can be expressed as:

\[ x = \pm 2^e \cdot (1 + m) \]

Here, \( m \) is the mantissa (with \( m \in [0, 1) \)).

Now the floating-point number \(x\) is stored as a 32-bit integer, comprising:

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
\(S\) \(E\) \(E\) \(E\) \(E\) \(E\) \(E\) \(E\) \(E\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\) \(M\)

The Magic Number and Algorithm Derivation

The goal is still to calculate \(y=\frac{1}{\sqrt{x}}\). When we take the logarithm on both sides we get

\[\log_b(y)=\log_b\left(\frac{1}{\sqrt{x}}\right)=\log_b\left(x^{-\frac{1}{2}}\right)=-\frac{1}{2}\log_b(x)\]

And applying it with \(b=2\) to the floating point representation of \(x = \pm 2^e \cdot (1 + m)\) by ignoring the negative numbers (since we can't calculate the negative square root) we have:

\[\log_2(x)=e+\log_2(1+m)\]

This demonstrates that aliasing a float32 to an integer provides a rough approximation of its logarithm in base two. Since \( m \in [0,1) \), we can approximate \( \log_2(x) \) as \( m + \mu \), where \( \mu \) is a free parameter. For instance, setting \( \mu = 0 \) gives exact results at the endpoints of the interval, while \( \mu = \frac{1}{2} - \frac{1 + \ln(\ln(2))}{2 \ln(2)} \approx 0.0430357 \) minimizes the worst-case error of this standalone approximation in the uniform norm sense. That value would give the integer constant 0x5f37bcb6. The constant 0x5f3759df instead corresponds to \(\mu\approx0.0450466\), which works better for the final estimate after one Newton step; how the original authors selected it is not documented. Therefore

\[\log_2(x) = e_x + m_x + \mu\]

Now saying that \(I\) is an integer, representing the bit pattern of the floating point number, we get

\[\begin{array}{rl} I &= 2^{23}\cdot E + M\\ &= 2^{23}\cdot(e+B+m)\\ &= 2^{23}\cdot(e+m+\mu+B-\mu)\\ &\approx 2^{23}\cdot\log_2(x) + 2^{23}\cdot(B-\mu) \end{array}\]

From which follows that we can approximate \(\log_2(x)\) with the bit representation of a number, shifted by some constants

\[ \log_2(x) \approx \frac{I}{2^{23}} - (B - \mu) \]

Using the approximation of \(\log_2(x)\) for the inverse square root yields

\[\begin{array}{rrl} &y &= \frac{1}{\sqrt x}\\ \Leftrightarrow& \log_2(y) &= -\frac{1}{2}\log_2(x)\\ \Rightarrow& \frac{I_y}{2^{23}} - (B-\mu) &\approx -\frac{1}{2}\left(\frac{I_x}{2^{23}} - (B-\mu)\right)\\ \Leftrightarrow& I_y &\approx \underbrace{\frac{3}{2}\cdot 2^{23}\cdot(B-\mu)}_{=\text{0x5f3759df}} - \underbrace{\frac{1}{2}}_{i\text{>>}1}\cdot I_x \end{array}\]

So the magic number 0x5f3759df that is found in the original source code used to compute the initial guess is basically the first part of the equation with \(B=127\) and \(\mu\approx 0.0450466\) and the division by two is implemented as a right shift by one, leading to

i = 0x5f3759df - (i >> 1)

After exhaustively testing 32-bit IEEE-754 floats, Chris Lomont showed that 0x5F375A86 is the best constant he found, slightly reducing the maximum relative error compared to 0x5F3759DF (≈0.175124% vs. ≈0.175228%) when using one Newton iteration [Lomont].

An Alternative Derivation: Fitting a Line to the Curve

The magic constant can also be motivated without going through logarithms at all, by fitting a line directly to the function that needs to be approximated. Writing \(x=2^e\cdot(1+m)\) as before, the inverse square root is

\[ \frac{1}{\sqrt{x}} = 2^{-e/2}\cdot\frac{1}{\sqrt{1+m}} \]

so everything comes down to approximating \(G(m)=\frac{1}{\sqrt{1+m}}\) for \(m\in[0,1)\). Since \(G\) is convex with \(G(0)=1\) and \(G'(0)=-\frac{1}{2}\), its tangent line at \(m=0\),

\[ T(m) = 1 - \frac{m}{2} \]

touches \(G\) only at \(m=0\) and lies below it everywhere else, with the gap widening toward \(m=1\). A line that cuts through the graph instead of merely touching it balances the error over the whole interval much better. The line used in the original code,

\[ L(m) = 0.966215 - \frac{m}{4} \]

has half the slope of \(T(m)\) and produces a noticeably smaller worst-case error, as the comparison below shows.

\(G(m)=1/\sqrt{1+m}\) (black) together with the tangent \(T(m)\) (blue, dashed) and the flatter line \(L(m)\) (red) actually used in the code. \(T(m)\) only touches \(G\) at \(m=0\), while \(L(m)\) cuts through the curve and keeps the worst-case gap much smaller across the whole interval.

Multiplying \(L(m)\) through by two puts it into normalized floating-point form,

\[ L(m) = \frac{1.93243 - m/2}{2} \]

The rounded decimal 0.966215 is not precise enough to determine the last bit: the binary32 value represented by \(\texttt{0x3f7759df}\) is 0.966215074..., which rounds to 0.966215. Accounting for the exponent bias when halving gives \(\texttt{0x3f7759df} + \texttt{0x1fc00000} = \texttt{0x5f3759df}\), since half of \(127\cdot2^{23}\) is \(\texttt{0x1fc00000}\). Why \(0.966215\) in particular was chosen is not fully documented; a natural guess, minimizing the integral squared error of \(C-\frac{m}{4}\) against \(G(m)\) over \([0,1]\), turns out not to reproduce this exact value either, so the constant was most likely tuned empirically.

Fast Inverse Square Root in C

The classic implementation made famous by Quake III Arena uses a bit-level initial estimate followed by Newton's method. On hardware of the time, this approach could be considerably faster than a native square-root operation. Across positive, normalized single-precision inputs, the initial estimate has a maximum relative error of about 3.44%; one Newton iteration reduces it to about 0.175%, and a second iteration to about 0.0005%. The historical C implementation is:

float Q_rsqrt(float number) {

  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * (long *) &y;                       // evil floating point bit level hacking
  i  = 0x5f3759df - (i >> 1);               // what the fuck?
  y  = *(float *) &i;
  y  = y * (threehalfs - (x2 * y * y));     // 1st iteration
  // y  = y * (threehalfs - (x2 * y * y));   // 2nd iteration, this can be removed

  return y;
}

The pointer cast in this historical snippet is not portable: on LP64 systems such as 64-bit Linux and macOS, long is 64 bits, not 32, and accessing a float through a long * violates C's strict-aliasing rules. A modern variant using Lomont's lower-error constant for one Newton iteration uses uint32_t and memcpy to move the object representation without aliasing. It assumes that float is a 32-bit IEEE-754 value:

#include <stdint.h>
#include <string.h>
float Q_rsqrt(float number) {
  uint32_t i;
  float y = number;
  memcpy(&i, &y, sizeof i);          // read the bits of the float as an integer
  i = 0x5F375A86 - (i >> 1);
  memcpy(&y, &i, sizeof y);
  return y * (1.5f - 0.5f * number * y * y);  // one Newton step
}

Fast Inverse Square Root in JavaScript

With some tricks of modern JavaScript, the Fast Inverse Square Root algorithm can also be implemented in JavaScript:

function Q_rsqrt(number) {

  const threehalfs = 1.5;
  const x2 = number * 0.5;

  const buffer = new ArrayBuffer(4);
  const view = new DataView(buffer);
  view.setFloat32(0, number, true);  // Store the float in little-endian format

  let i = view.getInt32(0, true);    // Get the 32-bit binary representation of the float
  i = 0x5f3759df - (i >> 1);

  view.setInt32(0, i, true);
  let y = view.getFloat32(0, true);   // Convert back to float

  y = y * (threehalfs - (x2 * y * y));   // 1st iteration

  return y;
}

Using this idea for Square Roots

If we try to use the same idea for ordinary square roots, we find that

\[\begin{array}{rrl} &y &= \sqrt x\\ \Leftrightarrow& \log_2(y) &= \frac{1}{2}\log_2(x)\\ \Rightarrow& \frac{I_y}{2^{23}} - (B-\mu) &\approx \frac{1}{2}\left(\frac{I_x}{2^{23}} - (B-\mu)\right)\\ \Leftrightarrow& I_y &\approx 532676608 - 4194304 \mu + \frac{I_x}{2} \end{array}\]

With \(\mu:= 0.0759\) a quite good sqrt approximation function is

union FloatLong {
  float x;
  uint32_t i;
};

float Q_sqrt(float x) {

  union FloatLong u;
  u.x = x;
  u.i = (532358260 + (u.i >> 1)) & 0x7fffffff; // Get initial y_0

  return (x / u.x + u.x) * 0.5; // Return after one Newton step
}