Fast inverse square root (sometimes referred to as Fast InvSqrt or by the hexadecimal constant 0x5f3759df) is a method of calculating x−½, the reciprocal (or multiplicative inverse) of a square root for a 32-bit floating point number in IEEE 754 floating point format. The algorithm was probably developed at Silicon Graphics in the early 1990s, and an implementation appeared in 1999 in the Quake III Arena source code, but the method did not appear on public forums such as Usenet until 2002 or 2003. At the time, the primary advantage of the algorithm came from avoiding computationally expensive floating point operations in favor of integer operations. Inverse square roots are used to compute angles of incidence and reflection for lighting and shading in computer graphics.
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 of one bit is performed and the result subtracted from the "magic" value 0x5f3759df. This is the first approximation of the inverse square root of the input. Treating the bits again as floating point it runs one iteration of Newton's method to return a more precise approximation. This computes an approximation of the inverse square root of a floating point number approximately four times faster than floating point division.
The algorithm was originally attributed to John Carmack, but an investigation showed that the code had deeper roots in both the hardware and software side of computer graphics. Adjustments and alterations passed through both Silicon Graphics and 3dfx Interactive, with Gary Tarolli's implementation for the SGI Indigo as the earliest known use. It is not known how the constant was originally derived, though investigation has shed some light on possible methods.
Read more about Fast Inverse Square Root: Motivation, Overview of The Code, Newton's Method, History and Investigation, See Also
Famous quotes containing the words fast, inverse, square and/or root:
“And in the next instant, immediately behind them, Victor saw his former wife.
At once he lowered his gaze, automatically tapping his cigarette to dislodge the ash that had not yet had time to form. From somewhere low down his heart rose like a fist to deliver an uppercut, drew back, struck again, then went into a fast disorderly throb, contradicting the music and drowning it.”
—Vladimir Nabokov (1899–1977)
“The quality of moral behaviour varies in inverse ratio to the number of human beings involved.”
—Aldous Huxley (1894–1963)
“The square dance fiddler’s first concern is to carry a tune, but he must carry it loud enough to be heard over the noise of stamping feet, the cries of the “caller,” and the shouts of the dancers. When he fiddles, he “fiddles all over”; feet, hands, knees, head, and eyes are all busy.”
—State of Oklahoma, U.S. public relief program (1935-1943)
“The bud of the apple is desire, the down-falling gold,
The catbird’s gobble in the morning half-awake
These are real only if I make them so. Whistle
For me, grow green for me and, as you whistle and grow green,
Intangible arrows quiver and stick in the skin
And I taste at the root of the tongue the unreal of what is real.”
—Wallace Stevens (1879–1955)