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

在編程中，處理極大數值是常見需求，例如：

• 密碼學中的大數運算（如 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 (n2)：

// 高精度乘法
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;
}

四、總結

高精度算法是處理大數運算的基礎，其核心在于：

• 將大數字拆分為小單元處理
• 模擬手工計算過程（進位、借位、試商等）
• 合理處理符號和邊界情況

理解高精度算法不僅有助于解決實際問題，還能加深對數字運算本質的理解。在密碼學、科學計算等領域，高精度算法更是不可或缺的基礎工具。