# 谈谈牛顿迭代法

## 从开根说起

$$y - y_1 = f^\prime (x_1) ( x - x_1 )$$

$f ^ \prime (x) = 2x$ ，因此对于本问题的牛顿迭代公式为：

$$x_n = x_{n-1} - \dfrac{y_{n-1}}{2x_{n-1}}$$

• $(x_1, y_1) = (2,2)$ , $x_2 = 2 - \dfrac{2}{4} = \dfrac{3}{2}$

• $( x_2, y_2 ) = (\dfrac{3}{2}, \dfrac{1}{4}), x_3 = \dfrac{3}{2} - \dfrac{1}{4} \cdot \dfrac{1}{3} = \dfrac{17}{12}$

• $(x_3, y_3) = (1.41666666667, 0.00694444444)， y_x = 1.41421568628$

• $x_0 = 1.41421356237$

• $y_4 = 1.41421568628$

 1double sqrt(double n) {
2  const double delta = 1E-10;
3  double x = 1;
4  while (true) {
5    double xn = (x + n / x) / 2;
6    if (abs(x - xn) < delta) {
7        break;
8    }
9    x = xn;
10  }
11  return x;
12}


 1float Q_rsqrt( float number )
2{
3    long i;
4    float x2, y;
5    const float threehalfs = 1.5F;
6
7    x2 = number * 0.5F;
8    y  = number;
9    i  = * ( long * ) &y;                       // evil floating point bit level hacking
10    i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
11    y  = * ( float * ) &i;
12    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
13//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
14
15#ifndef Q3_VM
16#ifdef __linux__
17    assert( !isnan(y) ); // bk010122 - FPE?
18#endif
19#endif
20    return y;
21}