牛顿迭代法的作用是使用迭代法来求解函数方程的根，简单的说就是不断地求取切线的过程．对于形如f(x)=0的方程，首先任意的估算一个解x0，再把该估计值代入原方程中．由于一般不会正好选择到正确的解，所以有f(x0)=a.这时计算函数在x0处的斜率，和这条斜率与ｘ轴的交点x1. f(x)=0中精确解的意义是，当取得解的时候，函数值为零(即f(x)的精确解是函数的零点)．因此，x1比x0更加的接近精确地解．只要以此方法不分段的更新ｘ，就可以取得无线接近的精确地解．但是也有可能会遇到牛顿迭代法无法收敛的情况．比如函数有多个零点，或者是函数不连续的时候．
设x的ｍ次方根为a
const float EPS = 0.00001;
double sqrt(double x) {
if(x == 0) return 0;
double result = x; /*Use double to avoid possible overflow*/
double lastValue;
do{
lastValue = result;
result = result / 2.0f + x / 2.0f / result;
}while(abs(result - lastValue) > EPS);
return (double)result;
}
更快的方法
在游戏雷神之锤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; // 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;
}
这段代码的作用就是求数number的平方根，并返回它的倒数．经过测试，它的效率比牛顿法要快几十倍，也比C++标准的sqrt()函数要快好几倍．
