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

16 sec read

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

函数返回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输了…

参考文档:http://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

使用tqdm显示Python代码执行进度

在使用Python执行一些比较耗时的操作时,为了方便观察进度,通常使用进度条的方式来可视化呈现。Python中
标点符
34 sec read

利用SWIG实现Python调用C/C++

SWIG简介 SWIG是Simplified Wrapper and Interface Generator的
标点符
1 min read

WordPress又被黑了,解决方案记录

过了一个周末,今天整个网站打开无样式,后台无法打开,直接跳转到其他网站,才意识到网站可能被黑了。查看源代码:
标点符
1 min read

One Reply to “平方根倒数速算法中的神奇数字:0x5f3759df”

发表评论

电子邮件地址不会被公开。 必填项已用*标注