Quake III's mysterious constant 0x5F3759DF sparked a hunt for its author
Buried in the code of Quake III Arena was a baffling line that subtracted a number from the constant 0x5F3759DF and somehow produced an inverse square root. Programmers guessed John Carmack had written it. The real author, Greg Walsh, only stepped forward in 2006, years after the trick went viral.
Games need inverse square roots constantly. Lighting and shading require angles of incidence and reflection, and those rely on unit vectors: arrows scaled to length one by dividing each component by the vector's length, the square root of the sum of its squared components. Quake III had to do this enormous numbers of times every second. In the early 1990s, floating-point arithmetic lagged well behind integer operations, and common software drew starting guesses from lookup tables before refining them.
The trick sidestepped both. It took a 32-bit floating-point number, reinterpreted its bits as an integer, shifted them right by one place, an integer shortcut for dividing by two that stands in for taking a square root, and subtracted the result from the magic constant. Read back as a floating-point number, that bit pattern was already a rough answer, and one round of Newton's method sharpened it. The approach ran roughly four times faster than computing a square root and then dividing. Modern C programmers are warned that the pointer cast used for the reinterpretation can trigger undefined behaviour; unions or C++20's std::bit_cast avoid that.
Its lineage is tangled. William Kahan and K.C. Ng at Berkeley described square roots via bit manipulation and Newton iterations in an unpublished 1986 paper. Cleve Moler at Ardent Computer passed the idea to his colleague Walsh, who devised the famous constant. Gary Tarolli probably carried it to 3dfx around 1994, and Brian Hook may have brought it from there to id Software, which released Quake III in 1999. A variant also turned up in Activision's 1997 Interstate '76. The code spread through a Chinese developer forum in 2000 and online forums in 2002 and 2003, and even the full source release at QuakeCon 2005 settled nothing; Walsh finally contacted the site Beyond3D.
Hardware has since overtaken it. Intel's SSE instruction rsqrtss, introduced in 1999, took 0.85 nanoseconds per number in a 2009 benchmark against 3.54 for the trick, with less error.
Source: Fast inverse square root
