一、引言

今天在做力扣每日一题中，有一道题为：

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如  sqrt 。

大名鼎鼎的求平方根，传说中的牛顿迭代法，本篇来看一下具体是怎么进行实现的吧！

二、牛顿迭代法

牛顿迭代法又称为牛顿-拉弗森方法，实际上是由牛顿、拉弗森（又是一个被牛顿大名掩盖的家伙）各自独立提出来的

牛顿-拉弗森方法提出来的思路就是 利用切线是曲线的线性 逼近这个思想。

牛顿、拉弗森们想啊，切线多简单啊，研究起来多容易啊，既然切线可以近似于曲线，我直接研究切线的根不就成了。

如图所示：

对于上述函数的根来说，我们知道：x = 0

如果用牛顿迭代法怎么进行计算呢？

• F(x) = x * x
• F’(x) = 2 * x

首先，牛顿迭代法会找到一个点，比如 x0 ，从 x0 向曲线做直线，交于点 A，做点 A 的切线交于点 x1

这样的话，我们可以得到三个点：x1、x0、A

设A点坐标为 (x0，x0 * x0)、x1点坐标为 (x1， 0)

通过A点和x1点的坐标，可以得出该线的斜率：K = (x0 * x0) / (x0 - x1)

化简得知：

x0 - x1 = ( x0 * x0) / K

x0 - x1 = F(x0) / F’(x0)

x0 - x1 = x0 / 2

x1 = x0 / 2

我们再以 x1 点做上面相同的操作，得到：

• x2 = x1 / 2

我们无限制的进行上述操作，最终会得到一个公式：Xn+1 = Xn / 2

当无线次的迭代时，我们的 x 值会趋于0

三、平方根

我们上面说到，对于 F(x) = x * x，最终得到的结果为：Xn+1 = Xn / 2

我们想，对于平方根来说：x * x = num

可不可以转化一下，比如：F(x) = x * x - num，F'(x) = 2 * x，求这个函数的交点

利用上述我们说的牛顿迭代法，我们可以得知：

设 F1 点为(x0，x0 * x0 - num)，x1 点为（x1，0）

则：

• K = (x0 * x0 - num) / (x0 - x1)
• x0 - x1 = (x0 * x0 - num) / K
• x0 - x1 = F(x0) / F’(x0)
• x0 - x1 = x0 / 2 - num / (2 * x0)
• x1 = x0 / 2 + num / (2 * x0)
• 将x1、x2两点同样进行迭代，得到：x2 = x1 / 2 + num / (2 * x1)

得出式子：Xn+1 = Xn / 2 + num / 2 * Xn

简单来说，选中某个x的初始值，无限进行迭代，最终找到其平方根

F(x) = x * x - num 凸函数的性质，最终的结果应该是：x = sqrt(num)

我们最开始的 x 可以直接取值为 num，因为 num >= sqrt(num)

一般来说，可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数，一般可以取 1e-6 或者 1e-7

四、代码实现

  public boolean isPerfectSquare(int num) {
        if(num == 1){
            return true;
        }
        double ans = num;
        double dir = num;
        while(ans * ans - dir >= 1e-6){
            ans = ans / 2 + dir / (2 * ans);
        }
        int x = (int)ans;
        return x * x == num;
    }

五、总结

简单来说，牛顿迭代法通过不断的进行迭代，逐渐趋近于某个目标值

题目一：367. 有效的完全平方数

有兴趣的小伙伴可以去做一下，目前来说对于这种 平方根 题目，面试官最想听到的就是 牛顿迭代法，反手给其一波推理过程，直接抬走面试官。