《雷神之锤》的快速平方根倒数
在1999年,id software公司发布了《雷神之锤III竞技场(Quake III Arena)》巨作,此第一身射击游戏有别于前作,以多人连綫游戏为主轴,得到空前的成功。
在2002、2003年间,网上出现一段关于该游戏中的源代码讨论,那段代码是这样的:
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;}
它是用于计算一个单精度浮点数的平方根倒数(reciprocal square root, 即1/sqrt(x))。平方根倒数在游戏中经常用到,例如把矢量归一化(normalize)时,就要计算n = v / sqrt(v ⋅ v)。
此段代码使用了牛顿法(Newton’s method)去提升精确度,但令人渍渍称奇的是它计算初始估值的这一句:
i = 0x5f3759df - ( i >> 1 );
它利用了IEEE754浮点数的二进制表示来计算第一个近似值。此方法是谁发明的,魔术数字(magic number) 0x5f3759df从何而来,暂时也没有确切的证据。
查看详情

他的文章