Quake III inverse square root
A bit trick for lighting, credited to the wrong person for years.
Greg Walsh. Constant 0x5f3759df. Shipped by id Software.
Quake III needed a fast inverse square root. Lighting and physics normalize vectors constantly. A normalized vector is a direction with length one, and the cheap way to get it is to multiply by the reciprocal of the length. The length is a square root. A full square root, done carefully, was too expensive for the number of vectors a frame required in 1999. The shipped code uses a shortcut that is worse mathematics and better engineering.
The shortcut treats the bits of a floating-point number as if they were an integer. It shifts those bits and subtracts them from the constant 0x5f3759df. It treats the result as a float again. One step of Newton's method then pulls the guess closer to the true reciprocal square root. The result is not exact. It is close enough for graphics, where a slightly wrong light is less visible than a slow frame, and it is much cheaper than the library square root the hardware of the time would have used.
The constant is the famous part, and it is a tuned approximation, not a magic number in the superstitious sense. Floating-point format stores a magnitude as an exponent and a fraction. The bit pattern of a float, read as an integer, is roughly related to the logarithm of the value. An inverse square root is a logarithm you can approximate with a multiply and a subtract, which in integer clothes is a shift and a subtract. The constant centers that approximation so the Newton step has a good place to start. Change the constant and the guess gets worse. The one that shipped is 0x5f3759df.
Greg Walsh wrote the routine. John Carmack did not. Carmack's mail, and the id Software source, made the trick famous, and the fame stuck to the wrong name for years. Carmack has not claimed the invention. He passed on code he had met, the way a working programmer passes on a gem. The public, and a great many blog posts, preferred a single famous author to a correct one. The credit on this site names Walsh, and it names the constant, and it says the routine shipped in Quake III. That is the whole attribution the object is willing to imply. The essay is where the miscredit gets corrected.
The bars are the function as it appears in the Quake III sources. Comment lines are gray runs. The constant is the color of a number. The shift and the Newton step are the colors of the operations around them. No letters remain in the picture, including the blunt comment the source is known for. The comment's job, astonishment that the trick works, is part of the oral history. It is not part of the print. A picture with no letters cannot smuggle a sentence onto a shirt, which is the rule this catalog prefers when the sentence belongs to someone else's file.
id released that source under GPL-2.0. A lawyer cleared the listing. The license notice stays on the product page, with the copyright in id Software's name and the statement that Walsh wrote the routine. GPL is a condition, not a vibe. The condition includes carrying the license. The page carries it. The mug carries the bit trick: integer, constant, float, one refinement.
There is a longer prehistory, as there usually is with a trick this good. Approximations of this family were known to graphics programmers before Quake III shipped. The catalog does not reassign Walsh's credit in order to gesture at that prehistory, and it does not hand the routine back to Carmack in order to use a more famous name on a product. The shipped function has an author. The author is the one the notice names. The constant is printed here as digits because digits are the fact that made the function identifiable across a decade of wrong captions. Everything else a caption usually adds is the mistake.
The Newton step is there because the bit trick alone is a rough guess. One iteration is the compromise the frame rate allowed. A second iteration would have been closer and slower, and the shipped game picked closer-enough. The bars include that step, so the picture is not only the constant. The constant is the headline. The step is the craft.