0x5f3759df这个快速开方中的常数的数学依据是什么?
2015-11-24 20:23:03;  来源:知乎;  作者:;  评论:0 点击:

看了关于卡马克和雷神之锤3的故事,其中一个关于快速开方的算法中常数0x5f3759df被广为讨论,我们来看看其中的奥妙~(分析由网友提供)。原...
看了关于卡马克和雷神之锤3的故事,其中一个关于快速开方的算法中常数0x5f3759df被广为讨论,我们来看看其中的奥妙~(分析由网友提供)。
原函数如下:
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;
}
代码中标识WTF的地方神奇地完成了核心运算,这个是靠猜的吗?如果不是猜的依据在哪里?如果是猜的为何会这么准?

单精度的浮点数结构是这样:
那么现在,每个正浮点数 y 可以用尾数和指数的形式写成 2^e(1+m),其中 m 是尾数部分,取值范围是 [0, 1);e 是指数部分,一个整数。每个浮点数所对应的「整数形式」则可以用EL+M表示,其中 L 是指数部分需要的位移次数(用 2 的幂表示),E 和 M 是指数部分和小数部分的整数版本。两者之间的关系是
\left\{ 
\begin{array}{ll}
E  =  e + B \\
M  =  mL
\end{array}
 \right.
对单精度浮点而言,L=2^{23},B=127

考虑对数 \log_2 y=e+\log_2(1+m),由于m\in\left[0, 1\right)\log_2(1+m)\in\left[0,1\right),取近似\log_2(1+m)\approx m+\delta,可以算出整体「偏差」最小的\delta=0.0430357 ,此时两者基本相当。因此我们可以说

\log_2 y\approx e+m+\delta……………… (1)

那么,对于 y 的整数形式 Y 而言,展开并带代入 (1) 有:
Y & = & EL+M\\
&= &L(e+B+m) \\
& \approx & L(\log_2 y + B - \delta)


\log_2 y\approx {Y \over L}-(B-\delta)………………(2)

那么对于 y来说,\log_2{y,代入 (2) 得:
{Y
解得
Y
这个就是代码
i  = 0x5f3759df - ( i >> 1 );
的秘密所在。


作者:Belleve
链接:http://www.zhihu.com/question/26287650/answer/32552231
来源:知乎 本文属转载文章,并不能保证完全正确,只供学习交流参考,版权归原作者所有。如果您认为有侵犯权利等不和法行为,请联系我们及时改正。

相关热词搜索:0x5f3759df 快速开方 算法 卡马克

上一篇:第一页
下一篇:最后一页

收藏
回到顶部