fast inverse square root
root-finding algorithm
≈ 15 min read
fast inverse square root. encyclopegia.org, snapshot fast-inverse-square-root-003937-99370e91c5f4b7af. /a/fast-inverse-square-root
Names in other languages
- Polskiszybka odwrotność pierwiastka kwadratowego
- Русскийбыстрый обратный квадратный корень
- Italianoradice quadrata inversa veloce
- Françaisracine carrée inverse rapide
- Englishfast inverse square root
- Српски0x5f3759df
- 한국어고속 역 제곱근
- 中文平方根倒数速算法
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
OpenArena, use the fast inverse square root code to compute angles of incidence and reflection. Fast inverse square root, sometimes referred to as or by the hexadecimal constant , is an algorithm that estimates 1/\sqrt{x} , the reciprocal (or multiplicative inverse) of the square root of a 32-bit floating-point number x in IEEE 754 floating-point format.
The algorithm is best known for its implementation in the 19991 video game Quake III Arena. With subsequent hardware advancements, especially the x86 SSE instruction rsqrtss , this algorithm is not generally the best choice for modern computers, though it remains an interesting historical example.
The algorithm accepts a 32-bit floating-point number as the input and stores a halved value for later use. Then, treating the bits representing the floating-point number as a 32-bit integer, a logical shift right by one bit is performed and the result subtracted from the number , which is a floating-point representation of an approximation of \sqrt{2^{127}} .
This results in an initial guess of the inverse square root of the input. Treating the bits again as a floating-point number, it runs one iteration of Newton's method, yielding a more precise approximation.
History
William Kahan and K.C. Ng at Berkeley wrote an unpublished paper in May 1986 describing how to calculate the square root using bit fiddling techniques followed by Newton iterations. In the late 1980s, Cleve Moler at Ardent Computer learned about this technique and passed it along to his coworker Greg Walsh.
Greg Walsh devised the now-famous constant and fast inverse square root algorithm. Gary Tarolli was consulting for Kubota, the company funding Ardent at the time, and likely brought the algorithm to 3dfx Interactive circa 1994. Jim Blinn demonstrated a simple approximation of the inverse square root in a 1997 column for IEEE Computer Graphics and Applications.
Reverse engineering of other contemporary 3D video games uncovered a variation of the algorithm in Activision's 1997 Interstate '76. Quake III Arena, a first-person shooter video game, was released in 1999 by id Software and used the algorithm. Brian Hook may have brought the algorithm from 3dfx to id Software.
A discussion of the code appeared on the Chinese developer forum CSDN in 2000, and Usenet and the gamedev.net forum spread the code widely in 2002 and 2003. Speculation arose as to who wrote the algorithm and how the constant was derived; some guessed John Carmack. Quake III s full source code was released at QuakeCon 20051, but provided no answers.
The authorship question was resolved in 2006 when Greg Walsh, the original author, contacted Beyond3D after their speculation gained popularity on Slashdot. In 2007 the algorithm was implemented in some dedicated hardware vertex shaders using field-programmable gate arrays (FPGA).
Motivation
s are used extensively in lighting and shading calculations, requiring the calculation of norms for vectors. A field of vectors normal to a surface is shown here. Computer graphics frequently uses inverse square roots for transform, clipping, lighting, and shading to compute angles of incidence and reflection.
Programs such as Quake III: Arena must perform a large number of these calculations every second to simulate lighting. In particular, the operation of scaling a vector to length 1 to produce a unit vector uses the inverse square root. Specifically, the length of the vector is determined by calculating its Euclidean norm: the square root of the sum of squares of the vector components.
When each component of the vector is divided by that length, the new vector will be a unit vector pointing in the same direction. In a 3D graphics program, all vectors are in three-dimensional space, so \boldsymbol v would be a vector (v_1, v_2, v_3) .
Then, \|\boldsymbol{v}\| = \sqrt{v_1^2+v_2^2+v_3^2} is the Euclidean norm of the vector, and the normalized (unit) vector is \begin{align} \boldsymbol{\hat{v}} &= \frac{1}{\left\|\boldsymbol{v}\right\|}\boldsymbol{v}\\ &= \frac{1}\sqrt{v_1^2+v_2^2+v_3^2}\,\boldsymbol{v}, \end{align} where the fraction term is the inverse square root of v_1^2+v_2^2+v_3^2 . When the fast inverse square root algorithm was developed in the early 1990s, most floating point processing power lagged the speed of integer processing.
In particular the x87 instruction set was very slow at the time compared to modern SSE operations. The fast inverse square generates a good approximation through integer operations by adding and subtracting the integer form of floating-point numbers, and taking a square root by dividing by two (which is just a right-shift).
Subsequent additions by hardware manufacturers have made this algorithm redundant for the most part. For example, on x86, Intel introduced the SSE instruction rsqrtss in 1999. In a 2009 benchmark on the Intel Core 2, this instruction took 0.85ns per float compared to 3.54ns for the fast inverse square root algorithm, and had less error.
Overview of the code
The following C code is the fast inverse square root implementation from Quake III Arena, stripped of C preprocessor directives, but including the exact original comment text: 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; } At the time, the general method to compute the inverse square root was to calculate an approximation for \frac{1}{\sqrt{x}} , then revise that approximation via another method until it came within an acceptable error range of the actual result. Common software methods in the early 1990s drew approximations from a lookup table.
The key of the fast inverse square root was to directly compute an approximation by utilizing the structure of floating-point numbers, proving faster than table lookups. The algorithm was approximately four times faster than computing the square root with another method and calculating the reciprocal via floating-point division.
The algorithm was designed with the IEEE 754-1985 32-bit floating-point specification in mind, but investigation from Chris Lomont showed that it could be implemented in other floating-point specifications. The advantages in speed offered by the fast inverse square root trick came from treating the 32-bit floating-point word as an integer, then subtracting it from a magic constant, .
This integer subtraction and bit shift results in a bit pattern which, when re-defined as a floating-point number, is a rough approximation for the inverse square root of the number. One iteration of Newton's method is performed to gain some accuracy, and the code is finished.
The algorithm generates reasonably accurate results using a unique first approximation for Newton's method; however, it is much slower and less accurate than using the SSE instruction rsqrtss on x86 processors also released in 1999.
Worked example
As an example, the number x=0.15625 can be used to calculate \frac{1}{\sqrt{x}} \approx 2.52982 . The first steps of the algorithm are illustrated below: 0011_1110_0010_0000_0000_0000_0000_0000 Bit pattern of both x and i 0001_1111_0001_0000_0000_0000_0000_0000 Shift right one position: (i >> 1) 0101_1111_0011_0111_0101_1001_1101_1111 The magic number 0x5F3759DF 0100_0000_0010_0111_0101_1001_1101_1111 The result of 0x5F3759DF - (i >> 1) Interpreting as IEEE 32-bit representation: 0_01111100_01000000000000000000000 1.25 × 2 −3 0_00111110_00100000000000000000000 1.125 × 2 −65 0_10111110_01101110101100111011111 1.432430... × 2 63 0_10000000_01001110101100111011111 1.307430... × 2 1 Reinterpreting this last bit pattern as a floating point number gives the approximation y=2.61486 , which has an error of about 3.4%.
After one iteration of Newton's method, the final result is y=2.52549 , an error of only 0.17%.
Avoiding undefined behavior
According to the C standard, reinterpreting a floating point value as an integer by casting then dereferencing the pointer to it can cause undefined behavior in case the sizes of integer and float do not match on the given architecture. This can be avoided by using alternative type punning techniques such as C's unions or C++20's std::bit_cast .
Algorithm
The algorithm computes \frac{1}{\sqrt{x}} by performing the following steps: Alias the argument x to an integer as a way to compute an approximation of the binary logarithm \log_{2}(x) Use this approximation to compute an approximation of \log_{2}\left(\frac{1}{\sqrt{x}}\right) = -\frac{1}{2} \log_{2}(x) Alias back to a float, as a way to compute an approximation of the base-2 exponential Refine the approximation using a single iteration of Newton's method.
Floating-point representation
Since this algorithm relies heavily on the bit-level representation of single-precision floating-point numbers, a short overview of this representation is provided here. To encode a non-zero real number x as a single precision float, the first step is to write x as a normalized binary number: \begin{align} x &= \pm 1.b_1b_2b_3\ldots \times 2^{e_x} \end{align} where the exponent e_x is an integer, and 1.b_1b_2b_3\ldots is the binary representation of the significand.
Since the single bit before the point in the significand is always 1, it does not need be stored. The equation can be rewritten as: \begin{align} x &= (-1)^{S_x} \cdot 2^{e_x} (1 + m_x) \end{align} where m_x means 0.b_1b_2b_3\ldots , so m_x \in [0, 1) .
From this form, three unsigned integers are computed: S_x , the "sign bit", is 0 if x is positive and 1 negative or zero (1 bit) E_x = e_x + B is the "biased exponent", where B = 127 is the "exponent bias" (8 bits) M_x = m_x \times L , where L = 2^{23} (23 bits) Thus: e_x = E_x -B and m_x = \frac{M_x}{L} . These fields are then packed, left to right, into a 32-bit container.
As an example, consider again the number x = 0.15625 = 0.00101_2 . Normalizing x yields: x = (-1)^{0} \cdot 2^{-3}(1 + 0.25) = +2^{-3}(1 + 0.25) and thus, the three unsigned integer fields are: S = 0 E = -3 + 127 = 124 = 0111\ 1100_2 M = 0.25 \times 2^{23} = 2\ 097\ 152 = 0010\ 0000\ 0000\ 0000\ 0000\ 0000_2 these fields are packed as shown in the figure below: The number is represented in binary as: I_x = S_x \cdot 2^{31} + E_xL + M_x Also, since this algorithm works on real numbers, \sqrt{x} is only defined for x \geq 0 .
The code thus assumes x \geq 0 and S_x = 0 . The number, given to calculate the square root, could be rewritten as: I_x = E_xL +M_x x = (-1)^0 \cdot 2^{e_x} (1 + m_x) = + 2^{e_x} (1 + m_x)
Aliasing to an integer as an approximate logarithm
If \frac{1}{\sqrt{x}} were to be calculated without a computer or a calculator, a table of logarithms would be useful, together with the identity \log_b\left(\frac{1}{\sqrt{x}}\right) = \log_b\left(x^{-\frac{1}{2}}\right) = -\frac{1}{2} \log_b(x) , which is valid for every base b . The fast inverse square root is based on this identity, and on the fact that aliasing a float32 to an integer gives a rough approximation of its logarithm. Here is how: If x is a positive normal number: x = 2^{e_x} (1 + m_x) then \log_2(x) = e_x + \log_2(1 + m_x) and since m_x \in [0, 1) , the logarithm on the right-hand side can be approximated by \log_2(1 + m_x) \approx m_x + \sigma where \sigma is a free parameter used to tune the approximation.
For example, \sigma = 0 yields exact results at both ends of the interval, while \sigma = \frac{1}{2} - \frac{1+\ln(\ln(2))}{2\ln(2)} \approx 0.0430357 yields the optimal approximation (the best in the sense of the uniform norm of the error). However, this value is not used by the algorithm as it does not take subsequent steps into account.
Thus there is the approximation \log_2(x) \approx e_x + m_x + \sigma. Interpreting the floating-point bit-pattern of x as an integer I_x yields \begin{align} I_x &= E_x L + M_x\\ &= L (e_x + B + m_x)\\ &= L (e_x + m_x + \sigma + B - \sigma)\\ &\approx L \log_2(x) + L (B - \sigma). \end{align} It then appears that I_x is a scaled and shifted piecewise-linear approximation of \log_2(x) , as illustrated in the figure on the right.
In other words, \log_2(x) is approximated by \log_2(x) \approx \frac{I_x}{L} - (B - \sigma).
First approximation of the result
The calculation of y=\frac{1}{\sqrt{x}} is based on the identity \log_2(y) = - \tfrac{1}{2}\log_2(x) Using the approximation of the logarithm above, applied to both x and y , the above equation gives: \frac{I_y}{L} - (B - \sigma) \approx - \frac{1}{2}\left(\frac{I_x}{L} - (B - \sigma)\right) Thus, an approximation of I_y is: I_y \approx \tfrac{3}{2} L (B - \sigma) - \tfrac{1}{2} I_x which is written in the code as i = 0x5f3759df - ( i >> 1 ); The first term above is the magic number \tfrac{3}{2} L (B - \sigma) = \mathtt{0x5f3759df} from which it can be inferred that \sigma \approx 0.0450466 . The second term, \frac{1}{2}I_x , is calculated by shifting the bits of I_x one position to the right.
Newton's method
The number y=\tfrac{1}{\sqrt{x}} is a solution of the equation \tfrac{1}{y^2}-x=0 . The approximation yielded by the earlier steps can be refined by using a root-finding method, a method that finds the zero of a function.
The algorithm uses Newton's method: if there is an approximation, y_n for y , then a better approximation y_{n+1} can be calculated by taking y_n - \tfrac{f(y_n)}{f'(y_n)} , where f'(y_n) is the derivative of f(y) at y_n . Applied to the equation \tfrac{1}{y^2}-x=0 , Newton's method gives \begin{align} f(y) &= \frac{1}{y^2} - x\\ f'(y) &= -\frac{2}{y^3}\\ y_{n+1} &= y_n - \frac{f(y_n)}{f'(y_n)}\\ &= y_n + \frac{y_n^3}{2} \left(\frac{1}{y_n^2} - x\right)\\ &= y_n \left(\frac{3}{2} - \frac{x}{2}y_n^2\right), \end{align} which is written in the code as y = y * ( threehalfs - ( x2 * y * y ) ); .
By repeating this step, using the output of the function ( y_{n+1} ) as the input of the next iteration, the algorithm causes y to converge to the inverse square root. For the purposes of the Quake III engine, only one iteration was used. A second iteration remained in the code but was commented out.
Magic number
It is not known precisely how the exact value for the magic number was determined. Chris Lomont developed a function to minimize approximation error by choosing the magic number R over a range. He first computed the optimal constant for the linear approximation step as , close to , but this new constant gave slightly less accuracy after one iteration of Newton's method.
Lomont then searched for a constant optimal even after one and two Newton iterations and found , which is more accurate than the original at every iteration stage. He concluded by asking whether the exact value of the original constant was chosen through derivation or trial and error.
Lomont said that the magic number for 64-bit IEEE754 size type double is , but it was later shown by Matthew Robertson to be exactly . Jan Kadlec reduced the relative error by a further factor of 2.7 by adjusting the constants in the single Newton's method iteration as well, arriving after an exhaustive search at conv.i = 0x5F1FFFF9 - ( conv.i >> 1 ); conv.f *= 0.703952253f * ( 2.38924456f - x * conv.f * conv.f ); return conv.f; A complete mathematical analysis for determining the magic number is now available for single-precision floating-point numbers.
See also
Magic number
Bibliography
Centenary Edition, 2008, .
External links
0x5f3759df, further investigations into accuracy and generalizability of the algorithm by Christian Plesner Hansen Origin of Quake3's Fast InvSqrt() Quake III Arena source code (archived in Software Heritage) Implementation of InvSqrt in DESMOS "Fast Inverse Square Root — A Quake III Algorithm" (YouTube)
Text derived from https://en.wikipedia.org/w/index.php?oldid=1375856938 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “fast inverse square root” release date (×3) · confidence 0.95 revision URL