1. 项目概述当整型不再够用在C的世界里我们习惯了int、long long这些内置数据类型带来的便利。处理日常计算它们游刃有余。但当你需要计算一个100位的阶乘或者处理银行系统中涉及天文数字金额的利息计算时这些固定位宽的整型就显得力不从心了。long long的最大值大约是9.22e18一个20位的数字就能让它“溢出”导致计算结果完全错误。这就是“高精度算法”登场的时刻。高精度算法有时也被称为“大整数运算”其核心思想并不复杂既然一个变量装不下那就用多个变量来装。它通过数组、字符串或者容器手动模拟我们在小学就学会的竖式计算过程实现理论上无限位数仅受限于内存的加、减、乘、除等运算。这不仅仅是学术上的奇技淫巧在密码学RSA密钥、科学计算高精度圆周率、金融系统以及信息学竞赛中它都是不可或缺的基础工具。本文将以C为工具从零开始手把手带你实现一套完整的高精度算法。我们将从最基础的数据存储讲起逐步实现加、减、乘、除四大运算并深入探讨其中的优化技巧和无数我踩过的“坑”。无论你是正在备战信息学奥赛的学生还是需要在项目中处理大数运算的开发者这篇文章都将为你提供一份可直接“抄作业”的、经过实战检验的代码与思路。2. 高精度算法的核心设计与存储模型2.1 为什么选择“倒序存储”几乎所有高精度算法的入门教程都会告诉你用数组存储并且要倒序。比如数字12345我们会存储在数组里num[0]5, num[1]4, num[2]3, num[3]2, num[4]1。新手看到这里往往会疑惑这不是自找麻烦吗正着存不是更符合直觉这里面的门道在于运算的便利性。竖式计算是从最低位个位开始的。如果我们正序存储num[0]1, num[1]2,...当两个数位数不同时对位就会变得非常麻烦。例如123 45你需要将45的个位5去和123的百位1对齐吗显然不对。你需要先找到个位的位置这增加了无谓的判断。而采用倒序存储数组下标天然就代表了位数下标0是个位1是十位以此类推。进行加法时我们只需要从i0开始循环将a[i]与b[i]相加处理进位然后写入结果数组的c[i]。整个过程干净利落代码逻辑极其清晰。这个设计选择是无数前辈经验总结的最优解务必理解并接受它。2.2 数据结构选型数组、字符串还是vector确定了倒序存储接下来是用什么来存。常见的有三种选择C风格数组int num[1000]最原始最直接。需要预先定义一个足够大的固定长度如1000可能会造成内存浪费或者长度不够用。优点是访问速度极快代码简单。C字符串std::string将数字以字符形式存储。string本身是动态的长度灵活。但字符‘5’需要减去‘0’才能得到数字5进行运算运算完又要加回‘0’才能存回去稍微有些繁琐。不过它非常便于直接从输入流读取大数。C向量std::vectorint我个人最推荐的方式。它兼具了数组的快速随机访问和动态扩容的能力。我们可以用vector的每个元素存储数字的一位0-9。这是现代C中实现高精度最优雅和高效的方式。为了兼顾性能、易用性和教学清晰度本文将主要采用std::vectorint作为存储结构并在关键部分对比不同选择的优劣。我们会定义一个BigInt类来封装这个大整数。class BigInt { public: std::vectorint digits; // 倒序存储每一位数字 bool isNegative; // 符号位true为负 // 构造函数 BigInt(const std::string s 0) { fromString(s); } // ... 其他成员函数 private: void fromString(const std::string s) { digits.clear(); isNegative (s[0] -); // 从字符串末尾个位开始倒序存入vector for (int i s.length() - 1; i (isNegative ? 1 : 0); --i) { digits.push_back(s[i] - 0); } trim(); // 去除前导零 } void trim() { while (digits.size() 1 digits.back() 0) { digits.pop_back(); } if (digits.size() 1 digits[0] 0) { isNegative false; // 统一处理-0的情况 } } };注意trim()函数至关重要。在运算过程中尤其是乘法和除法可能会产生大量的前导零比如00123。这些零不仅浪费空间还会在比较和输出时造成错误。因此在每次可能产生前导零的运算后都必须调用trim()进行清理。3. 四大核心运算的逐行实现与优化3.1 高精度加法进位是唯一难点加法的逻辑最直白就是模拟竖式加法对应位相加加上低位的进位然后计算当前位的值和新进位。BigInt BigInt::operator(const BigInt rhs) const { if (isNegative ! rhs.isNegative) { // 异号转化为减法这里先省略后文详述 // 例如 a (-b) 等同于 a - b BigInt tmp rhs; tmp.isNegative !tmp.isNegative; return *this - tmp; } BigInt result; result.isNegative isNegative; // 同号相加符号不变 result.digits.clear(); int carry 0; // 进位 size_t maxLen std::max(digits.size(), rhs.digits.size()); for (size_t i 0; i maxLen || carry; i) { int sum carry; if (i digits.size()) sum digits[i]; if (i rhs.digits.size()) sum rhs.digits[i]; result.digits.push_back(sum % 10); carry sum / 10; } // 加法不会产生前导零除非00但为了规范还是trim一下 return result; }实操心得注意循环条件i maxLen || carry。这是关键即使两个数的所有位都处理完了i maxLen如果最后还有进位carry 1循环必须继续将这个进位作为新的最高位。这是新手最容易遗漏的点会导致999 1的结果错误地变成000实际应为1000。3.2 高精度减法借位与结果符号的判断减法比加法复杂因为涉及借位和结果符号的判断。核心思路是先判断两个数的大小确保用大数减小数并最终确定结果的符号。BigInt BigInt::operator-(const BigInt rhs) const { if (isNegative ! rhs.isNegative) { // 异号转化为加法例如 a - (-b) a b BigInt tmp rhs; tmp.isNegative !tmp.isNegative; return *this tmp; } // 同号相减比较绝对值大小 const BigInt a *this; const BigInt b rhs; bool resultNegative false; // 比较绝对值的函数 absLessThan 需要另外实现 if (a.isNegative) { // 都是负数 (-a) - (-b) -(a - b) b - a if (absLessThan(a, b)) { // |a| |b|, 结果为正 return b.absSub(a); } else { // |a| |b|, 结果为负 BigInt result a.absSub(b); result.isNegative true; return result; } } else { // 都是正数 if (absLessThan(a, b)) { // a b, 结果为负 BigInt result b.absSub(a); result.isNegative true; return result; } else { // a b, 结果为正 return a.absSub(b); } } } // 辅助函数假设this和rhs都是正数且this rhs BigInt BigInt::absSub(const BigInt rhs) const { BigInt result; result.digits.clear(); int borrow 0; // 借位 for (size_t i 0; i digits.size(); i) { int diff digits[i] - borrow; if (i rhs.digits.size()) { diff - rhs.digits[i]; } if (diff 0) { diff 10; borrow 1; } else { borrow 0; } result.digits.push_back(diff); } result.trim(); // 至关重要减法会产生前导零如100-9901 return result; }避坑指南减法最棘手的部分是符号处理。我的经验是先将所有情况转化为“两个正数相减”最后再贴上正确的符号。上面代码中的absSub函数就是做这个“脏活”的它假设被减数绝对值大于减数。在实现比较函数absLessThan时要从最高位开始逐位比较注意先比较位数位数多的绝对值一定大。3.3 高精度乘法从O(n²)到优化最朴素的乘法是模拟竖式将乘数的每一位与被乘数相乘然后错位相加。时间复杂度是O(n²)其中n是位数。// 朴素乘法 BigInt BigInt::operator*(const BigInt rhs) const { BigInt result; result.digits.resize(digits.size() rhs.digits.size(), 0); // 结果最大位数 for (size_t i 0; i digits.size(); i) { int carry 0; for (size_t j 0; j rhs.digits.size() || carry; j) { // 关键result.digits[ij] 是累加的位置 long long cur result.digits[i j] (long long)digits[i] * (j rhs.digits.size() ? rhs.digits[j] : 0) carry; result.digits[i j] cur % 10; carry cur / 10; } } result.isNegative (isNegative ! rhs.isNegative); // 同号得正异号得负 result.trim(); return result; }性能瓶颈与优化当数字非常大比如上万位时O(n²)的复杂度是无法接受的。在实际项目或竞赛中我们通常会采用更高效的算法Karatsuba算法将大数分成两部分通过三次递归乘法代替四次将复杂度降至约O(n^1.585)。FFT快速傅里叶变换乘法将大数乘法转化为多项式乘法利用FFT在O(n log n)时间内完成这是目前已知最快的大数乘法算法之一。对于绝大多数应用场景位数在几千以内朴素乘法已经足够。但了解这些优化方向是进阶的必经之路。一个简单的优化是在内外层循环中确保外层循环是位数较短的那个数可以减少一些计算量。3.4 高精度除法最复杂的运算除法是高精度运算中最复杂的一种因为商是一位一位试出来的。常用的是“模拟竖式除法”。这里实现一个高精度整数除以低精度整数int的版本相对简单也很有用例如求阶乘后除以一个数。// 高精度除以低精度int返回商remainder返回余数 BigInt BigInt::divide(int divisor, int remainder) const { if (divisor 0) { throw std::runtime_error(Division by zero!); } BigInt quotient; quotient.digits.resize(digits.size(), 0); // 商最多和被除数位数一样多 long long rem 0; // 余数用long long防止中间溢出 // 从最高位开始除注意我们是倒序存储所以最高位在最后 for (int i (int)digits.size() - 1; i 0; --i) { rem rem * 10 digits[i]; quotient.digits[i] rem / divisor; // 注意这里商也是倒序存的但计算顺序是正序 rem % divisor; } quotient.trim(); remainder (int)rem; quotient.isNegative (isNegative ! (divisor 0)); return quotient; }关于高精度除以高精度这是一个更复杂的主题通常采用“试商法”。基本思路是将除数通过左移操作乘以10的幂对齐到和被除数相同的最高位然后估算商例如用被除数的前几位除以除数的最高位加一再进行减法调整。由于实现复杂且代码冗长它常常是信息学竞赛的压轴题。一个更工程化的思路是将高精度数转换为字符串或二进制流利用数学库如GMP或者转换为浮点数进行估算再精细调整。但这已经超出了基础实现的范畴。4. 完整实现、测试与性能调优实录4.1 一个可运行的BigInt类框架将上述模块组合起来并补充比较运算符、输入输出我们就得到了一个可用的BigInt类雏形。#include iostream #include vector #include string #include algorithm #include stdexcept class BigInt { private: std::vectorint digits; bool isNegative; void trim() { /* 如前所述 */ } void fromString(const std::string s) { /* 如前所述 */ } bool absLessThan(const BigInt rhs) const; // 比较绝对值 BigInt absSub(const BigInt rhs) const; // 绝对值减法 public: // 构造函数 BigInt(const std::string s 0) { fromString(s); } BigInt(long long num) { /* 从long long构造略 */ } // 算术运算符 BigInt operator(const BigInt rhs) const; BigInt operator-(const BigInt rhs) const; BigInt operator*(const BigInt rhs) const; BigInt operator/(int divisor) const; // 仅实现除以int // 比较运算符 bool operator(const BigInt rhs) const; bool operator(const BigInt rhs) const; // 友元函数方便输入输出 friend std::ostream operator(std::ostream os, const BigInt bi); friend std::istream operator(std::istream is, BigInt bi); }; // 比较绝对值 bool BigInt::absLessThan(const BigInt rhs) const { if (digits.size() ! rhs.digits.size()) { return digits.size() rhs.digits.size(); } for (int i (int)digits.size() - 1; i 0; --i) { if (digits[i] ! rhs.digits[i]) { return digits[i] rhs.digits[i]; } } return false; // 相等 } // 输出运算符 std::ostream operator(std::ostream os, const BigInt bi) { if (bi.isNegative) os -; for (int i (int)bi.digits.size() - 1; i 0; --i) { os bi.digits[i]; } if (bi.digits.empty()) os 0; // 处理空值 return os; } // 输入运算符 std::istream operator(std::istream is, BigInt bi) { std::string s; is s; bi.fromString(s); return is; } // 主函数测试 int main() { BigInt a, b; std::cout Enter two big integers: ; std::cin a b; std::cout a b (a b) std::endl; std::cout a - b (a - b) std::endl; std::cout a * b (a * b) std::endl; int divisor 7; int rem; BigInt quotient a.divide(divisor, rem); std::cout a / divisor quotient ... rem std::endl; return 0; }4.2 典型问题排查与性能优化技巧在实际编码和调试中你会遇到各种各样的问题。下面这个表格总结了我遇到的一些典型“坑”及其解决方案问题现象可能原因排查与解决技巧加法结果少一位如9991000循环结束后最高位的进位被遗漏。检查加法循环条件必须是 i maxLen **减法结果出现前导零如100-9901运算后没有去除前导零。在减法、乘法、除法函数返回前务必调用trim()函数。乘法结果完全错误或出现负数中间计算结果溢出。int类型在计算a[i]*b[j]时可能超出范围。将中间变量升级为long long。如long long cur (long long)a[i] * b[j] carry;除法试商不准导致死循环或结果错误试商逻辑有缺陷尤其是在除数高位很小的时候。对于高精除高精一个稳健的试商方法是取被除数的前两位和除数的最高位加一来估算如果估算值偏大就循环减1直到合适。程序在处理极大数字如万位时异常缓慢使用了未优化的朴素O(n²)乘法。1.优化基础确保外层循环是位数更短的那个数。2.算法升级考虑实现Karatsuba算法千位到万位或研究FFT乘法万位以上。3.压位优化这是最有效的优化之一。内存占用过高每个vectorint元素只存0-9浪费了大量内存一个int至少4字节。采用“压位”存储。重点聊聊“压位优化”这是将高精度算法性能提升一个数量级的关键技巧。我们不再用一个int存一个十进制位0-9而是用一个int存多位十进制数比如存4位0-9999。这样存储空间立刻减少为原来的1/4同时加法、乘法的循环次数也同比减少。例如用int数组digits每个元素存储0-9999。那么数字123456789将被存储为digits[0]6789,digits[1]2345,digits[2]1依然是倒序但以万进制为单位。运算时进位基数从10变成了10000。输出时需要特别注意除了最高位中间的每一位都要用printf(“%04d”, digits[i])这样的方式补零输出。压位实现的复杂度会显著上升但带来的性能收益是巨大的。对于竞赛和严肃项目这是必选项。4.3 进阶应用计算N的阶乘高精度算法一个经典的应用就是计算大数阶乘N!。这完美展示了其价值。BigInt factorial(int n) { BigInt result(1); for (int i 2; i n; i) { // 这里需要实现 BigInt * int 的重载比高精*高精快 result result * i; // 假设已重载 BigInt::operator*(int) } return result; } // 重载 BigInt * int BigInt BigInt::operator*(int rhs) const { if (rhs 0) return BigInt(0); BigInt result; long long carry 0; for (size_t i 0; i digits.size() || carry; i) { if (i digits.size()) { carry (long long)digits[i] * rhs; } result.digits.push_back(carry % 10); carry / 10; } result.trim(); result.isNegative (isNegative ! (rhs 0)); return result; }计算1000的阶乘用上面的代码未压位可能已经能感觉到延迟了。计算10000的阶乘朴素算法就会非常慢。此时压位优化和更高效的乘法算法就显得尤为重要。你可以尝试用这个函数计算factorial(100)并观察结果的位数应该有158位来验证你实现的正确性。5. 工程实践建议与扩展方向当你掌握了基础的高精度四则运算后可以思考如何将其工程化以及还有哪些可以探索的方向。1. 封装与接口设计 一个完善的BigInt类应该提供完整的运算符重载,-,*,/,%,,-等支持与内置整型的混合运算实现完整的比较运算符,,,,,!。此外像pow幂运算、sqrt开平方可用牛顿迭代法配合高精度实现、gcd最大公约数等常用函数也值得封装。2. 性能权衡对于教学和一般应用使用vectorint存储十进制位实现朴素算法代码清晰易懂。对于竞赛和中等性能要求实现压位存储如万进制并采用Karatsuba乘法。对于极限性能要求如密码学使用专门的库如GNU MP (GMP)。这是一个用C编写的高度优化的大数运算库经过了数十年的打磨性能远超自己实现的版本。在C中可以通过gmpxx.h接口来使用。3. 扩展方向浮点数高精度处理小数需要独立存储整数部分和小数部分并定义小数点位置。运算规则更复杂特别是除法。高精度与数论结合实现模幂运算用于RSA、Miller-Rabin素数测试等。与其他算法结合例如在高精度运算中融入快速傅里叶变换FFT来实现超大规模整数的乘法。实现一套高精度算法是对你编程基本功、算法思维和耐心的一次全面锻炼。从最初的“为什么这么存”的疑惑到后来对进位借位逻辑的娴熟再到主动思考压位和FFT优化这个过程本身就是极大的收获。我建议你不要止步于看懂本文的代码最好能自己从头到尾敲一遍并在过程中尝试添加新的功能比如%运算符、复合赋值或者尝试将其改造成压位存储。当你能够用它流畅地计算2^1000或者1000!时你对整数运算和C语言的理解一定会到达一个新的层次。
1. 项目概述当整型不再够用在C的世界里我们习惯了int、long long这些内置数据类型带来的便利。处理日常计算它们游刃有余。但当你需要计算一个100位的阶乘或者处理银行系统中涉及天文数字金额的利息计算时这些固定位宽的整型就显得力不从心了。long long的最大值大约是9.22e18一个20位的数字就能让它“溢出”导致计算结果完全错误。这就是“高精度算法”登场的时刻。高精度算法有时也被称为“大整数运算”其核心思想并不复杂既然一个变量装不下那就用多个变量来装。它通过数组、字符串或者容器手动模拟我们在小学就学会的竖式计算过程实现理论上无限位数仅受限于内存的加、减、乘、除等运算。这不仅仅是学术上的奇技淫巧在密码学RSA密钥、科学计算高精度圆周率、金融系统以及信息学竞赛中它都是不可或缺的基础工具。本文将以C为工具从零开始手把手带你实现一套完整的高精度算法。我们将从最基础的数据存储讲起逐步实现加、减、乘、除四大运算并深入探讨其中的优化技巧和无数我踩过的“坑”。无论你是正在备战信息学奥赛的学生还是需要在项目中处理大数运算的开发者这篇文章都将为你提供一份可直接“抄作业”的、经过实战检验的代码与思路。2. 高精度算法的核心设计与存储模型2.1 为什么选择“倒序存储”几乎所有高精度算法的入门教程都会告诉你用数组存储并且要倒序。比如数字12345我们会存储在数组里num[0]5, num[1]4, num[2]3, num[3]2, num[4]1。新手看到这里往往会疑惑这不是自找麻烦吗正着存不是更符合直觉这里面的门道在于运算的便利性。竖式计算是从最低位个位开始的。如果我们正序存储num[0]1, num[1]2,...当两个数位数不同时对位就会变得非常麻烦。例如123 45你需要将45的个位5去和123的百位1对齐吗显然不对。你需要先找到个位的位置这增加了无谓的判断。而采用倒序存储数组下标天然就代表了位数下标0是个位1是十位以此类推。进行加法时我们只需要从i0开始循环将a[i]与b[i]相加处理进位然后写入结果数组的c[i]。整个过程干净利落代码逻辑极其清晰。这个设计选择是无数前辈经验总结的最优解务必理解并接受它。2.2 数据结构选型数组、字符串还是vector确定了倒序存储接下来是用什么来存。常见的有三种选择C风格数组int num[1000]最原始最直接。需要预先定义一个足够大的固定长度如1000可能会造成内存浪费或者长度不够用。优点是访问速度极快代码简单。C字符串std::string将数字以字符形式存储。string本身是动态的长度灵活。但字符‘5’需要减去‘0’才能得到数字5进行运算运算完又要加回‘0’才能存回去稍微有些繁琐。不过它非常便于直接从输入流读取大数。C向量std::vectorint我个人最推荐的方式。它兼具了数组的快速随机访问和动态扩容的能力。我们可以用vector的每个元素存储数字的一位0-9。这是现代C中实现高精度最优雅和高效的方式。为了兼顾性能、易用性和教学清晰度本文将主要采用std::vectorint作为存储结构并在关键部分对比不同选择的优劣。我们会定义一个BigInt类来封装这个大整数。class BigInt { public: std::vectorint digits; // 倒序存储每一位数字 bool isNegative; // 符号位true为负 // 构造函数 BigInt(const std::string s 0) { fromString(s); } // ... 其他成员函数 private: void fromString(const std::string s) { digits.clear(); isNegative (s[0] -); // 从字符串末尾个位开始倒序存入vector for (int i s.length() - 1; i (isNegative ? 1 : 0); --i) { digits.push_back(s[i] - 0); } trim(); // 去除前导零 } void trim() { while (digits.size() 1 digits.back() 0) { digits.pop_back(); } if (digits.size() 1 digits[0] 0) { isNegative false; // 统一处理-0的情况 } } };注意trim()函数至关重要。在运算过程中尤其是乘法和除法可能会产生大量的前导零比如00123。这些零不仅浪费空间还会在比较和输出时造成错误。因此在每次可能产生前导零的运算后都必须调用trim()进行清理。3. 四大核心运算的逐行实现与优化3.1 高精度加法进位是唯一难点加法的逻辑最直白就是模拟竖式加法对应位相加加上低位的进位然后计算当前位的值和新进位。BigInt BigInt::operator(const BigInt rhs) const { if (isNegative ! rhs.isNegative) { // 异号转化为减法这里先省略后文详述 // 例如 a (-b) 等同于 a - b BigInt tmp rhs; tmp.isNegative !tmp.isNegative; return *this - tmp; } BigInt result; result.isNegative isNegative; // 同号相加符号不变 result.digits.clear(); int carry 0; // 进位 size_t maxLen std::max(digits.size(), rhs.digits.size()); for (size_t i 0; i maxLen || carry; i) { int sum carry; if (i digits.size()) sum digits[i]; if (i rhs.digits.size()) sum rhs.digits[i]; result.digits.push_back(sum % 10); carry sum / 10; } // 加法不会产生前导零除非00但为了规范还是trim一下 return result; }实操心得注意循环条件i maxLen || carry。这是关键即使两个数的所有位都处理完了i maxLen如果最后还有进位carry 1循环必须继续将这个进位作为新的最高位。这是新手最容易遗漏的点会导致999 1的结果错误地变成000实际应为1000。3.2 高精度减法借位与结果符号的判断减法比加法复杂因为涉及借位和结果符号的判断。核心思路是先判断两个数的大小确保用大数减小数并最终确定结果的符号。BigInt BigInt::operator-(const BigInt rhs) const { if (isNegative ! rhs.isNegative) { // 异号转化为加法例如 a - (-b) a b BigInt tmp rhs; tmp.isNegative !tmp.isNegative; return *this tmp; } // 同号相减比较绝对值大小 const BigInt a *this; const BigInt b rhs; bool resultNegative false; // 比较绝对值的函数 absLessThan 需要另外实现 if (a.isNegative) { // 都是负数 (-a) - (-b) -(a - b) b - a if (absLessThan(a, b)) { // |a| |b|, 结果为正 return b.absSub(a); } else { // |a| |b|, 结果为负 BigInt result a.absSub(b); result.isNegative true; return result; } } else { // 都是正数 if (absLessThan(a, b)) { // a b, 结果为负 BigInt result b.absSub(a); result.isNegative true; return result; } else { // a b, 结果为正 return a.absSub(b); } } } // 辅助函数假设this和rhs都是正数且this rhs BigInt BigInt::absSub(const BigInt rhs) const { BigInt result; result.digits.clear(); int borrow 0; // 借位 for (size_t i 0; i digits.size(); i) { int diff digits[i] - borrow; if (i rhs.digits.size()) { diff - rhs.digits[i]; } if (diff 0) { diff 10; borrow 1; } else { borrow 0; } result.digits.push_back(diff); } result.trim(); // 至关重要减法会产生前导零如100-9901 return result; }避坑指南减法最棘手的部分是符号处理。我的经验是先将所有情况转化为“两个正数相减”最后再贴上正确的符号。上面代码中的absSub函数就是做这个“脏活”的它假设被减数绝对值大于减数。在实现比较函数absLessThan时要从最高位开始逐位比较注意先比较位数位数多的绝对值一定大。3.3 高精度乘法从O(n²)到优化最朴素的乘法是模拟竖式将乘数的每一位与被乘数相乘然后错位相加。时间复杂度是O(n²)其中n是位数。// 朴素乘法 BigInt BigInt::operator*(const BigInt rhs) const { BigInt result; result.digits.resize(digits.size() rhs.digits.size(), 0); // 结果最大位数 for (size_t i 0; i digits.size(); i) { int carry 0; for (size_t j 0; j rhs.digits.size() || carry; j) { // 关键result.digits[ij] 是累加的位置 long long cur result.digits[i j] (long long)digits[i] * (j rhs.digits.size() ? rhs.digits[j] : 0) carry; result.digits[i j] cur % 10; carry cur / 10; } } result.isNegative (isNegative ! rhs.isNegative); // 同号得正异号得负 result.trim(); return result; }性能瓶颈与优化当数字非常大比如上万位时O(n²)的复杂度是无法接受的。在实际项目或竞赛中我们通常会采用更高效的算法Karatsuba算法将大数分成两部分通过三次递归乘法代替四次将复杂度降至约O(n^1.585)。FFT快速傅里叶变换乘法将大数乘法转化为多项式乘法利用FFT在O(n log n)时间内完成这是目前已知最快的大数乘法算法之一。对于绝大多数应用场景位数在几千以内朴素乘法已经足够。但了解这些优化方向是进阶的必经之路。一个简单的优化是在内外层循环中确保外层循环是位数较短的那个数可以减少一些计算量。3.4 高精度除法最复杂的运算除法是高精度运算中最复杂的一种因为商是一位一位试出来的。常用的是“模拟竖式除法”。这里实现一个高精度整数除以低精度整数int的版本相对简单也很有用例如求阶乘后除以一个数。// 高精度除以低精度int返回商remainder返回余数 BigInt BigInt::divide(int divisor, int remainder) const { if (divisor 0) { throw std::runtime_error(Division by zero!); } BigInt quotient; quotient.digits.resize(digits.size(), 0); // 商最多和被除数位数一样多 long long rem 0; // 余数用long long防止中间溢出 // 从最高位开始除注意我们是倒序存储所以最高位在最后 for (int i (int)digits.size() - 1; i 0; --i) { rem rem * 10 digits[i]; quotient.digits[i] rem / divisor; // 注意这里商也是倒序存的但计算顺序是正序 rem % divisor; } quotient.trim(); remainder (int)rem; quotient.isNegative (isNegative ! (divisor 0)); return quotient; }关于高精度除以高精度这是一个更复杂的主题通常采用“试商法”。基本思路是将除数通过左移操作乘以10的幂对齐到和被除数相同的最高位然后估算商例如用被除数的前几位除以除数的最高位加一再进行减法调整。由于实现复杂且代码冗长它常常是信息学竞赛的压轴题。一个更工程化的思路是将高精度数转换为字符串或二进制流利用数学库如GMP或者转换为浮点数进行估算再精细调整。但这已经超出了基础实现的范畴。4. 完整实现、测试与性能调优实录4.1 一个可运行的BigInt类框架将上述模块组合起来并补充比较运算符、输入输出我们就得到了一个可用的BigInt类雏形。#include iostream #include vector #include string #include algorithm #include stdexcept class BigInt { private: std::vectorint digits; bool isNegative; void trim() { /* 如前所述 */ } void fromString(const std::string s) { /* 如前所述 */ } bool absLessThan(const BigInt rhs) const; // 比较绝对值 BigInt absSub(const BigInt rhs) const; // 绝对值减法 public: // 构造函数 BigInt(const std::string s 0) { fromString(s); } BigInt(long long num) { /* 从long long构造略 */ } // 算术运算符 BigInt operator(const BigInt rhs) const; BigInt operator-(const BigInt rhs) const; BigInt operator*(const BigInt rhs) const; BigInt operator/(int divisor) const; // 仅实现除以int // 比较运算符 bool operator(const BigInt rhs) const; bool operator(const BigInt rhs) const; // 友元函数方便输入输出 friend std::ostream operator(std::ostream os, const BigInt bi); friend std::istream operator(std::istream is, BigInt bi); }; // 比较绝对值 bool BigInt::absLessThan(const BigInt rhs) const { if (digits.size() ! rhs.digits.size()) { return digits.size() rhs.digits.size(); } for (int i (int)digits.size() - 1; i 0; --i) { if (digits[i] ! rhs.digits[i]) { return digits[i] rhs.digits[i]; } } return false; // 相等 } // 输出运算符 std::ostream operator(std::ostream os, const BigInt bi) { if (bi.isNegative) os -; for (int i (int)bi.digits.size() - 1; i 0; --i) { os bi.digits[i]; } if (bi.digits.empty()) os 0; // 处理空值 return os; } // 输入运算符 std::istream operator(std::istream is, BigInt bi) { std::string s; is s; bi.fromString(s); return is; } // 主函数测试 int main() { BigInt a, b; std::cout Enter two big integers: ; std::cin a b; std::cout a b (a b) std::endl; std::cout a - b (a - b) std::endl; std::cout a * b (a * b) std::endl; int divisor 7; int rem; BigInt quotient a.divide(divisor, rem); std::cout a / divisor quotient ... rem std::endl; return 0; }4.2 典型问题排查与性能优化技巧在实际编码和调试中你会遇到各种各样的问题。下面这个表格总结了我遇到的一些典型“坑”及其解决方案问题现象可能原因排查与解决技巧加法结果少一位如9991000循环结束后最高位的进位被遗漏。检查加法循环条件必须是 i maxLen **减法结果出现前导零如100-9901运算后没有去除前导零。在减法、乘法、除法函数返回前务必调用trim()函数。乘法结果完全错误或出现负数中间计算结果溢出。int类型在计算a[i]*b[j]时可能超出范围。将中间变量升级为long long。如long long cur (long long)a[i] * b[j] carry;除法试商不准导致死循环或结果错误试商逻辑有缺陷尤其是在除数高位很小的时候。对于高精除高精一个稳健的试商方法是取被除数的前两位和除数的最高位加一来估算如果估算值偏大就循环减1直到合适。程序在处理极大数字如万位时异常缓慢使用了未优化的朴素O(n²)乘法。1.优化基础确保外层循环是位数更短的那个数。2.算法升级考虑实现Karatsuba算法千位到万位或研究FFT乘法万位以上。3.压位优化这是最有效的优化之一。内存占用过高每个vectorint元素只存0-9浪费了大量内存一个int至少4字节。采用“压位”存储。重点聊聊“压位优化”这是将高精度算法性能提升一个数量级的关键技巧。我们不再用一个int存一个十进制位0-9而是用一个int存多位十进制数比如存4位0-9999。这样存储空间立刻减少为原来的1/4同时加法、乘法的循环次数也同比减少。例如用int数组digits每个元素存储0-9999。那么数字123456789将被存储为digits[0]6789,digits[1]2345,digits[2]1依然是倒序但以万进制为单位。运算时进位基数从10变成了10000。输出时需要特别注意除了最高位中间的每一位都要用printf(“%04d”, digits[i])这样的方式补零输出。压位实现的复杂度会显著上升但带来的性能收益是巨大的。对于竞赛和严肃项目这是必选项。4.3 进阶应用计算N的阶乘高精度算法一个经典的应用就是计算大数阶乘N!。这完美展示了其价值。BigInt factorial(int n) { BigInt result(1); for (int i 2; i n; i) { // 这里需要实现 BigInt * int 的重载比高精*高精快 result result * i; // 假设已重载 BigInt::operator*(int) } return result; } // 重载 BigInt * int BigInt BigInt::operator*(int rhs) const { if (rhs 0) return BigInt(0); BigInt result; long long carry 0; for (size_t i 0; i digits.size() || carry; i) { if (i digits.size()) { carry (long long)digits[i] * rhs; } result.digits.push_back(carry % 10); carry / 10; } result.trim(); result.isNegative (isNegative ! (rhs 0)); return result; }计算1000的阶乘用上面的代码未压位可能已经能感觉到延迟了。计算10000的阶乘朴素算法就会非常慢。此时压位优化和更高效的乘法算法就显得尤为重要。你可以尝试用这个函数计算factorial(100)并观察结果的位数应该有158位来验证你实现的正确性。5. 工程实践建议与扩展方向当你掌握了基础的高精度四则运算后可以思考如何将其工程化以及还有哪些可以探索的方向。1. 封装与接口设计 一个完善的BigInt类应该提供完整的运算符重载,-,*,/,%,,-等支持与内置整型的混合运算实现完整的比较运算符,,,,,!。此外像pow幂运算、sqrt开平方可用牛顿迭代法配合高精度实现、gcd最大公约数等常用函数也值得封装。2. 性能权衡对于教学和一般应用使用vectorint存储十进制位实现朴素算法代码清晰易懂。对于竞赛和中等性能要求实现压位存储如万进制并采用Karatsuba乘法。对于极限性能要求如密码学使用专门的库如GNU MP (GMP)。这是一个用C编写的高度优化的大数运算库经过了数十年的打磨性能远超自己实现的版本。在C中可以通过gmpxx.h接口来使用。3. 扩展方向浮点数高精度处理小数需要独立存储整数部分和小数部分并定义小数点位置。运算规则更复杂特别是除法。高精度与数论结合实现模幂运算用于RSA、Miller-Rabin素数测试等。与其他算法结合例如在高精度运算中融入快速傅里叶变换FFT来实现超大规模整数的乘法。实现一套高精度算法是对你编程基本功、算法思维和耐心的一次全面锻炼。从最初的“为什么这么存”的疑惑到后来对进位借位逻辑的娴熟再到主动思考压位和FFT优化这个过程本身就是极大的收获。我建议你不要止步于看懂本文的代码最好能自己从头到尾敲一遍并在过程中尝试添加新的功能比如%运算符、复合赋值或者尝试将其改造成压位存储。当你能够用它流畅地计算2^1000或者1000!时你对整数运算和C语言的理解一定会到达一个新的层次。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
