爱吃醋的饺子's BLOG

浏览数(10351)

【0x5f3759df】

《雷神之锤III》的代码直到QuakeCon 2005才正式放出,但早在2002年(或2003年)时平方根倒数速算法的代码就已经出现在Usenet与其他论坛上了。最初人们猜测是卡马克写下了这段代码,但他在询问邮件的回复中否定了这个观点,并猜测可能是先前曾帮id Software优化雷神之锤的资深汇编程序员Terje Mathisen写下了这段代码;而在Mathisen的邮件里他表示在1990年代初他只曾作过类似的实现,确切来说这段代码亦非他所作。现在所知的最早实现是由Gary Tarilli在SGI Indigo中实现的,但他亦坦承他仅对常数R的取值做了一定的改进,实际上他也不是作者。Rys Sommefeldt则在向以发明MATLAB而闻名的Cleve Moler查证后认为原始的算法是Ardent Computer公司的Greg Walsh所发明,但他也没有任何决定性的证据能证明这一点。

目前不仅该算法的原作者不明,人们也仍无法明确当初选择这个“魔术数字”的方法。Chris Lomont在研究中曾做了个试验:他编写了一个函数,以在一个范围内遍历选取R值的方式将逼近误差降到最小,以此方法他计算出了线性近似的最优R值0x5f37642f(与代码中使用的0x5f3759df相当接近),但以之代入算法计算并进行一次牛顿迭代后,所得近似值与代入0x5f3759df的结果相比精度却仍略微更低;而后Lomont将目标改为遍历选取在进行1-2次牛顿迭代后能得到最大精度的R值,并由此算出最优R值为0x5f375a86,以此值代入算法并进行牛顿迭代后所得的结果都比代入原始值(0x5f3759df)更精确,于是他的论文最后以“原始常数是以数学推导还是以反复试错的方式求得”的问题作结。在论文中Lomont亦指出64位的IEEE754浮点数(即双精度类型)所对应的魔术数字是0x5fe6ec85e7de30da,但后来的研究表明代入0x5fe6eb50c7aa19f9的结果精确度更高(McEniry得出的结果则是0x5FE6EB50C7B537AA,精度介于两者之间)。在Charles McEniry的论文中,他使用了一种类似Lomont但更复杂的方法来优化R值:他最开始使用穷举搜索法,所得结果与Lomont相同;而后他尝试用带权二分法寻找最优值,所得结果恰是代码中所使用的魔术数字0x5f3759df,因此McEniry确信这一常数或许最初便是以“在可容忍误差范围内使用二分法”的方式求得。

// Quake-III Arena (雷神之锤3)引擎sqrt实现

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 thefuck?

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;

}

✎﹏₯㎕﹍﹍·狗粮

微信打赏

菜单