C++高精度算法实现详解
高精度算法用于处理超出标准数据类型范围的数值运算。以下将详细讲解加减乘除及开方的实现思路，并提供完整代码和测试示例。所有算法均基于字符串操作，支持任意长度非负整数运算。
一、高精度加法
思路：
- 从右至左逐位相加，记录进位
- 处理不等长数字
- 最终进位需添加
#include <algorithm>std::string highPrecisionAdd(std::string num1, std::string num2) {std::reverse(num1.begin(), num1.end());std::reverse(num2.begin(), num2.end());std::string result;int carry = 0;const size_t n = std::max(num1.size(), num2.size());for (size_t i = 0; i < n || carry; ++i) {int sum = carry;if (i < num1.size()) sum += num1[i] - '0';if (i < num2.size()) sum += num2[i] - '0';result.push_back(sum % 10 + '0');carry = sum / 10;}std::reverse(result.begin(), result.end());return result.empty() ? "0" : result; // 处理空结果
}
二、高精度减法
思路：
- 确保
num1 >= num2，否则交换并标记负号 - 从右至左逐位相减，处理借位
- 移除前导零
// 比较两个非负数字符串大小
bool isGreaterOrEqual(const std::string& a, const std::string& b) {if (a.size() != b.size()) return a.size() > b.size();for (int i = 0; i < a.size(); ++i) {if (a[i] != b[i]) return a[i] > b[i];}return true;
}std::string highPrecisionSub(std::string num1, std::string num2) {bool negative = false;if (!isGreaterOrEqual(num1, num2)) {std::swap(num1, num2);negative = true;}std::reverse(num1.begin(), num1.end());std::reverse(num2.begin(), num2.end());std::string result;int borrow = 0;const size_t n = num1.size();for (size_t i = 0; i < n; ++i) {int digit1 = num1[i] - '0' - borrow;int digit2 = (i < num2.size()) ? num2[i] - '0' : 0;borrow = 0;if (digit1 < digit2) {digit1 += 10;borrow = 1;}result.push_back(digit1 - digit2 + '0');}// 移除前导零并反转while (result.size() > 1 && result.back() == '0') result.pop_back();std::reverse(result.begin(), result.end());return (negative ? "-" : "") + result;
}
三、高精度乘法
思路：
- 双重循环遍历每位数字相乘
- 累加到结果数组对应位置
- 统一处理进位
std::string highPrecisionMul(const std::string& num1, const std::string& num2) {if (num1 == "0" || num2 == "0") return "0";const int n = num1.size(), m = num2.size();std::vector<int> res(n + m, 0);for (int i = n-1; i >= 0; --i) {int x = num1[i] - '0';for (int j = m-1; j >= 0; --j) {int y = num2[j] - '0';res[i+j+1] += x * y; // 关键：位置计算}}// 统一处理进位for (int k = n+m-1; k > 0; --k) {res[k-1] += res[k] / 10;res[k] %= 10;}// 转换为字符串std::string result;int start = res[0] ? 0 : 1; // 跳过前导零for (; start < n+m; ++start) {result.push_back(res[start] + '0');}return result;
}
四、高精度除法
思路：
- 从高位到低位逐位试商
- 用减法模拟试商过程
- 支持返回商和余数
std::pair<std::string, std::string> highPrecisionDiv(const std::string& dividend, const std::string& divisor) {if (divisor == "0") throw std::invalid_argument("Division by zero");std::string quotient;std::string current;std::string remainder;for (char ch : dividend) {current.push_back(ch);current.erase(0, current.find_first_not_of('0')); // 去除前导零if (current.empty()) current = "0";int count = 0;std::string tempDivisor = divisor;while (isGreaterOrEqual(current, tempDivisor)) {current = highPrecisionSub(current, tempDivisor);tempDivisor = divisor; // 重置除数++count;}quotient.push_back(count + '0');}quotient.erase(0, quotient.find_first_not_of('0'));remainder = current.empty() ? "0" : current;return {quotient.empty() ? "0" : quotient, remainder};
}
五、高精度开方（牛顿迭代法）
思路：
- 初始化近似值
- 迭代公式：
x_{n+1} = (x_n + S/x_n)/2 - 直到收敛
std::string highPrecisionSqrt(const std::string& s) {if (s[0] == '-') throw std::invalid_argument("Square root of negative number");if (s == "0") return "0";std::string x = s;std::string prev;while (prev != x) {prev = x;auto [quotient, remainder] = highPrecisionDiv(s, x);x = highPrecisionDiv(highPrecisionAdd(x, quotient), "2").first;// 处理前导零x.erase(0, x.find_first_not_of('0'));if (x.empty()) x = "0";}return x;
}
六、测试案例
int main() {// 加法测试std::cout << highPrecisionAdd("999", "9999"); // 输出10998// 减法测试std::cout << highPrecisionSub("1001", "999"); // 输出2// 乘法测试std::cout << highPrecisionMul("123456789", "987654321"); // 输出121932631137021795// 除法测试auto [q, r] = highPrecisionDiv("12345", "67");std::cout << q << " ... " << r; // 184 ... 17// 开方测试std::cout << highPrecisionSqrt("152399025"); // 输出12345return 0;
}
七、关键点解析
- 统一接口：所有函数接受和返回字符串，避免数值范围限制
- 前导零处理：在加减乘除中均需正确处理前导零
- 进位/借位机制：加法和乘法需要后处理进位，减法处理借位
- 除法复杂度：试商法时间复杂度为O(n²)，可采用更高效的算法（如二分法优化）
- 开方优化：牛顿迭代法二次收敛，通常10次迭代内即可达到千位精度
八、扩展功能建议
- 支持负数：在函数入口处处理符号位
- 小数运算：增加小数点位置记录，调整运算逻辑
- 性能优化：
- 使用
std::deque提高中间结果操作效率 - 实现Karatsuba快速乘法（复杂度O(n^1.585)）
- 使用
- 异常处理：完善除零、负数开方等异常检测
通过系统化的字符串操作和逐位模拟，高精度算法能够准确处理超大数运算问题。开发者可根据实际需求扩展功能或优化性能。