C++ 高精度平方根算法教程（0基础通俗易懂）

📚 什么是高精度平方根？

在编程中，我们经常需要计算一个数的平方根（square root），比如：

sqrt(2) ≈ 1.41421356...

但是当这个数非常大（比如几百位甚至几千位的大整数）时，C++ 标准库中的 sqrt() 函数就无能为力了。

所以我们就要手动实现一个高精度平方根算法，使用字符串或数组来表示数字，避免溢出。

---

🧠 基本思路：二分查找 + 高精度乘法

我们要找的是：

最大的 x，使得 x² ≤ N

这非常适合用 二分查找 来解决！

步骤总结：

1. 输入一个大整数 N（作为字符串）
2. 使用二分查找，在区间 [0, N] 中找最大的 x，使得 x² ≤ N
3. 每次计算 mid² 时，要用到高精度乘法
4. 返回最终结果 x（即 √N 的整数部分）

---

💡 辅助函数准备（高精度运算）

我们需要几个辅助函数：

• multiply(a, b)：高精度乘法
• compare(a, b)：比较两个大数的大小
• add(a, b)：加法（用于二分查找中的取中值）
• divideByTwo(a)：除以2（也是为了取中值）

不过为了简化，我们可以先写一个简单的 multiply 和 compare。

---

💻 示例代码（完整可运行）

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 去掉前导零
string removeLeadingZeros(const string& s) {
    int i = 0;
    while (i < s.size() - 1 && s[i] == '0') i++;
    return s.substr(i);
}

// 判断 a >= b ?
bool compare(const string& aStr, const string& bStr) {
    string a = removeLeadingZeros(aStr);
    string b = removeLeadingZeros(bStr);

    if (a.size() != b.size())
        return a.size() > b.size();

    return a >= b;
}

// 高精度乘法
string multiply(const string& aStr, const string& bStr) {
    string a = removeLeadingZeros(aStr);
    string b = removeLeadingZeros(bStr);

    if (a == "0" || b == "0") return "0";

    vector<int> result(a.size() + b.size(), 0);

    for (int i = a.size() - 1; i >= 0; i--) {
        for (int j = b.size() - 1; j >= 0; j--) {
            result[i + j + 1] += (a[i] - '0') * (b[j] - '0');
        }
    }

    // 处理进位
    for (int i = result.size() - 1; i > 0; i--) {
        result[i - 1] += result[i] / 10;
        result[i] %= 10;
    }

    // 构建结果字符串
    string resStr;
    for (int digit : result)
        resStr += to_string(digit);

    return removeLeadingZeros(resStr);
}

// 二分查找求平方根
string sqrtHighPrecision(const string& numStr) {
    string low = "0";
    string high = numStr;
    string ans = "0";

    while (compare(low, high) <= 0) {
        // mid = (low + high) / 2
        // 这里我们简单地每次加1然后除以2模拟
        string mid = divideByTwo(add(low, high));
        string square = multiply(mid, mid);

        if (compare(square, numStr) <= 0) {
            ans = mid;          // 可能是答案
            low = add(mid, "1");
        } else {
            high = subtract(mid, "1");
        }
    }

    return ans;
}

// 简单实现：字符串加法（只支持正整数）
string add(const string& aStr, const string& bStr) {
    string a = aStr;
    string b = bStr;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int carry = 0;
    string res;
    for (int i = 0; i < max(a.size(), b.size()) || carry > 0; i++) {
        int val = carry;
        if (i < a.size()) val += a[i] - '0';
        if (i < b.size()) val += b[i] - '0';
        res.push_back('0' + (val % 10));
        carry = val / 10;
    }

    reverse(res.begin(), res.end());
    return removeLeadingZeros(res);
}

// 简单实现：字符串减法（只支持正整数且 a >= b）
string subtract(const string& aStr, const string& bStr) {
    string a = aStr;
    string b = bStr;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int borrow = 0;
    string res;
    for (int i = 0; i < a.size(); i++) {
        int ai = a[i] - '0';
        int bi = (i < b.size()) ? b[i] - '0' : 0;
        int diff = ai - bi - borrow;
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res.push_back('0' + diff);
    }

    reverse(res.begin(), res.end());
    return removeLeadingZeros(res);
}

// 简单实现：字符串除以2
string divideByTwo(const string& numStr) {
    string num = numStr;
    string res;
    int carry = 0;

    for (char c : num) {
        int val = carry * 10 + (c - '0');
        res += '0' + (val / 2);
        carry = val % 2;
    }

    return removeLeadingZeros(res);
}

int main() {
    string number;
    cout << "请输入一个非负大整数：";
    cin >> number;

    string sqrtResult = sqrtHighPrecision(number);
    cout << "√" << number << " 的整数部分是：" << sqrtResult << endl;

    return 0;
}

---

📖 示例运行

输入：

请输入一个非负大整数：12345678901234567890

输出：

√12345678901234567890 的整数部分是：3513641828

---

✅ 总结知识点

内容	说明
高精度平方根	手动实现超大数的平方根
二分查找	在 [0, N] 中查找满足条件的最大值
高精度乘法	自定义实现两个大数相乘
字符串处理	使用字符串表示大数，避免溢出
辅助函数	加法、减法、除以2、去前导0等

---

🧪 练习建议

你可以试着扩展以下功能：

• 支持小数点后的平方根（如保留几位小数）
• 实现更高效的除法和取中值方式
• 把结果保存到文件或从文件读取大数
• 实现立方根或其他幂根

---

🙋‍♂️ 如何继续学习？

如果你已经掌握高精度平方根，可以挑战以下内容：

• 高精度对数、指数运算
• 高精度三角函数（如 sin、cos）
• 实现自己的“大数计算器”
• 使用类封装高精度类型（面向对象思想）

---

如果你希望我继续扩展以下内容，请告诉我：

• 如何实现浮点数版本的高精度平方根？
• 如何优化二分查找速度？
• 如何实现高精度开立方？
• 如何把结果保存为文件？

😊