TIL the Quake 3 Fast Inverse Square Root hack
POSTED ON:
TAGS: math videogames magicnumber
I was reading about Repel Magic Numbers from Building a newbie-friendly codebase
and thought of this...
You might be familiar with the Fast Inverse Square Root
Inverse square roots are useful in video game graphics and particularly in 3D game engines. Pathfinding, lighting, reflections, and many other game programming techniques require vector normalization, which involves an inverse square root operation. Inverse square roots, which rely on floating point division, are expensive for processors.
In a fast paced, graphically intense game like Quake III Arena, these calculations are made millions of times every second, so even a minor improvement in the performance of such a calculation could significantly improve graphics computation speed and ultimately the game’s frame rate. So how did programmers of the id Tech 3 engine get around the expensive inverse square root function? They implemented a very accurate, very fast approximation.
via https://medium.com/hard-mode/the-legendary-fast-inverse-square-root-e51fee3b49d9
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. Copies of the fast inverse square root code appeared on Usenet and other forums as early as 2002 or 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 2005, but provided no answers. The authorship question was answered in 2006.
via the wiki article.
It looks like this:
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;
}Related TILs
Tagged: math