Fast inverse square root
lastmod 2023-03-30created 2016-09-194 edits
Fast inverse square root, sometimes called Fast InvSqrt() or by the hexadecimal 0x5f3759df, is an algorithm for computing the reciprocal of the square root of a 32-bit real number in the IEEE 754 floating-point format. The algorithm is thought to have been developed at Silicon Graphics in the early 1990s, and is best known for its use in the source code of Quake III Arena in 1999. The algorithm was discussed on the Chinese developer forum CSDN in 2000, and became publicly known in 2002 or 2003 on public forums such as Usenet. Used in computer graphics to calculate angles of incidence and reflection for lighting and shading, the algorithm helped ease the computational cost of large-scale floating-point operations.
The algorithm takes a real number as input, stores half of its value separately for later use, and then treats the input float as long bits. The result of a one-bit logical right shift is subtracted from the magic number 0x5f3759df, and for a more accurate approximation this approximation is treated as a float again and one iteration of Newton's method is applied. The algorithm computes the inverse square root almost four times faster than using float division.
John Carmack believed the source code used in Quake III Arena was written by Terje Mathisen, an outstanding assembly programmer who had helped optimize Quake at id Software. However, the method turned out to have deep roots in both hardware and software development, and among the earliest known uses, Gary Tarolli's implementation for the SGI Indigo passed through Silicon Graphics and 3dfx Interactive. Rys Sommefeldt concluded that Greg Walsh of Ardent Computer created the algorithm after consulting with Cleve Moler, who designed MATLAB.
The fast inverse square root algorithm is used when calculating angles of incidence and reflection in operations such as lighting.