文章目录
一、为什么需要高精度算法
在编程中，处理极大数值是常见需求，例如：
- 密码学中的大数运算（如 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;
}
四、总结
高精度算法是处理大数运算的基础，其核心在于：
- 将大数字拆分为小单元处理
- 模拟手工计算过程（进位、借位、试商等）
- 合理处理符号和边界情况
理解高精度算法不仅有助于解决实际问题，还能加深对数字运算本质的理解。在密码学、科学计算等领域，高精度算法更是不可或缺的基础工具。