0x5F3759DF and the fast approximate square root

Tags: numerical-methods

First note that the inverse square root, \(x^{-\frac{1}{2}}\) can be expressed as follows:

\[\begin{align} & x^{-\frac{1}{2}} \\ = & 2^{log_{2} (x^{-\frac{1}{2}})} \\ = & 2^{-{\frac{1}{2}log_{2} x}} \label{b}\tag{Eq.1} \end{align}\]

Also note that when a float is cast to an int it is a piecewise linear approximation of a log function, therefore let us write a function:

\[\begin{align} & floatToInt(u) = A log_{2} u + B \\ \implies & log_{2} u = \frac{floatToInt(u) - B}{A} \label{a}\tag{Eq.2} \end{align}\]

and its inverse:

\[\begin{align} intToFloat(v) = 2^{(\frac{v - B}{A})} \label{c}\tag{Eq.3} \end{align}\]

where the constants \(A\) and \(B\) depend on the type of floating point used.

We can then substitute the expression in \(\ref{a}\) into \(\ref{b}\).

\[\begin{align} x^{-\frac{1}{2}} & = 2^{-\frac{1}{2}(\frac{floatToInt(x) - B}{A})} \\ & = 2^{\frac{-\frac{1}{2} floatToInt(x) + \frac{1}{2}B}{A}} \\ & = 2^{\frac{-\frac{1}{2} floatToInt(x) + \frac{1}{2}B + \frac{3}{2}B - \frac{3}{2}B}{A}} \\ & = 2^{\frac{-\frac{1}{2} floatToInt(x) + \frac{3}{2}B - B}{A}} \end{align}\]

Then we can use the substitution \(v = -\frac{1}{2} floatToInt(x) + \frac{3}{2}B\)

\[\begin{align} x^{-\frac{1}{2}} & = 2^{(\frac{v - B}{A})} \end{align}\]

Now we can substitute with \(\ref{c}\):

\[\begin{align} x^{-\frac{1}{2}} & = intToFloat(v) \\ & = intToFloat(-\frac{1}{2} floatToInt(x) + \frac{3}{2}B) \\ & = intToFloat(\frac{3}{2}B -\frac{1}{2} floatToInt(x)) \end{align}\]

For an IEEE 754 32-bit floating point number

\[\begin{align} A & = \text{0x00800000} \\ B & = \text{0x3F800000} \\ \implies \frac{3}{2}B & = \text{0x5F400000} \end{align}\]


\[\begin{align} x^{-\frac{1}{2}} = intToFloat(\text{0x5F400000} -\frac{1}{2} floatToInt(x)) \end{align}\]

The difference between 0x5F400000 and 0x5F3759DF is due to our use of a piecewise linear approximation of the log curve in this derivation. A piecewise linear approximation will either be the same or a slight underestimate. To maximise the accuracy we’d want an approximation that was in equal parts an over or underestimate, therefore 0x5F3759DF is the result of performing some sort of best fit.