现在的位置: 首页 > 综合 > 正文

求平方根倒数的算法

2014年01月08日 ⁄ 综合 ⁄ 共 637字 ⁄ 字号 评论关闭

下面这个求的函数号称比直接调用sqrt库函数快4倍,来自游Quake
III的源代
码。
float InvSqrt (float
x){

   float xhalf = 0.5f*x;
   int i = *(int*)&x;
   i = 0x5f3759df - (i>>1);
   x = *(float*)&i;
   x = x*(1.5f - xhalf*x*x);
   return x;
}
们这里分析一下它的原理(指程序的正确性,而不是解释为何快)。
分析程序之前,我们必须解释一下float数据在计算机里的表示方式。一般而言,一个float数据共32个bit,和int数据一样。其中前23位为有效数字,后面接着一个8位数据表示指数,最后一位表示符号,由于这里被开方的数总是大于0,所以我们暂不考虑最后一个符号位。此时
如果我们把计算机内的浮点数看做一个整数,那么
现在开始逐步分析函数。这个函数的主体有四个语句,分别的功能是:
int i = *(int*)&x;
这条语句把转成
i = 0x5f3759df - (i>>1);
这条语句从计算
x = *(float*)&i;
这条语句将转换为
x = x*(1.5f - xhalf*x*x);
这时候的x是近似解;此步就是经典的牛顿迭代法。迭代次数越多越准确。

键是第二步 i = 0x5f3759df - (i>>1);
这条语句从计算,原理:
,用带入之后两边取对数,再利用近似表示,算一算就得到
若取就是程序里所用的常量0x5f3759df。至于为何选择这个则应该是曲线拟合实验的结果

抱歉!评论已关闭.