[数据结构与算法]计算平方根的一些方法总结(C++)

tags: DSA Math C++

写在前面

重新熟悉下计算平方根的算法, 当然对于力扣的平方根69. x 的平方根 - 力扣（LeetCode）, 已经出现了不下五种的方法了, 这次简要总结下. 代码均为C++.

调包

return (int) sqrt(x);
return (int) pow(x, .5);

高级调包

应用了
$$\sqrt{x}=\exp (\frac{\ln x}{2})$$
这一关系, 需要注意浮点数舍入误差.

int mySqrt(int x) {
    if (x == 0) {
        return 0;
    }
    int ans = exp(0.5 * log(x));
    return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
}

二分查找

class Solution {
public:
    int mySqrt(int x) {
        int l{}, r{x}, ans{-1};
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        return ans;
    }
};

因为要找出小于等于$x$的最大整数$k$使$k$满足$k^2\le x$, 这类最大化最小的问题当然可以通过二分来做.

相当经典的思路, 但是每次mid增减的量太少, 比较慢.

减奇数法

class Solution {
public:
    int mySqrt(int x) {
        int cnt{};
        long long k{1};
        while ((x = x - k) >= 0) k = 2 * (++cnt) + 1;
        return cnt;
    }
};

这里参考B站某位网友的评论, 整数的平方不是可以表示成奇数之和吗, 这个思路很新颖, 虽然时间上比较长.

牛顿迭代

数值分析中的经典算法, 任何初值只要迭代7次以内几乎都可以得到较为精确的结果, 何况这还只需要给出整数.

class Solution {
public:
    int mySqrt(int x) {
        if (!x) return 0;
        double xk = x, xk1 = INT64_MAX;
        while (fabs(xk - xk1) > 1e-7) {
            xk = xk1;
            xk1 = (xk + x / xk) / 2;
        }
        return static_cast<int>(xk);
    }
};

当然还有牛顿迭代的位运算实现, 这里就不给出了, 具体可参考维基¹.

位运算估计

这个方法算是相当高级的了, 但是也相当靠近计算机底层的算法, CS味道很浓, 这里只给出代码, 具体可参考Wikipedia². 代码也参考Wikipedia.

class Solution {
public:
    int mySqrt(int x) {
        // c?
        int c = 0;
        // d? which starts at the highest power of four <= n
        int d = 1 << 30; // The second-to-top bit is set.
                         // Same as ((unsigned) INT32_MAX + 1) / 2.
        while (d > x) d >>= 2;
        // for d? … d?
        while (d) {
            if (x >= c + d) {     // if X??? ≥ Y? then a? = 2?
                x -= c + d;       // X? = X??? - Y?
                c = (c >> 1) + d; // c??? = c?/2 + d? (a? is 2?)
            } else {
                c >>= 1; // c??? = c?/2      (a? is 0)
            }
            d >>= 2; // d??? = d?/4
        }
        return c; // c??
    }
};

实际执行速度并不快, 可能是因为编译器优化使得位运算的速度快的并不明显.

手算方法

这里先给出代码, 具体的内容可以参考我的另一篇文章:

class Solution {
public:
    int find_nice(int R, int b = 0) {
        int l{}, r{9};
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((20 * b + mid) * mid > R)
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l - 1;
    }
    int mySqrt(int n) {
        int dividend{}, quotient{}, reminder{}, i{};
        vector<int> a(10, 0);
        while (n) {
            a[i++] = n % 100;
            n /= 100;
        }
        for (int j = i - 1; j >= 0; --j) {
            dividend = reminder * 100 + a[j];
            int tmp = find_nice(dividend, quotient);
            reminder = dividend - (20 * quotient + tmp) * tmp;
            quotient = quotient * 10 + tmp;
        }
        return quotient;
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了36.80%的用户

看起来还是不错的, 并且是一种新方法, 我看大家的题解中并没有写过.

ref