C++ 手撕 Sqrt 开根号算法详解与源码实现

C++ 手撕 Sqrt 开根号算法详解

在计算机科学中，开根号（Square Root）看似简单，实则蕴含不少门道。日常开发里我们习惯直接调用 sqrt(x)，但在某些特定场景下，自己实现这个算法是必须的。比如操作系统或编译器底层库开发、嵌入式系统（无标准库支持）、算法竞赛禁止使用库函数，或者是为了优化数值计算的精度与性能。

很多开发者会好奇：sqrt 内部到底怎么算的？为什么不能暴力枚举？浮点误差怎么控制？今天我们就用 C++ 从零实现两种经典的开根号算法，并讲清楚背后的数学原理和工程细节。

为什么不能直接枚举？

暴力枚举的思路很简单：从 1 开始试，直到 $i^2 > x$。但时间复杂度是 $O(\sqrt{n})$，当数值很大时效率极低。我们需要的是对数级算法（$O(\log n)$）。

核心算法思路

这里主要介绍两种方法：二分查找法和牛顿迭代法。

1. 二分查找法（适合整数）

核心思想是利用单调性。$\sqrt{x}$ 一定落在 [0, x] 区间内。通过不断取中间值 mid，比较 mid * mid 与 x 的大小来缩小范围。

注意：计算 mid * mid 时容易溢出 int 范围，所以中间变量要用 long long。

2. 牛顿迭代法（适合浮点）

这是工程中用得最广的方法，收敛速度极快（二阶收敛）。公式为： $$x_{n+1} = \frac{1}{2}(x_n + \frac{S}{x_n})$$ 只要初始猜测值不太离谱，几次迭代就能达到很高的精度。

核心代码实现

// =====================================================
// 文件名：SqrtImplementation.cpp
// 说明：C++ 实现平方根（不使用 sqrt 库函数）
// =====================================================
#include <iostream>
#include <cmath>
using namespace std;

// -----------------------------------------------------
// 方法一：二分查找法（整数平方根）
// 返回不超过 sqrt(x) 的最大整数
// -----------------------------------------------------
int SqrtBinary(int x) {
    if (x < 0) return -1;
    int left = ;
     right = x;
     ans = ;
     (left <= right) {
          mid = left + (right - left) / ;
          sq = mid * mid;
         (sq == x)  mid;
          (sq < x) {
            ans = mid;
            left = mid + ;
        }  {
            right = mid - ;
        }
    }
     ans;
}





{
     (x < )  ;
     (x == )  ;
     guess = x;
     ((guess * guess - x) > eps) {
        guess =  * (guess + x / guess);
    }
     guess;
}




{
     n = ;
     d = ;
    cout <<  << (n) << endl;
    cout <<  << (d) << endl;
     ;
}