背景
开根号（Square Root，√x）是计算机科学中一个极其基础、却又极具深度的问题。
在日常编程中，我们习惯直接调用：
sqrt(x);
但在以下场景中，自己实现 sqrt 算法是必须的：
- 操作系统 / 编译器 / 数学库开发
- 嵌入式系统（无标准库或浮点支持受限）
- 算法竞赛 / 面试（禁止使用库函数）
- 数值计算精度与性能优化
- 底层算法与计算机体系结构学习
很多开发者都会遇到这些问题：
sqrt内部是如何实现的？- 为什么不能直接暴力枚举？
- 浮点数误差如何控制？
- 整数开根号与浮点开根号有何区别？
- 牛顿迭代法为什么这么快？
因此，本项目的目标非常明确：
用 C++ 从零实现多种开根号（sqrt）算法，并系统讲清数学原理、数值特性与工程实现。
需求
本示例程序需要满足以下要求：
1. 功能需求
- 实现整数平方根
- 实现浮点平方根
- 不使用
sqrt()标准库函数 - 输出计算结果用于验证
2. 技术需求
- 使用 标准 C++
- 代码结构清晰、注释详细
- 所有代码放在 单一代码块
3. 算法覆盖
- 二分查找法
- 牛顿迭代法（Newton-Raphson）
- 对比不同方法的优缺点
相关技术
3.1 平方根的数学定义
平方根具有以下特点：
- 仅对 非负数 有实数解
- 单调递增
- 连续函数
3.2 整数平方根 vs 浮点平方根
| 类型 | 说明 |
|---|---|
| 整数平方根 | 返回不超过 √x 的最大整数 |
| 浮点平方根 | 返回近似实数值，允许误差 |
3.3 为什么不能直接枚举？
暴力枚举：
1², 2², 3², 4² ...
- 时间复杂度 O(√n)
- 数值大时效率极低
必须使用对数级算法（O(log n)）。
实现思路
本项目采用两种经典算法：
4.1 二分查找法（Binary Search）
核心思想
- √x 一定落在
[0, x]区间 - 利用单调性不断缩小范围
算法流程
left = 0, right = x
while left <= right:
mid = (left + right) / 2
if mid² == x → 找到
if mid² < x → left = mid + 1
else → right = mid - 1
4.2 牛顿迭代法（Newton-Raphson）
特点
- 收敛速度极快
- 工程中使用最广
- 浮点精度可控
完整实现代码
// =====================================================
// 文件名：SqrtImplementation.cpp
// 说明：C++ 实现平方根（不使用 sqrt 库函数）
// =====================================================
#include <iostream>
#include <cmath>
using namespace std;
// -----------------------------------------------------
// 方法一：二分查找法（整数平方根）
// 返回不超过 sqrt(x) 的最大整数
// -----------------------------------------------------
int SqrtBinary(int x) {
if (x < 0) return -1;
int left = 0;
int right = x;
int ans = 0;
while (left <= right) {
long long mid = left + (right - left) / 2;
long long sq = mid * mid;
if (sq == x) return mid;
else if (sq < x) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
// -----------------------------------------------------
// 方法二：牛顿迭代法（浮点平方根）
// eps：精度控制
// -----------------------------------------------------
double SqrtNewton(double x, double eps = 1e-6) {
if (x < 0) return -1.0;
if (x == 0) return 0.0;
double guess = x;
while (fabs(guess * guess - x) > eps) {
guess = 0.5 * (guess + x / guess);
}
return guess;
}
// -----------------------------------------------------
// 测试入口
// -----------------------------------------------------
int main() {
int n = 27;
double d = 27.0;
cout << "整数平方根（二分法）: " << SqrtBinary(n) << endl;
cout << "浮点平方根（牛顿法）: " << SqrtNewton(d) << endl;
return 0;
}
代码解读
1. SqrtBinary
- 使用二分查找
- 防止
mid * mid溢出 - 适合整数平方根问题
2. SqrtNewton
- 使用牛顿迭代法
- 通过 eps 控制精度
- 收敛速度快，工程常用
3. main
- 演示两种方法的使用
- 便于对比与验证
总结
通过本示例，你已经系统掌握了：
- 平方根的数学本质
- 整数与浮点 sqrt 的区别
- 二分查找在数值问题中的应用
- 牛顿迭代法的工程实现
- 数值精度与收敛控制方法
这类实现常见于：
- 面试高频算法题
- 标准库实现基础
- 数值计算与科学计算
- 底层系统开发
常见问题
Q1：牛顿法为什么收敛这么快？ A：属于二阶收敛，误差平方级下降。
Q2：为什么要用 long long？ A：防止 mid² 溢出 int 范围。
Q3：eps 取多大合适？
A：工程常用 1e-6 或 1e-8。
扩展方向与性能优化
- 实现 快速平方根倒数（Quake 算法）
- 定点数 sqrt（嵌入式）
- SIMD / 向量化优化
- GPU 并行 sqrt
- IEEE 754 浮点分析
- 与
std::sqrt源码对比