1. 项目概述为什么我们需要高精度算法在C的日常开发中我们最常接触的整数类型是int、long long这些内置类型。int通常是32位能表示大约 ±21亿的范围long long是64位能表示大约 ±9.2×10¹⁸ 的范围。这个范围对于绝大多数应用场景来说已经足够比如计算商品价格、统计用户数量、处理时间戳等等。但总有一些场景这些“常规”的整数类型会显得力不从心。比如你需要计算一个100位的质数或者处理金融领域精确到小数点后很多位的超大金额运算又或者是在密码学中计算像RSA加密算法里那种几百位甚至上千位的大整数模幂运算。在这些场景下内置的整数类型直接“溢出”了计算结果会变得毫无意义。这就是高精度算法Arbitrary-Precision Arithmetic也叫大整数运算的用武之地。它的核心思想很简单既然一个变量装不下这么大的数那我就用多个变量通常是一个数组来模拟一个“超级整数”。数组的每一个元素比如一个int只存储这个超大整数的一位或几位比如十进制的一位或者四位然后通过模拟我们小学就学过的竖式计算加、减、乘、除来实现任意精度的数学运算。听起来是不是有点“返璞归真”没错高精度算法的本质就是把我们手算的过程用代码精确地复现出来。它不依赖于任何特殊的硬件指令纯粹是算法和数据结构的艺术。对于C程序员尤其是参加算法竞赛如NOIP/NOI、ACM-ICPC的同学来说高精度是必须掌握的基本功。它能帮你解决那些看似“简单”但数据范围巨大的题目也是理解计算机如何进行底层数值计算的一个绝佳窗口。2. 核心设计如何用数组表示一个大整数在动手写代码之前我们必须先解决一个最基础的问题如何在计算机内存中表示一个理论上可以无限长受限于内存的整数2.1 存储结构的选择最直观的想法是用一个字符数组char[]或者整数数组int[]来存储。每个元素代表数字的一位。这里有一个关键的设计决策数字的高位和低位在数组中应该如何对应假设我们要存储数字123456789。方案A高位在前a[0]1, a[1]2, a[2]3, ..., a[8]9方案B低位在前a[0]9, a[1]8, a[2]7, ..., a[8]1强烈推荐使用方案B即低位在前Little-Endian的存储方式。为什么与运算顺序天然匹配我们做竖式加法、减法、乘法时都是从最低位开始计算的。低位在数组开头意味着我们的循环可以从i0开始顺序处理逻辑清晰代码简洁。处理长度变化方便做加法或乘法时结果的长度可能会增加比如99911000从3位变成了4位。如果低位在前我们只需要在数组的“后面”更高索引处追加进位即可。如果高位在前长度增加意味着需要在数组“前面”插入新的位这通常需要移动大量元素效率低下。所以我们的存储约定是声明一个足够大的整型数组int num[MAX_LEN]其中num[0]存储的是个位数num[1]存储十位数以此类推。同时我们需要一个变量来记录这个数字实际的长度有效位数避免处理一堆前导零。2.2 输入与输出的处理输入通常是一个字符串。我们需要将这个字符串转换成我们内部的数组表示。const int MAX_LEN 1005; // 预设最大位数比如1000位十进制数 struct BigInt { int digits[MAX_LEN]; // 存储每一位digits[0]是个位 int len; // 有效长度 bool sign; // 符号位true为负暂不考虑先处理非负 BigInt() { // 构造函数初始化为0 memset(digits, 0, sizeof(digits)); len 1; // 0的长度记为1 } // 从字符串构造 BigInt(const char* s) { memset(digits, 0, sizeof(digits)); len strlen(s); // 字符串是高位在前需要反向存入数组低位在前 for (int i 0; i len; i) { digits[i] s[len - 1 - i] - 0; // 字符转数字 } // 处理前导零比如输入 000123 while (len 1 digits[len-1] 0) { len--; } } };输出函数则是逆过程从最高位digits[len-1]开始依次输出到最低位digits[0]。void BigInt::print() const { for (int i len - 1; i 0; i--) { printf(%d, digits[i]); } if (len 0) printf(0); // 保险起见 }注意这里有一个初学者极易踩的坑。当我们从字符串s转换时s[0]是最高位。如果直接digits[i] s[i] - 0就变成了高位在前与后续运算逻辑冲突。务必记住digits[i] s[len - 1 - i] - 0这个反向操作。3. 四则运算的模拟实现存储问题解决后我们就可以开始实现最核心的运算了。我们将按照加、减、乘、除的顺序由易到难地实现。3.1 高精度加法加法的逻辑最直接就是模拟竖式加法对应位相加加上低位的进位然后处理当前位的进位。BigInt BigInt::add(const BigInt other) const { BigInt result; int carry 0; // 进位 // 结果的长度最大为 max(len, other.len) 1 for (int i 0; i max(len, other.len) || carry; i) { if (i len) carry digits[i]; if (i other.len) carry other.digits[i]; result.digits[result.len] carry % 10; // 当前位结果 carry / 10; // 新的进位 } // 如果最后还有进位len已经在循环中增加了 return result; }关键点解析for循环的终止条件是i max(len, other.len) || carry。这意味着即使两个数的位都加完了只要还有进位比如9991循环就要继续为结果增加新的最高位。carry变量非常巧妙它同时承担了“临时和”与“进位”两个角色。在每一轮循环中它先累加两个操作数当前位的值然后carry % 10成为结果位carry / 10成为下一轮的进位。result.len在赋值的同时自增最后自然就是结果的正确长度。3.2 高精度减法减法比加法稍微复杂一点因为涉及到借位并且要处理结果为负的情况。我们先实现一个前提this必须大于等于other即保证结果非负。我们可以先实现一个比较函数。// 比较绝对值大小this other 返回1等于返回0小于返回-1 int BigInt::compare(const BigInt other) const { if (len ! other.len) { return len other.len ? 1 : -1; } for (int i len - 1; i 0; i--) { if (digits[i] ! other.digits[i]) { return digits[i] other.digits[i] ? 1 : -1; } } return 0; }然后实现不考虑符号的减法this otherBigInt BigInt::subtract(const BigInt other) const { BigInt result; int borrow 0; // 借位 for (int i 0; i len; i) { // 当前位的被减数 int current digits[i] - borrow; // 如果还有减数则减去 if (i other.len) { current - other.digits[i]; } // 处理借位 if (current 0) { current 10; borrow 1; } else { borrow 0; } result.digits[result.len] current; } // 移除结果的前导零比如 100 - 99 001需要去掉前面的两个0 while (result.len 1 result.digits[result.len - 1] 0) { result.len--; } return result; }关键点解析借位borrow在每一轮开始时就从当前位扣除。如果当前位计算后为负数需要向高位借1即borrow1给下一轮同时当前位加10。减法结果可能会产生前导零必须在最后清除保证len的准确性。这是减法独有的步骤。完整的带符号减法就需要先比较绝对值决定结果的符号然后调用上面的subtract函数。3.3 高精度乘法乘法是第一个性能瓶颈。最朴素的方法我们称之为“高精度 × 高精度”是模拟竖式乘法的每一位相乘。对于A * B其中A有la位B有lb位。结果C的每一位c[ij]由所有a[i] * b[j]的和贡献而来。BigInt BigInt::multiply(const BigInt other) const { BigInt result; // 结果的最大位数是 la lb for (int i 0; i len; i) { int carry 0; // 每一行的进位 for (int j 0; j other.len; j) { // 关键a[i] * b[j] 的结果累加到 c[ij] 上 result.digits[i j] digits[i] * other.digits[j] carry; carry result.digits[i j] / 10; result.digits[i j] % 10; } // 处理每一行最后的进位 if (carry 0) { result.digits[i other.len] carry; } } // 确定结果长度 result.len len other.len; // 可能是最大长度 while (result.len 1 result.digits[result.len - 1] 0) { result.len--; } return result; }关键点解析这是一个双重循环时间复杂度是 O(n²)其中 n 是位数。当数字很大时比如10万位这个算法会非常慢。内层循环的carry是当前(i, j)乘积累加后产生的进位需要立刻处理并加到下一位(i, j1)的计算中。外层循环结束后可能还有进位需要处理到result.digits[i other.len]。最后同样需要清理前导零。优化方向对于超大整数的乘法有更高效的算法如Karatsuba算法O(n^1.585)和基于快速傅里叶变换(FFT)的算法O(n log n)。这在后文会简要提及。3.4 高精度除法除法是四则运算中最复杂的。我们这里实现的是高精度除以高精度得到商和余数。我们采用竖式长除法的模拟。基本思路是从被除数的高位开始逐位“落位”构造一个临时的被除数或余数看它是否大于等于除数。如果是就进行试商然后做减法。// 返回商余数保存在参数remainder中 BigInt BigInt::divide(const BigInt divisor, BigInt remainder) const { BigInt quotient; remainder 0; // 初始化余数为0 // 如果被除数小于除数商为0余数为被除数 if (this-compare(divisor) 0) { remainder *this; return quotient; // quotient默认为0 } // 复制被除数到余数用于逐步计算 remainder *this; // 从最高位开始处理 for (int i len - divisor.len; i 0; i--) { // 构造一个临时的除数比较对象它是 divisor 左移 i 位 // 但实际上我们不需要真的移动数组而是通过偏移量来模拟 // 关键判断当前余数的高位部分是否 divisor BigInt tempDivisor divisor; // 给tempDivisor后面补i个零相当于左移 // 这里我们用一个辅助函数来比较 remainder 从第i位开始的长为divisor.len的子段与 divisor while (remainder.greaterOrEqual(divisor, i)) { // 如果够减则商对应位加1 quotient.digits[i]; // 注意商的第i位对应的是10^i的系数 // 从余数中减去 (divisor * 10^i) remainder remainder.subtractMultiple(divisor, i); } } // 整理商去除前导零并确定长度 quotient.normalize(); return quotient; }上面的代码是概念性的。实际实现中greaterOrEqual和subtractMultiple函数需要仔细处理偏移量。更常见且易于理解的实现是试商法先将被除数和除数对齐通过补零。从高位开始每次取被除数的前若干位位数与除数相同作为“当前被除数”。估算商。一个简单的估算是用当前被除数的前两位除以除数的最高位。但需要调整以确保估算值不会过大。用估算的商乘以除数从当前被除数中减去。如果结果非负则该位商确定如果为负则将商减1重新调整。将下一位被除数“落”下来重复步骤3-4。由于试商法的细节较多代码较长其核心在于如何快速而准确地估算每一位的商。一个常见的优化是使用更高进制的存储如万进制即一个数组单元存0-9999这样不仅能减少循环次数还能让试商时用int范围内的除法进行估算大大提高效率。实操心得高精度除法的边界条件非常多除数为0、被除数为0、商为0等调试起来比较痛苦。建议先写出核心逻辑然后用大量的小数据包括边界数据进行测试再逐步过渡到大数测试。单元测试在这里非常有用。4. 性能优化与高级技巧当数字的位数达到成千上万甚至更多时朴素的 O(n²) 乘法会成为不可接受的瓶颈。下面介绍两种主流的优化方法。4.1 压位高精度我们之前用一个int存储一个十进制位0-9这非常浪费。一个int能轻松存储超过20亿的数我们只用了10个状态。压位的思想就是用一个int来存储多位十进制数。万进制这是最常用的选择。用一个int存储4位十进制数0-9999。这样存储空间立即变为原来的1/4加法和减法的循环次数也减少为原来的1/4。亿进制用int存储8位十进制数0-99999999。但要注意乘法时两个8位数相乘可能达到10^16会超过32位int的范围约2×10^9所以通常用64位的long long作为中间计算类型。万进制加法示例const int BASE 10000; // 基数为10000 const int WIDTH 4; // 每个单元宽度为4位十进制 struct BigInt { vectorint parts; // 每个part存储0-9999parts[0]是最低位 // ... 其他成员 BigInt add(const BigInt other) { BigInt result; int carry 0; for (size_t i 0; i max(parts.size(), other.parts.size()) || carry; i) { if (i parts.size()) carry parts[i]; if (i other.parts.size()) carry other.parts[i]; result.parts.push_back(carry % BASE); carry / BASE; } return result; } // 输出时需要补零例如 part123 需要输出为 0123 };压位的优势大幅减少循环次数提升加、减、乘、除速度。减少内存占用。乘法优势更明显两个n位的万进制数相乘计算量约为 (n/4)²而十进制下是 n²理论上有16倍的提升。4.2 高效乘法算法Karatsuba与FFT对于极端大规模例如10万位以上的乘法即使压位后 O(n²) 的复杂度依然太高。这时就需要更高级的算法。Karatsuba算法 这是一个基于分治的算法。它将两个大数X和Y各自分成两部分X A * B^m BY C * B^m D。那么X*Y AC * B^(2m) ((AB)(CD) - AC - BD) * B^m BD。这样一次大的乘法被转化为三次较小的乘法AC,BD,(AB)(CD)递归进行。其时间复杂度约为 O(n^1.585)优于 O(n²)。FFT快速傅里叶变换乘法 这是目前已知的、用于超大整数乘法的最快实用算法。其核心思想是将大数看成多项式多项式的乘法可以通过点值表示法在 O(n) 时间内完成。而利用FFT我们可以在 O(n log n) 时间内完成系数表示法与点值表示法之间的转换。因此整个乘法过程可以在 O(n log n) 时间内完成。这是许多专业大数库如GMP使用的算法。如何选择对于算法竞赛和大多数应用压位高精度万进制配合朴素乘法已经完全足够代码复杂度低不易出错。如果位数超过10^5级别并且性能成为关键瓶颈可以考虑实现Karatsuba算法。它的实现比FFT简单在中等规模数据上已有明显优势。FFT乘法实现复杂常数因子大通常只在学术研究或极其追求性能的专用库中才会使用。除非有非常特殊的需求否则不建议自己实现。5. 常见问题与实战调试技巧即使理解了原理实现高精度算法时也难免遇到各种“坑”。下面是一些常见问题和解决技巧。5.1 前导零问题这是最高频的错误来源。在减法、乘法、除法运算后结果的最高位可能变成0。必须在函数返回前清理这些前导零保证len或parts.size()准确反映数字的真实长度。一个长度为0的数字应表示为0。检查清单在每个可能改变最高位的运算函数末尾加上清理前导零的循环。5.2 数组越界我们通常用一个固定的大数组如int digits[1005]来存储。在加法和乘法中结果的长度可能超过操作数的长度。必须确保循环的上界足够大能够容纳可能的最大结果。加法max(lenA, lenB) 1乘法lenA lenB在压位高精度中使用vector动态扩容可以避免这个问题但需要注意push_back的性能。5.3 除法的试商精度在模拟竖式除法时如果除数很大直接用被除数的前几位除以除数的最高位来试商误差可能很大导致需要多次调整减1。一个更稳健的方法是用被除数的前两位或前三位除以除数的前两位如果除数足够长来试商。在万进制下我们可以用long long来存储被除数的前两部分和除数的前一部分进行64位除法来估算精度非常高通常一次就能得到正确的商。5.4 负数的处理我们之前的讨论都基于非负整数。支持负数需要增加一个bool sign成员表示正负。加法和减法需要根据符号判断实际操作(A) (B)A B(A) (-B)A - B(需比较|A|和|B|)(-A) (B)B - A(-A) (-B)-(A B)减法可以转换为加法A - B A (-B)。乘法和除法的符号规则简单同号得正异号得负。5.5 测试策略如何验证你的高精度类是正确的单元测试针对每个运算加、减、乘、除编写大量测试用例。边界值01大数。进位/借位999...9 11000...0 - 1。随机测试用脚本生成随机的大整数对用你的高精度类和Python内置的大整数int是任意精度的进行同样的计算对比结果。Python是你的“标准答案生成器”。性能测试用递增的位数测试乘法的运行时间绘制曲线观察是否符合预期的复杂度O(n²) 或 O(n^1.585)。内存检查确保没有内存泄漏如果用了动态数组特别是在实现Karatsuba等递归算法时。5.6 一个完整的、带压位的类框架示例核心部分#include iostream #include vector #include string #include algorithm using namespace std; class BigInt { static const int BASE 10000; // 万进制 static const int WIDTH 4; // 每位宽度 vectorint parts; // 低位在前 bool sign; // true为负 // 工具函数去除前导零 void trim() { while (parts.size() 1 parts.back() 0) { parts.pop_back(); } if (parts.empty()) parts.push_back(0); if (parts.size() 1 parts[0] 0) sign false; // 0统一为正 } public: // 构造函数 BigInt(long long num 0) { *this num; } BigInt(const string s) { *this s; } // 赋值运算符 BigInt operator(long long num) { parts.clear(); sign (num 0); num abs(num); do { parts.push_back(num % BASE); num / BASE; } while (num 0); return *this; } BigInt operator(const string s) { parts.clear(); sign (s[0] -); int start sign ? 1 : 0; // 从字符串末尾开始每WIDTH字符截取一段 for (int i s.length(); i start; i - WIDTH) { int end max(start, i - WIDTH); string partStr s.substr(end, i - end); int part stoi(partStr); parts.push_back(part); } trim(); return *this; } // 加法暂未处理符号仅演示压位加法 BigInt operator(const BigInt rhs) const { if (sign ! rhs.sign) { // 异号转为减法 // ... 此处省略符号处理代码 } BigInt res; res.parts.clear(); int carry 0; size_t maxSize max(parts.size(), rhs.parts.size()); for (size_t i 0; i maxSize || carry; i) { if (i parts.size()) carry parts[i]; if (i rhs.parts.size()) carry rhs.parts[i]; res.parts.push_back(carry % BASE); carry / BASE; } res.sign sign; // 同号符号不变 res.trim(); return res; } // 比较绝对值大小 bool absLess(const BigInt rhs) const { if (parts.size() ! rhs.parts.size()) { return parts.size() rhs.parts.size(); } for (int i parts.size() - 1; i 0; i--) { if (parts[i] ! rhs.parts[i]) { return parts[i] rhs.parts[i]; } } return false; // 相等 } // 输出 friend ostream operator(ostream out, const BigInt num) { if (num.sign) out -; out num.parts.back(); // 最高位无需补零 for (int i num.parts.size() - 2; i 0; i--) { // 中间位需要补零到WIDTH位 out.width(WIDTH); out.fill(0); out num.parts[i]; } return out; } };这个框架展示了压位存储、构造函数、加法、比较和输出的核心逻辑。你可以在此基础上补充减法、乘法、除法以及完整的符号处理。最后高精度算法的实现是一个很好的编程练习它能极大地锻炼你对数据结构、循环、边界条件的掌控能力。从最简单的十进制数组开始逐步优化到压位存储最后挑战Karatsuba算法这个学习路径是清晰且收获满满的。当你看到自己写的类能够正确计算几百位的阶乘或者斐波那契数时那种成就感是实实在在的。
