Leecode-69.Sqrt(x)-牛顿迭代法

题目：

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,  由于返回类型是整数，小数部分将被舍去。

解题思路：

注：使用 while(r * r> x)会溢出
牛顿迭代法：计算x2 = n的解，令f(x)=x2-n，相当于求解f(x)=0的解。 首先取x0，如果x0不是解，做一个经过(x0,f(x0))这个点的切线，与x轴的交点为x1。 同样的道理，如果x1不是解，做一个经过(x1,f(x1))这个点的切线，与x轴的交点为x2。 以此类推。 以这样的方式得到的xi会无限趋近于f(x)=0的解。 判断xi是否是f(x)=0的解有两种方法： 一是直接计算f(xi)的值判断是否为0，二是判断前后两个解xi和xi-1是否无限接近。

另一种解释：设r是f(x) = 0的根，选取x0作为r初始近似值，过点（x0,f(x0)）做曲线y = f(x)的切线L，L的方程为y = f(x0)+f’(x0)(x-x0)，求出L与x轴交点的横坐标 x1 = x0-f(x0)/f’(x0)，称x1为r的一次近似值。 过点（x1,f(x1)）做曲线y = f(x)的切线，并求该切线与x轴交点的横坐标 x2 = x1-f(x1)/f’(x1)，称x2为r的二次近似值。重复以上过程，得r的近似值序列，其中x(n+1)=x(n)－f(x(n))/f’(x(n))，称为r的n+1次近似值，上式称为牛顿迭代公式。

经过(xi, f(xi))这个点的切线方程为f(x) = f(xi) + f ‘(xi)(x - xi)，其中f’(x)为f(x)的导数，本题中为2x。令切线方程等于0，即可求出xi+1=xi - f(xi) / f’(xi)。 继续化简，xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2。

public static int mySqrt(int x) {
        int r;
        if(x <= 1)
            return x;
        r = x;
        while(r > x / r)
            r = (r + x / r)/2;
        return(r);
    }

切线方程： 曲线C：y=f(x),曲线上点P(a,f(a)) f(x)的导函数f '(x)存在，以P为切点的切线方程：y-f(a)=f '(a)(x-a)