这是2019/09/06的一篇笔记，现在补上。这是《算法》第四版中提到的，如何实现sqrt(x)，当时和文德在实验室里面一起研究了一下。今天深信服笔试又遇到了简单版的题目。

整数型

放在以前，只能求整数的平方根：

1
2
3
4
5

public int sqrt(int n){
    for(int i = 0; i * i < n; i++){
        if(i * i == n) return i;	//或者想要记录i * i <= n
  	}
}

至于深信服也是简化到int，笔试嘛…我直接

return (int)Math.sqrt(n);

测试用例当然是100%，能不能拿到分我就不知道了，笔试嘛谁管这个，他也没说不能用，时间重要哈

小数型-牛顿迭代法

再来说一下正经的sqrt实现，也就是如果是小数，你就不知道每次迭代加多少了，0.01？还是0.001？都不够精确。书中提到了牛顿迭代法：

假设要求√2的值，那么构造f(x) = x² - 2， 当y=0时，与x轴的交点就是√2(红点)

随机取一点p，求得f(p)，斜率为2p

点斜式构造(y – y0) = k(x – x0)得 y – f(p) = 2p(x - p)

令y = 0，求得直线与y轴交点处x的值x = p – f(p)/2p

这一点会比(4, 0)更接近红点，于是取p = 这一点并重复上述步骤，慢慢逼近红点处x的值

将f(p)化开来：x = p – (p² - 2)/2p

一般化，若p为x上任意一点，x则为下一个靠近点

即next_x = x – (x² - 2) / 2x，化简得next_x = (x + 2/x) / 2

在代码中则直接都表示为x，即x = (x + 2/x) / 2

再一般化，求根号c的值：x = (x + c/x) / 2

逼近个7 8次就已经很接近√2了

Java实现

逼近个7 8次这个说法太宽泛了，可以设置一个能接受的误差程度，比如err = 1e-15

1
2
3
4
5
6
7
8
9

public double sqrt(double c){
    if(c < 0) return Double.NaN;    //小于0是没有平方根的
    double err = 1e-15;			    //因为是逼近，√2是无理数，需要结束条件，也就是能接受的误差程度,否则永远循环
    double res = c;                 //一开始取p = c，因为√2一定<2
    while(Math.abs(res - c / res) > err * res){	//结束条件: abs(res² - c) <= err
        res = (res + c / res) / 2.0;			//前面推导的公式
    }
    return res;
}

ps：这是什么？当时看这个的时候我忽然发现，这不就类似bp神经网络的梯度下降嘛！！！！神经网络的那些听起来高大上的反向传播，梯度下降。不就正是和这个一样求导逼近的思想吗，还不如从这个牛顿迭代法开始讲解呢，更加直观。