Quake-III Arena里面有一个闻名游戏界的开平方取倒函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
** float q_rsqrt( float number )
*/
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

#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}

第一次看到时着实被酷炫了一把,感觉很厉害,但却无法弄懂它的原理。这个函数的作用是用于对一个数开平方并取倒数,比用C库的sqrt实现(1.0f/sqrt(x))快了将近4倍。实现原理其实是牛顿迭代,也是平方根的一般算法,反复执行 y = y ( threehalfs – ( x2 y * y ) ); 其中y趋向于(1.0f/sqrt(x)),拿到的结果可以无限接近于我们想要的精度。

这个函数实现的算法被称为‘Fast Inverse Square Root’, 而它神奇的地方在于函数里面的实现采用了一个神秘的常数:0x5f3759df. 这个常数的来源目前无法被考究,也不能追溯确定这个常数的方法。

这里还有个典故,在Q3的代码公布,并且数学家Chris Lomont得知0x5f3759df这个常数之后,他通过用暴力搜索得出了与0x5f3759df非常接近、并且代入后得出的结果更加精确的魔数0x5f375a86,当然,实际上和0x5f3759df还是非常接近。

3D游戏引擎设计的作者David Eberly曾经发表论文解释了这个算法:
http://www.geometrictools.com/Documentation/FastInverseSqrt.pdf

不过最早还是Lomont在2003发表的:
http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

而David Eberly最近的一次补充是在2010年。

See also: http://en.wikipedia.org/wiki/Fast_inverse_square_root