暴力循环已死，牛顿迭代法称王

你好，我是小黄，一名独角兽企业的Java开发工程师。
感谢茫茫人海中我们能够相遇，
俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习，
希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。

在这里插入图片描述

一、引言

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

给定一个 正整数 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;
    }

在这里插入图片描述