找回密码
 骑士注册

QQ登录

微博登录

搜索
❏ 站外平台:

Linux中国开源社区 观点 查看内容

平方根倒数速算法中的神奇数字:0x5f3759df

2013-06-20 14:56    评论: 6    

Quake III 公开源码后,有人在game/code/q_math.c里发现了这样一段代码。它的作用是将一个数开平方并取倒,经测试这段代码比(float)(1.0/sqrt(x))快4倍。具体代码为:

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;
}

 

函数返回1/sqrt(x),这个函数在图像处理中比sqrt(x)更有用。这个简洁的函数,最核心,也是最让人费解的,就是标注了“what the fuck?”的一句

i = 0x5f3759df – ( i >> 1 );

再加上

y  = y * ( threehalfs – ( x2 * y * y ) );

两句话就完成了开方运算!

算法的原理其实不复杂,就是牛顿迭代法,用x-f(x)/f’(x)来不断的逼近f(x)=a的根。一般的求平方根都是这么循环迭代算的,但是整个程序中选择了一个神秘的常数0x5f3759df 来计算那个猜测值,算出的值非常接近1/sqrt(n),这样我们只需要2次牛顿迭代就可以达到我们所需要的精度。

数学家Chris Lomont看了以后觉得有趣,决定要研究一下弄出来的这个猜测值有什么奥秘。在精心研究之后从理论上也推导出一个最佳猜测值, 0x5f37642f。Lomont计算出结果以后非常满意,于是拿自己计算出的起始值和神秘数字做比赛,看看谁的数字能够更快更精确的求得平方根。结果是Lomont输了…

via http://www.biaodianfu.com/0x5f3759df.html 

最新评论

我也要发表评论

微博评论 2013-06-20 15:43 回复
卡马克

来自 二踢脚plus 的新浪微博
微博评论 2013-06-20 15:43 回复
牛屄!但看不懂!

来自 Hunter木子会 的新浪微博
微博评论 2013-06-20 15:43 回复
写这个代码的到底是程序员还是数学家?

来自 死亡是解脱 的新浪微博
微博评论 2013-06-20 15:43 回复
回复@死亡是解脱:顶级程序员必然有深厚的数学功力

来自 Linux中国 的新浪微博
linux 2013-06-20 15:47 回复

关于这个事情的更详细的情况,可以看: http://www.douban.com/note/196653073/ 

微博评论 2013-06-21 19:24 回复
这些人是用代码在写诗啊!@汝等看好了208

来自 忘了不记得了 的新浪微博

收藏

返回顶部

分享到微信

打开微信,点击顶部的“╋”,
使用“扫一扫”将网页分享至微信。