高精度计算：从原理到实现，掌握大数运算的核心算法

1. 为什么我们需要“大数模拟”在编程的世界里我们习惯了int、long long这些内置数据类型。它们就像我们日常使用的计算器处理日常的加减乘除得心应手。但是你有没有遇到过这样的情况当你想计算一个天文数字比如 1000 的阶乘1000!或者处理两个几百位长的整数相加时你的程序突然“罢工”了或者给出了一个完全错误、莫名其妙的负数结果这不是你的代码逻辑错了而是你碰到了计算机内置整数类型的“天花板”。以 C 中常用的long long为例它通常能表示的最大整数大约是 9.2×10¹⁸。这个数字看起来很大但在计算组合数、大数阶乘、RSA 加密解密或者某些竞赛题目中动辄就是几百位甚至上千位的数字long long连它的零头都装不下。这时程序就会发生“溢出”导致结果错误。那么计算机真的无法处理这些大数字吗当然不是。计算机的“笨”在于它只能处理有限位数的数字但我们可以通过“模拟”人脑的竖式计算过程让计算机也能处理任意长度的数字。这就是“大数模拟”或“高精度计算”的核心思想我们不依赖语言提供的大整数类型而是自己用数组或字符串来“模拟”一个数字的每一位并手动实现这个数字的加、减、乘、除等运算规则。这听起来很基础甚至有些“笨拙”但它却是理解计算机如何“思考”运算的绝佳窗口也是算法竞赛和许多底层库如 Python 的int类型底层实现的基石。掌握了它你不仅解决了大数计算问题更深刻理解了运算的本质。2. 高精度数字的“容器”如何存储一个大数在动手写运算之前我们首先要解决存储问题。如何把一个像“12345678901234567890”这样的数字放进程序里最直观的想法是用字符串string存储。字符串可以轻松处理任意长度输入输出也方便。但是进行运算时我们需要频繁访问每一位并进行数字计算字符串的字符需要转换成数字计算完再转回字符这会产生额外的开销。因此更高效、更通用的做法是使用整型数组。数组的每个元素存储大数的一位数字。这里就面临两个关键设计选择2.1 正序存储 vs 倒序存储正序存储数组下标 0 存储最高位下标 n-1 存储最低位。这符合人类的阅读习惯。数字 12345 - 数组 [1, 2, 3, 4, 5]缺点在进行加法、乘法运算时我们是从最低位开始计算的如果结果产生进位这个进位需要加到更高位。在正序存储中向数组头部高位插入一个进位是非常低效的操作需要移动后面所有元素。倒序存储数组下标 0 存储最低位下标 n-1 存储最高位。这是高精度算法的标准做法。数字 12345 - 数组 [5, 4, 3, 2, 1]优点运算时我们从数组下标 0 开始处理自然就是从最低位开始计算。如果产生进位只需要将其加到下一位即当前下标1的位置这个操作是顺序的非常高效。输出时只需要将数组倒序输出即可。结论为了运算方便我们一律采用倒序存储。2.2 数组的“位宽”一位存一个数字还是一位存多个数字在倒序存储的基础上我们还可以进一步优化。数组的每个元素比如 C 的int能存储很大的值约21亿而我们只用它存 0-9 这一个数字无疑是巨大的浪费。这会导致数组长度很长循环次数多效率低。因此常见的优化是压位高精度。即数组的每一个元素存储大数的多位十进制数字。不压位每个int存 1 位十进制数0-9。数组长度等于数字位数。压位每个int存 4 位十进制数0-9999。那么一个 1000 位的数字只需要一个长度约为 250 的数组即可。乘法、加法运算的循环次数大大减少。压位的选择4位、8位、9位需要权衡位数越多单次运算更快但要注意不能超过所选整数类型的最大值且乘法的中间结果也可能溢出。对于入门我们先从最基础的“不压位”开始理解原理。在模板部分我会给出压位的思路。2.3 代码中的定义我们用一个vectorint来存储这个倒序的大数。同时为了处理负数高精度减法会涉及我们通常用一个独立的bool变量is_negative来标记正负。但在最基础的模板中我们先处理非负整数。一个典型的结构定义如下以 C 为例struct BigInt { vectorint digits; // 倒序存储每一位数字每个元素范围 0-9不压位 bool is_negative false; // 构造函数从字符串初始化 BigInt(const string s) { // 例如 s 12345 for (int i s.size() - 1; i 0; --i) { digits.push_back(s[i] - 0); // 倒序存入 [5, 4, 3, 2, 1] } // 这里可以添加处理负号‘-’的逻辑 trim(); // 去除前导零保证数字表示规范 } // 辅助函数去除前导零例如 [0,0,1,2,3] - [3,2,1] void trim() { while (digits.size() 1 digits.back() 0) { digits.pop_back(); } if (digits.empty()) digits.push_back(0); // 防止数字为 0 时被清空 } // 输出函数 string to_string() const { string res; if (is_negative) res -; for (int i digits.size() - 1; i 0; --i) { res char(digits[i] 0); } return res; } };这个BigInt结构体就是我们高精度运算的基石。接下来的所有运算都是对这个digits数组进行操作。3. 高精度加法从竖式计算到代码实现加法是最基础的运算。我们来回顾一下小学的竖式计算1 2 3 4 5 ------- 1 6 8计算过程从最低位个位开始358写8十位 246写6百位 10补位1写1。在代码中我们需要模拟这个过程并处理好进位。3.1 算法步骤假设有两个BigInt对象 A 和 B已倒序存储即A.digits[0]是个位。初始化一个空的结果BigIntC以及一个carry进位变量初始为 0。从最低位下标 i0开始遍历两个数字的每一位直到处理完较长的那个数字。当前位的和sum A_i B_i carry。如果某数字已没有更多位则其对应位为 0。当前位的结果是sum % 10存入 C。新的进位是sum / 10整除。循环结束后如果最后的carry不为 0则需要将其作为新的最高位加入 C。调用C.trim()去除可能的前导零虽然加法通常不会产生但规范操作是好的习惯。3.2 代码实现与逐行解析BigInt operator(const BigInt A, const BigInt B) { BigInt C; // 结果 int carry 0; // 进位 int max_len max(A.digits.size(), B.digits.size()); for (int i 0; i max_len || carry; i) { // 获取当前位如果索引超出范围则视为0 int digitA (i A.digits.size()) ? A.digits[i] : 0; int digitB (i B.digits.size()) ? B.digits[i] : 0; int sum digitA digitB carry; C.digits.push_back(sum % 10); // 当前位结果 carry sum / 10; // 新的进位 } // 注意循环条件 i max_len || carry 确保了即使最高位计算完还有进位也会多进行一次循环处理。 C.trim(); return C; }3.3 一个具体的计算示例让我们手动模拟一下123 45的过程A [3, 2, 1], B [5, 4]i0: digitA3, digitB5, carry0 - sum8 - C[8], carry0i1: digitA2, digitB4, carry0 - sum6 - C[8,6], carry0i2: digitA1, digitB0, carry0 - sum1 - C[8,6,1], carry0循环结束i2等于max_len3且carry0。结果 C 倒序输出为 “168”正确。实操心得加法是最高频的运算也是理解进位机制的关键。这里的for循环条件i max_len || carry是一个精巧的设计它把“处理完所有位”和“处理最后的进位”统一到了一个循环里代码更简洁。务必理解这个条件是如何工作的。4. 高精度减法借位的艺术与比较的重要性减法比加法复杂一点因为它涉及“借位”。同时我们必须先判断两个数谁大谁小因为A - B当A B时结果为负。我们先实现一个不考虑符号只计算大数减小数的辅助函数。4.1 算法步骤假设 A B初始化结果 C 和借位borrow为 0。遍历 A 的每一位因为 A B结果位数不会超过 A。当前位计算diff A.digits[i] - borrow。先减去上一位的借位。如果i B.digits.size()则diff - B.digits[i]。如果diff 0说明不够减需要向高位借位。则diff 10, 并设置borrow 1。否则borrow 0。将diff存入 C。循环结束后调用C.trim()去除前导零。4.2 比较函数与带符号减法在实现完整减法前我们需要一个比较两个BigInt绝对值大小的函数忽略符号。// 比较两个 BigInt 的绝对值大小。返回 1 表示 AB, 0 表示 AB, -1 表示 AB int compare_abs(const BigInt A, const BigInt B) { if (A.digits.size() ! B.digits.size()) { return A.digits.size() B.digits.size() ? 1 : -1; } for (int i A.digits.size() - 1; i 0; --i) { // 从最高位开始比 if (A.digits[i] ! B.digits[i]) { return A.digits[i] B.digits[i] ? 1 : -1; } } return 0; // 完全相等 }现在我们可以实现完整的减法运算符BigInt operator-(const BigInt A, const BigInt B) { BigInt C; int cmp compare_abs(A, B); if (cmp 0) { // 绝对值相等结果为0 return BigInt(0); } const BigInt* pLarger nullptr; const BigInt* pSmaller nullptr; bool result_negative false; if (cmp 0) { // |A| |B| pLarger A; pSmaller B; result_negative (A.is_negative ! B.is_negative) ? A.is_negative : false; // 同号相减符号同大数异号相减等同于绝对值相加符号同被减数A。 // 这里简化处理我们先处理非负数符号逻辑是完整的减法中最复杂部分初期可跳过。 } else { // |A| |B| pLarger B; pSmaller A; result_negative !( (A.is_negative ! B.is_negative) ? A.is_negative : false ); // 结果取反 } // 调用辅助函数计算 |larger| - |smaller| C subtract_abs(*pLarger, *pSmaller); // 假设有这个辅助函数 C.is_negative result_negative; C.trim(); return C; } // 辅助函数计算 |A| - |B| 调用方保证 |A| |B| BigInt subtract_abs(const BigInt A, const BigInt B) { BigInt C; int borrow 0; for (int i 0; i A.digits.size(); i) { int diff A.digits[i] - borrow; if (i B.digits.size()) { diff - B.digits[i]; } if (diff 0) { diff 10; borrow 1; } else { borrow 0; } C.digits.push_back(diff); } // 因为 |A| |B|最后 borrow 一定是 0 C.trim(); return C; }4.3 减法示例计算 123 - 45A [3,2,1], B[5,4]i0: diff 3 - 0 3, 减去 B[0]5 - diff-2 0 - diff8, borrow1, C[8]i1: diff 2 - 1 1, 减去 B[1]4 - diff-3 0 - diff7, borrow1, C[8,7]i2: diff 1 - 1 0, B 无此位 - diff0, borrow0, C[8,7,0]trim 后 C[8,7]倒序输出 “78”正确。踩坑提醒减法最易错的地方在于借位的处理顺序。一定要先减去上一位的借位borrow再减去当前减数的位。如果先减减数位发现不够再试图借位逻辑会混乱尤其是在连续借位的情况下。记住口诀“先还旧债减 borrow再算新账减 B[i]不够再借”。5. 高精度乘法从朴素算法到压位优化高精度乘法通常指一个大整数乘以一个小整数BigInt * int或者两个大整数相乘BigInt * BigInt。我们先实现更常用的BigInt * int它是实现BigInt * BigInt的基础。5.1 高精度 × 低精度BigInt * int这个场景非常常见比如计算阶乘n!就是连续乘以1, 2, 3, ..., n。算法思路和加法类似但进位可能不止一位因为乘数可以是很大的int。BigInt operator*(const BigInt A, int b) { if (b 0) return BigInt(0); BigInt C; long long carry 0; // 使用 long long 防止中间结果溢出 for (int i 0; i A.digits.size() || carry; i) { if (i A.digits.size()) { carry (long long)A.digits[i] * b; } C.digits.push_back(carry % 10); carry / 10; } C.trim(); return C; }示例计算 123 * 45我们可以用123 * 40 123 * 5来理解但算法是直接逐位乘。b45carry类型是long long很重要因为9*45405不会溢出但如果是BigInt * BigInt的中间步骤可能需要更大的类型。5.2 高精度 × 高精度BigInt * BigInt这就是模拟竖式乘法。我们把其中一个乘数 B 的每一位看作一个“低精度数”分别与另一个乘数 A 相乘然后将结果错位相加。1 2 3 (A) × 4 5 (B) -------- 6 1 5 (123 * 5) 4 9 2 0 (123 * 40即123*4后左移一位) -------- 5 5 3 5在代码中我们用一个中间结果数组temp来存储每次部分积然后累加到最终结果。BigInt operator*(const BigInt A, const BigInt B) { BigInt C(0); vectorint temp(A.digits.size() B.digits.size(), 0); // 积的位数最多为 len(A)len(B) // 双重循环模拟竖式 for (int i 0; i A.digits.size(); i) { int carry 0; for (int j 0; j B.digits.size() || carry; j) { // 计算当前位的结果并加上之前的进位 long long product temp[i j] (long long)A.digits[i] * (j B.digits.size() ? B.digits[j] : 0) carry; temp[i j] product % 10; carry product / 10; } } // 将 temp 数组转换为 BigInt C C.digits.assign(temp.begin(), temp.end()); C.trim(); return C; }关键解析temp[ij]这个索引是精髓。当乘数 A 的第i位实际是A.digits[i]对应10^i与乘数 B 的第j位10^j相乘时其结果会贡献到最终结果的第ij位10^(ij)。这正是竖式乘法中“错位相加”的体现。5.3 压位优化初探上述朴素乘法的时间复杂度是 O(n²)当数字位数很长时比如10万位效率很低。压位高精度可以显著提升速度。假设我们采用“万进制”即数组的每个元素存储 0-99994位十进制数。那么存储时我们需要将输入的字符串每4位一组转换成整数存入数组注意最后不足4位的处理。加法、减法的逻辑基本不变只是进位基数从10变成了10000。乘法的变化最大也最体现优化效果。两个“万进制”数相乘temp数组每个位置可能的最大值是9999*9999 ≈ 1e8远小于int的极限。我们使用long long作为中间计算类型即可。循环次数从(位数/1)²减少到(位数/4)²理论上速度提升约16倍。性能心得在算法竞赛中如果题目明确数字范围极大如 10^100000压位高精度几乎是必选项。实现压位的核心难点在于输入输出的进制转换以及确保所有中间运算不溢出。建议在彻底理解不压位版本后再挑战压位实现。6. 高精度除法最复杂的运算高精度除法主要有两种高精度 / 低精度求商和余数和高精度 / 高精度。前者相对简单应用也更广泛如进制转换后者非常复杂通常需要结合试商、减法或牛顿迭代法等。6.1 高精度 ÷ 低精度BigInt / int我们模拟的是竖式除法。从被除数最高位开始逐位处理将当前位并入“当前余数”remainder remainder * 10 current_digit。计算当前位的商quotient_digit remainder / divisor。计算新的余数remainder remainder % divisor。将商 digit 存入结果。重复直到所有位处理完。// 返回商余数通过参数 r 返回 BigInt divide(const BigInt A, int b, int r) { // r 是余数 BigInt C; r 0; // 余数 // 注意除法是从最高位开始算而我们的 digits 是倒序存储最低位在前。 // 所以我们需要从后往前遍历。 for (int i A.digits.size() - 1; i 0; --i) { r r * 10 A.digits[i]; C.digits.push_back(r / b); r % b; } // 此时 C.digits 是正序存储的商因为我们是按从高到低的顺序push_back的 // 我们需要将其反转以符合我们的倒序存储约定。 reverse(C.digits.begin(), C.digits.end()); C.trim(); return C; }示例计算 12345 ÷ 97初始 r0。处理最高位1: r0*1011, 商1/970, r1%971。C[0]。处理下一位2: r1*10212, 商12/970, r12。C[0,0]。处理3: r12*103123, 商123/971, r123%9726。C[0,0,1]。处理4: r26*104264, 商264/972, r264%9770。C[0,0,1,2]。处理5: r70*105705, 商705/977, r705%9726。C[0,0,1,2,7]。反转 C 得到 [7,2,1,0,0]trim 后为 [7,2,1]对应商 127余数 26。验算127*9726123192612345正确。6.2 高精度 ÷ 高精度BigInt / BigInt这是高精度运算中最难的部分。朴素的方法是模拟竖式除法不断用被除数减去除数直到不够减减的次数就是商。但这样效率极低O(商)次减法。更高效的方法是试商法。核心思想是估计商的每一位。将被除数和除数对齐使除数左移到与被除数最高几位长度相近。估计这一位的商。这是一个难点估计值可能在 0-9 之间但需要快速准确地确定。通常通过除数的前两位和被除数的前三位来估算但需要处理边界情况。用估计的商乘以除数得到一个临时乘积。比较临时乘积和当前被除数部分。如果太大则将商减1重新计算乘积并比较直到乘积不大于当前被除数部分。从当前被除数部分减去这个乘积得到新的被除数部分。将确定的商位存入结果。重复上述过程直到所有位处理完。由于实现复杂且代码较长这里不展开完整代码但给出核心的试商逻辑伪代码和注意事项// 伪代码展示试商思想 BigInt divide_big(const BigInt A, const BigInt B) { if (compare_abs(A, B) 0) return BigInt(0); // A B // 1. 规范化确保除数 B 足够大方便估算 // 2. 逐位求商 BigInt current_dividend A; // 当前被除数 BigInt quotient; int shift A.digits.size() - B.digits.size(); // 对齐的偏移量 for (int i shift; i 0; --i) { // 构造当前用于试商的被除数部分 (current_part) // 估算商 digit_guess (0-9) int digit_guess estimate_quotient_digit(current_part, B); // 调整商 digit_guess (通过减法验证) while (is_too_large(digit_guess, current_part, B)) { digit_guess--; } // 计算 partial_product B * digit_guess // current_part current_part - partial_product // 更新 current_dividend // 将 digit_guess 加入 quotient 的对应位 } quotient.trim(); return quotient; }避坑指南高精度除法的试商是极易出错的地方。估算的商可能比实际商大1或大2。一个稳健的策略是先用除数的最高位和次高位、被除数部分的前三位做一个快速除法来估算然后通过一次或两次减法来修正。务必在修正循环后验证current_part是否小于除数 B这是循环终止的正确条件。网上有很多现成的模板但理解其原理和调试过程对你掌握高精度运算有质的提升。7. 综合模板与实战应用将上述所有运算封装成一个完整的、可用的BigInt类是学习的最终目标。下面提供一个基础框架模板不含压位和完整符号处理但结构清晰#include iostream #include vector #include string #include algorithm using namespace std; struct BigInt { vectorint digits; bool is_negative false; // 构造函数 BigInt() {} BigInt(const string s) { from_string(s); } BigInt(long long num) { from_string(to_string(num)); } void from_string(const string s) { digits.clear(); int start 0; if (s[0] -) { is_negative true; start 1; } for (int i s.size() - 1; i start; --i) { digits.push_back(s[i] - 0); } trim(); } void trim() { while (digits.size() 1 digits.back() 0) digits.pop_back(); if (digits.empty()) digits.push_back(0); if (digits.size() 1 digits[0] 0) is_negative false; // 规范0 非负 } string to_string() const { string res; if (is_negative) res -; for (int i digits.size() - 1; i 0; --i) res char(digits[i] 0); return res; } // 比较绝对值 int compare_abs(const BigInt other) const { if (digits.size() ! other.digits.size()) { return digits.size() other.digits.size() ? 1 : -1; } for (int i digits.size() - 1; i 0; --i) { if (digits[i] ! other.digits[i]) { return digits[i] other.digits[i] ? 1 : -1; } } return 0; } // 加法 (假设均为非负或已处理好符号) BigInt operator(const BigInt other) const { // 符号处理逻辑略此处实现绝对值相加 BigInt result; int carry 0; int max_len max(digits.size(), other.digits.size()); for (int i 0; i max_len || carry; i) { int d1 (i digits.size()) ? digits[i] : 0; int d2 (i other.digits.size()) ? other.digits[i] : 0; int sum d1 d2 carry; result.digits.push_back(sum % 10); carry sum / 10; } result.trim(); return result; } // 减法 (this - other)简化版假设 this other 且均为非负 BigInt operator-(const BigInt other) const { BigInt result; int borrow 0; for (int i 0; i digits.size(); i) { int diff digits[i] - borrow; if (i other.digits.size()) diff - other.digits[i]; if (diff 0) { diff 10; borrow 1; } else { borrow 0; } result.digits.push_back(diff); } result.trim(); return result; } // 乘法 (this * int) BigInt operator*(int b) const { if (b 0) return BigInt(0); BigInt result; long long carry 0; for (int i 0; i digits.size() || carry; i) { if (i digits.size()) carry (long long)digits[i] * b; result.digits.push_back(carry % 10); carry / 10; } result.trim(); return result; } // 除法 (this / int)返回商余数通过参数返回 BigInt divide(int b, int remainder) const { BigInt result; remainder 0; for (int i digits.size() - 1; i 0; --i) { remainder remainder * 10 digits[i]; result.digits.push_back(remainder / b); remainder % b; } reverse(result.digits.begin(), result.digits.end()); result.trim(); return result; } }; // 重载输入输出流 istream operator(istream is, BigInt num) { string s; is s; num.from_string(s); return is; } ostream operator(ostream os, const BigInt num) { os num.to_string(); return os; } int main() { // 示例计算 100! BigInt fact(1); for (int i 1; i 100; i) { fact fact * i; } cout 100! fact endl; // 示例大数加法 BigInt a(12345678901234567890); BigInt b(98765432109876543210); cout a b (a b) endl; return 0; }7.1 实战应用场景阶乘与组合数计算这是最经典的例子。n!的增长速度极快20!就已经超出long long范围。高精度是唯一选择。斐波那契数列大项第几百甚至几千项的斐波那契数位数惊人。RSA等加密算法涉及超大素数的生成和模幂运算底层依赖高精度整数库。进制转换特别是涉及大数的进制转换需要用到高精度除法和取模。算法竞赛题目许多题目会直接要求处理“超过64位整数范围”的数字。7.2 从基础模板到工业级实现我们实现的这个模板是“究极基础”的它帮助你理解了所有核心原理。但在实际应用或追求高性能时还需要考虑符号的完整处理为所有运算 - *加入符号判断逻辑。压位存储将vectorint改为vectorlong long每个元素存储多位如9位并重写所有运算的进位/借位逻辑基数变为 1e9。更高效的乘法实现 Karatsuba 算法或 FFT快速傅里叶变换算法将乘法复杂度从 O(n²) 降到 O(n^log3) 或 O(n log n)用于处理数万位以上的乘法。更高效的除法实现牛顿迭代法求倒数再转换为乘法。内存管理避免频繁的向量扩容和拷贝。理解了这个基础模板你就掌握了高精度运算的“任督二脉”。以后遇到任何大数问题你都能清晰地知道数据如何流动、运算如何发生并能有方向地去优化和调试。这远比直接套用一个黑盒模板有价值得多。