高精度算法详解：从原理到加减乘除的完整实现

文章目录

一、为什么需要高精度算法
二、高精度算法的数据结构设计
- 2.1 基础工具函数
- 2.2 高精度加法实现
- 2.3 高精度减法实现
- 2.4 高精度乘法实现
- 2.5 高精度除法实现
三、完整测试程序
四、总结

一、为什么需要高精度算法

在编程中，处理极大数值是常见需求，例如：

密码学中的大数运算（如 RSA 算法中的模幂运算）
科学计算中的高精度数值计算
财务系统中的金额处理
数学竞赛中的大数问题求解

C++ 的原生数据类型（如long long）有固定数值范围限制（通常最大约 9×10^18），无法处理任意大小的整数。高精度算法通过将大数字拆分为多个小单元处理，以字符串或数组存储每一位数字，模拟手工计算实现各种运算。

二、高精度算法的数据结构设计

在 C++ 中，我们可以通过纯函数的方式实现高精度算法，避免使用类封装，使代码更加简洁直接。以下是各个核心功能的实现：

2.1 基础工具函数

首先实现一些基础工具函数，用于处理字符串表示的大数：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>// 反转字符串
std::string reverse(const std::string& s) {return std::string(s.rbegin(), s.rend());
}// 去除前导零
std::string removeLeadingZeros(const std::string& num) {int i = 0;while (i < num.size() - 1 && num[i] == '0') {i++;}return num.substr(i);
}// 判断是否为负数
bool isNegative(const std::string& num) {return num[0] == '-';
}// 获取绝对值
std::string getAbs(const std::string& num) {return isNegative(num) ? num.substr(1) : num;
}// 比较两个非负数字的大小
bool absGreaterOrEqual(const std::string& a, const std::string& b) {if (a.length() != b.length()) {return a.length() > b.length();}return a >= b;
}

2.2 高精度加法实现

高精度加法的核心思路是模拟手工加法运算，从低位到高位逐位相加并处理进位：

// 高精度加法
std::string add(const std::string& a, const std::string& b) {// 处理符号if (isNegative(a) && !isNegative(b)) {return subtract(b, getAbs(a));}if (!isNegative(a) && isNegative(b)) {return subtract(a, getAbs(b));}if (isNegative(a) && isNegative(b)) {return "-" + add(getAbs(a), getAbs(b));}// 两个正数相加std::string result;int carry = 0;int i = a.size() - 1;int j = b.size() - 1;while (i >= 0 || j >= 0 || carry > 0) {int sum = carry;if (i >= 0) sum += a[i--] - '0';if (j >= 0) sum += b[j--] - '0';result.push_back((sum % 10) + '0');carry = sum / 10;}return removeLeadingZeros(reverse(result));
}

2.3 高精度减法实现

高精度减法比加法更复杂，需要考虑借位和数字大小比较：

// 高精度减法
std::string subtract(const std::string& a, const std::string& b) {// 处理符号if (isNegative(a) && !isNegative(b)) {return "-" + add(getAbs(a), b);}if (!isNegative(a) && isNegative(b)) {return add(a, getAbs(b));}if (isNegative(a) && isNegative(b)) {return subtract(getAbs(b), getAbs(a));}// 两个正数相减if (!absGreaterOrEqual(a, b)) {return "-" + subtract(b, a);}std::string result;int borrow = 0;int i = a.size() - 1;int j = b.size() - 1;while (i >= 0) {int diff = (a[i] - '0') - borrow;if (j >= 0) diff -= (b[j] - '0');if (diff < 0) {diff += 10;borrow = 1;} else {borrow = 0;}result.push_back(diff + '0');i--;j--;}return removeLeadingZeros(reverse(result));
}

2.4 高精度乘法实现

高精度乘法通常采用竖式乘法的思路，时间复杂度为 O (n²)：

// 高精度乘法
std::string multiply(const std::string& a, const std::string& b) {// 处理零的情况if (a == "0" || b == "0") {return "0";}// 处理符号bool isNegative = (isNegative(a) && !isNegative(b)) || (!isNegative(a) && isNegative(b));std::string absA = getAbs(a);std::string absB = getAbs(b);// 结果数组，长度为两数位数之和std::vector<int> result(absA.size() + absB.size(), 0);// 竖式乘法核心逻辑for (int i = absA.size() - 1; i >= 0; i--) {for (int j = absB.size() - 1; j >= 0; j--) {int product = (absA[i] - '0') * (absB[j] - '0');int sum = product + result[i + j + 1];result[i + j + 1] = sum % 10;result[i + j] += sum / 10;}}// 转换结果数组为字符串std::string resultStr;for (int num : result) {if (!(resultStr.empty() && num == 0)) {resultStr.push_back(num + '0');}}return (isNegative ? "-" : "") + resultStr;
}

2.5 高精度除法实现

高精度除法是最复杂的运算，这里采用试商法实现：

// 高精度除法
std::string divide(const std::string& a, const std::string& b) {// 处理除数为零的情况if (b == "0") {throw std::runtime_error("Division by zero");}// 处理零的情况if (a == "0") {return "0";}// 处理符号bool isNegative = (isNegative(a) && !isNegative(b)) || (!isNegative(a) && isNegative(b));std::string absA = getAbs(a);std::string absB = getAbs(b);// 处理被除数小于除数的情况if (!absGreaterOrEqual(absA, absB)) {return "0";}// 试商法核心逻辑std::string quotient;std::string remainder;for (char c : absA) {remainder += c;remainder = removeLeadingZeros(remainder);int count = 0;while (absGreaterOrEqual(remainder, absB)) {remainder = subtract(remainder, absB);count++;}quotient += std::to_string(count);}quotient = removeLeadingZeros(quotient);return (isNegative ? "-" : "") + quotient;
}// 高精度取模
std::string mod(const std::string& a, const std::string& b) {if (b == "0") {throw std::runtime_error("Modulo by zero");}if (a == "0") {return "0";}bool isNegative = isNegative(a);std::string absA = getAbs(a);std::string absB = getAbs(b);if (!absGreaterOrEqual(absA, absB)) {return a;}std::string quotient = divide(absA, absB);std::string product = multiply(quotient, absB);std::string remainder = subtract(absA, product);return (isNegative ? "-" : "") + remainder;
}

三、完整测试程序

下面是一个完整的测试程序，展示如何使用上述高精度算法：

// 测试程序
int main() {try {// 测试加法std::cout << "加法测试: 12345 + 67890 = " << add("12345", "67890") << std::endl;// 测试减法std::cout << "减法测试: 98765 - 12345 = " << subtract("98765", "12345") << std::endl;// 测试乘法std::cout << "乘法测试: 1234 * 5678 = " << multiply("1234", "5678") << std::endl;// 测试除法std::cout << "除法测试: 123456789 / 12345 = " << divide("123456789", "12345") << std::endl;// 测试取模std::cout << "取模测试: 123456789 % 12345 = " << mod("123456789", "12345") << std::endl;// 测试负数运算std::cout << "负数测试:" << std::endl;std::cout << "-123 + 456 = " << add("-123", "456") << std::endl;std::cout << "123 - (-456) = " << subtract("123", "-456") << std::endl;std::cout << "-123 * (-456) = " << multiply("-123", "-456") << std::endl;std::cout << "-12345 / 67 = " << divide("-12345", "67") << std::endl;} catch (const std::exception& e) {std::cerr << "错误: " << e.what() << std::endl;return 1;}return 0;
}