如何优雅的求平方根

程序员文章站 2022-04-02 11:52:49

...

F&Q

承太郎：DIO，来做一道题

DIO：承太郎。来吧。（JOJO立）

承太郎：求一个数的算术平方根，保留整数部分，简单吧，你一定很快就能做出来。

DIO：Math.sqrt(x)，太简单了。hahaha

承太郎：你居然说用Math.sqrt()，不能用库函数！！！不能用库函数！！！不能用库函数！！！やれやれだぜ（真是够了），

DIO：这！！砸瓦鲁多!!F

二分法

求一个正整数的算术平方根的话，这个平方根一定不会大于这个正整数的二分之一。所以我们可以利用二分法从区间[1，x / 2]中来找这个平方根

关于二分搜索查考这篇文章：https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/er-fen-cha-zhao-xiang-jie

class Solution {
    public int mySqrt(int x) {
        // 二分法
        // 0的任何次方等于0
        if (x == 0) return 0;
        long left = 1;
        long right = x / 2;
        while (left < right) {
            long mid = (left + right + 1) / 2; // 不考虑越界
            long v = mid * mid;
            if (v > x) right = mid - 1;
            else left = mid;
        }
        return (int)left;
    }
}

值得注意的是取mid这里，我们一定要取区间的右中位数，例如求9的平方根，当我们计算到区间【3， 4】的话，如果mid按照如下取值的话

mid = left + (right - left ) / 2

此时，mid=3，left = mid，此时会循环查找【3，4】的值。

牛顿迭代法

重点来了，这道题更牛逼的算法还是牛顿迭代法（万能的牛顿，你还有啥不会的），其实准确的叫牛顿-拉夫逊（拉弗森）方法，又是一个被牛顿名声盖过的人，可怜拉弗森一秒钟。。。。

好了。在这里我不讲牛顿迭代法如何得来，反正从泰勒级数展开公式推导出的，说了你也不懂（皮一下），我就从结论入手。

先看一图：

如何优雅的求平方根

该算法的思想是：

迭代的过程中，使x不停的逼近与 f(x)=0，直到迭代收敛，上图不难看出来

因为牛顿法（下面会给出证明链接），所以我们可以令f(x) = x^2 - c

得出，x点切线方程：

如何优雅的求平方根

变形可得：

如何优雅的求平方根

又令f(x) = 0

所以得：

如何优雅的求平方根

所以：

如何优雅的求平方根

化简得出：

如何优雅的求平方根

那么，公式推导到此结束，剩下的就该写代码了

class Solution {
public:
    int mySqrt(int x) {
        long v = x;
        while (v * v > x)
            v = (v + x / v) / 2;  // 公式
        return (int)v;  // 取整
    }
};

如何优雅的求平方根

当然，如果我们不取整的话，只需要把long变成double型，注意有些数的算术平方根是算不出的，我们需要一个变量来保存上一步求出的数，用当前的数减去上一步求出的数小于 一个精度 即可。

看代码吧，我相信我的写作功底不是太好（留下了没有技术的泪）。

#define v 0.0000001
double sqrt(int x)
{
	double pre = 0;	// 上一步算的
	double curr = x;// 当前算的
	while (abs(curr - pre) > v)
	{
		pre = curr;
		curr = (curr + x / curr) / 2;
	}
	return pre;
}