求平方根的方法

数学

---

牛顿迭代法

它是一种在实数域和复数域上近似求解方程的方法。方法使用函数$f(x)$的泰勒级数的前面几项来寻找方程$f(x)=0$的根。
首先，选择一个接近函数$f(x)$零点的$x_0$，计算相应的$f(x_0)$和切线斜率$f'(x_0)$（这里$f'$表示函数$f$的导数）。然后我们计算穿过点$(x_0, f(x_0))$并且斜率为$f'(x_0)$的直线和x轴的交点的x坐标，也就是求如下方程的解：

$$f(x_0)= (x_0-x)\cdot f'(x_0)$$
我们将新求得的点的$x$坐标命名为$x_1$，通常$x_1$会比$x_0$更接近方程$f(x)=0$的解。因此我们现在可以利用$x_1$开始下一轮迭代。迭代公式可化简为如下所示：

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$
已经证明，如果$f'$是连续的，并且待求的零点$x$是孤立的，那么在零点$x$周围存在一个区域，只要初始值$x_0$位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果$f'(x)$不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。

根据上面我们可以把求平方根看做求下面公式

$$f(x)=x^2-N$$

求导得到：

$$f'(x)=2*x$$

可以推出下面公式

$$x_{n+1} = x_n - \frac{f(x_n)}{(2x_n)}$$

最后得到：

$$x_{n+1} = \frac12(x_n+ \frac{N}{x_n})$$

下面牛顿法求平方根代码：

public int sqrt(int n) {
        int ret = 0;
        double x = n;
        double y = 1;
        double e = 0.0000000000000000001;
        while ((x - y) > e) {//判断是否相等，浮点数相等不能之间判断
            x = x + (y - x) / 2;//当x不等于y是，继续计算
            y = n / x;
        }
        return (int) y;
    }

二分搜索法

将x可以看做从1到x是递增符合二分的要求，首先计算$mid^2$是否等于$x$，如果相等，返回；大于则在左边寻找；小于则在右边寻找。

     public int sqrt(int x) {
            int low = 0;
            int high = x;
            if(x<0){
                return -1;
            }
            if(1==x||x==0){
                return x;
            }
            int mid = low + (high - low) / 2;
            while (low <=high) {
                long res = (long)mid * mid;//由于int相乘可能导致溢出，使用long，使用double也行
                if (res > x) {
                    high=mid-1;//不减1导致无限循环
                }else if(res<x){
                    low=mid+1;//
                }else{
                    return mid;
                }
                mid = low + (high - low) / 2;
            }
            return (long)mid*mid>x?mid-1:mid;
        }