用牛顿迭代法求浮点数的平方根

版权申明：http://yarin.iteye.com/blog/453262

先说个例子：

比如我们要求a的平方根，首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代几次后x的值就已经相当精确了。

看下面(假设a=2,我们求2的平方根)：

1.先随便猜个数，比如我猜2的平方根为7

( 7  + 2/7 ) / 2 = 3.64287514
( 3.64287514  + 2/3.64287514 ) / 2 = 2.095946017

......

......

( n+ 2/n) / 2 = 1.414....

 

下面是代码：

#define ABS(VAL) (((VAL)>0)?(VAL):(-(VAL))) //用牛顿迭代法求浮点数的平方根 float mysqrt(float x) { float g0,g1; if(x==0) return 0; g0=x/2; g1=(g0+x/g0)/2; while(ABS(g1-g0)>0.01) { g0=g1; g1=(g0+(x/g0))/2; } return g1; }

 

好的，就写到这里了！谢谢支持！ 

 

 

 

 

 

 

 

 

有个游戏引擎中的开方算法比库函数快好多倍，好像也是用牛顿迭代，不过忘了是哪个游戏了。

quake 3吧。。。比libm里面快了4倍吧。。。

一般函数的求根，无外乎
1，弦线法，
2，切线法，
3，1+2综合

其实都是迭代，起始值最好估计下，否则可能不收敛（迭代的混沌现象）

随便找个《数值分析》或是《计算方法》的书看看，都可以找到估值和加速迭代因子的算法

quake iii

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;
  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;        // 浮点数按BIT强行赋给长整形
  i  = 0x5f3759df - ( i >> 1 ); // 没天理！！！！！
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 第1次叠代
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 第2次叠代，可以删除
  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

补充
http://en.wikipedia.org/wiki/Fast_inverse_square_root

John Carmack 不是一般的强悍...

啊，传说中的那个神奇的常数？

嗯 就是那个.

说白了就是一个收敛比较快的展开式 ……

恩,其实如果做tuning做久了会遇到许多奇怪的magic number比如说,6755399441055744.0,
0x55555555,0x33333333之类的.