C++实现大数相乘的算法-北京尧图网络

前言C 内置的整数类型有明确的上限long long至少 64 位能表示的最大无符号值约为 1.8×10¹⁹也就是 20 位十进制数。计算阶乘、处理加密参数、做大数幂运算时结果动辄几百上千位内置类型完全不够用。大数相乘big integer multiplication就是用数组或字符串模拟手算竖式的过程。初学时的典型误解有三个。第一是以为把每一位存进int数组就万事大吉结果在进位时用int承接乘积两个 9 位数相乘直接溢出。第二是以为「一位存一个十进制数字」是唯一做法于是数组长度是结果位数的十倍循环次数也成倍增加。第三是忽略符号与小数点把「大整数」和「大实数」混为一谈遇到负数或小数就无从下手。本文从竖式乘法的进位规律讲起说明为什么用 10⁹ 作为基数limb给出一个可直接使用的小端存储实现最后讨论 Karatsuba、FFT 等更快的算法以及符号处理。代码以 C17 为基准。一、竖式乘法的结构手算123 × 45的过程是用 5 依次乘 123 的每一位得到一个部分积用 4 乘 123 的每一位左移一位后相加。写成程序就是双重循环外层遍历乘数的每一位内层遍历被乘数的每一位把乘积累加到结果的对应位置。设a有 n 位、b有 m 位结果的第i j位累加a[i] * b[j]。所有乘积累加完毕后再统一处理进位这是最清晰的写法先把「乘」和「进位」分开避免在同一个循环里既算乘积又处理进位逻辑纠缠在一起。这里有一个关键的选择基数取多大。如果一位存一个十进制数字基数是 10那么每次乘法的结果最大是 81加上进位也不会溢出但数组长度等于十进制位数一个 1000 位的数需要 1000 个元素。如果基数取 10⁹每个元素存 9 位十进制数组长度缩短为约 1/9而两个 10⁹ 以下的数相乘最大约 10¹⁸用 64 位整数承接绰绰有余。10⁹ 是一个恰到好处的选择它小于 2³⁰两个这样的数相乘小于 2⁶⁰再加上进位也不超过 64 位同时它又是 10 的幂输出时可以按 9 位一组直接拼接不需要做进制转换。用 2³² 作基数虽然更贴近机器字长但输出时要反复除以 10反而更麻烦。基数每个 limb 的十进制位数乘积上限输出难度数组长度10181直接逐位输出最长10000410⁸按 4 位补零中等10⁹9约 10¹⁸按 9 位补零短2³²约 9.6需要 128 位或拆分需进制转换最短二、存储方向与进位大数在数组里通常采用小端存储下标 0 存最低位。这样做的好处是「进位向高位走」对应「下标增大」push_back就能扩展不需要在头部插入。如果反过来用大端存储每次进位都要往前挪或者在头部insert复杂度立刻退化。进位的处理有两种风格。第一种是边乘边进位内层循环里算出cur result[ij] a[i]*b[j] carry立刻取模写回、更新 carry。第二种是先累加所有乘积最后统一从低到高扫一遍做进位。第一种更省内存因为result的每个元素始终小于基数第二种写起来更直观但中间值可能累积得很大需要保证累加用的类型足够宽。本文采用第一种。要注意carry在每轮内层循环结束后可能还有剩余需要继续向更高位传播直到 carry 为 0。传播时也要取模因为高位的result可能已经有值。清零与长度处理是另一个易错点。结果数组的长度应当是n m两个 n 位和 m 位的数相乘结果最多 nm 位。乘完之后高位可能是 0必须从尾部去掉否则输出会带前导零如果结果本身就是 0所有位都是 0去掉之后数组为空输出时需要特判成0。三、完整实现// 适用于 C17#include algorithm#include cstdint#include iostream#include string#include vectorusing Limbs std::vectorstd::uint32_t; // 小端每个元素存 9 位十进制constexpr std::uint32_t kBase 1000000000u;Limbs from_string(const std::string s) {Limbs out;for (int end static_castint(s.size()); end 0; end - 9) {const int begin std::max(0, end - 9);out.push_back(static_caststd::uint32_t(std::stoul(s.substr(static_caststd::size_t(begin),static_caststd::size_t(end - begin)))));}return out;}Limbs multiply(const Limbs a, const Limbs b) {if (a.empty() || b.empty()) {return {};}std::vectorstd::uint64_t acc(a.size() b.size(), 0);for (std::size_t i 0; i a.size(); i) {std::uint64_t carry 0;for (std::size_t j 0; j b.size(); j) {const std::uint64_t cur acc[i j] static_caststd::uint64_t(a[i]) * b[j] carry;acc[i j] cur % kBase;carry cur / kBase;}std::size_t k i b.size();while (carry ! 0) {const std::uint64_t cur acc[k] carry;acc[k] cur % kBase;carry cur / kBase;k;}}Limbs out(acc.begin(), acc.end());while (!out.empty() out.back() 0) {out.pop_back();}return out;}std::string to_string(const Limbs v) {if (v.empty()) {return 0;}std::string s std::to_string(v.back());for (std::size_t i v.size() - 1; i-- 0;) {const std::string part std::to_string(v[i]);s.append(9 - part.size(), 0); // 非最高位补足 9 位s part;}return s;}int main() {const std::string x 123456789012345678901234567890;const std::string y 987654321098765432109876543210;std::cout to_string(multiply(from_string(x), from_string(y))) \n;return 0;}几个地方值得核一遍。from_string从字符串末尾开始每次取最多 9 个字符转成unsigned long。std::stoul对 9 位十进制最大 999999999不会溢出 32 位无符号类型转成std::uint32_t是安全的。如果分组长度写成 10就会超出std::uint32_t的范围必须改用std::stoull。multiply里acc用std::uint64_t是为了容纳a[i] * b[j]最大约 10¹⁸加上已有值和进位。这三个数相加仍小于 2⁶⁴不会溢出。若把acc声明成std::uint32_t乘积会先被截断结果完全错误。内层循环结束后进位写到i b.size()这个位置。最坏情况下i取a.size() - 1写入位置是a.size() b.size() - 1正好是acc的最后一个下标不会越界。while里继续向高位传播时最后一个位置的值是 0、进位最多为 1写完就归零因此不会越界到acc.end()。to_string里的循环for (std::size_t i v.size() - 1; i-- 0;)是一个需要小心的写法它从size()-2开始一直处理到下标 0靠的是「先用旧值判断、再自减」。如果写成i 0配合无符号数就会死循环。9 - part.size()里part.size()最大是 9不会下溢。四、复杂度、符号与更快的方法朴素竖式乘法的复杂度是 O(n·m)n 和 m 是 limb 的个数也就是十进制的约 1/9。两个一千位的数相乘大约需要 111×111 次乘加非常轻松两个一百万位的数相乘就要 10¹⁰ 次运算这时必须换算法。Karatsuba 算法把一次 n×n 的乘法拆成三次 n/2 规模的乘法递推式 T(n) 3T(n/2) O(n)解得 O(n^log₂3) ≈ O(n^1.585)。它在 n 达到几百位时开始有优势代价是实现复杂、常数因子大、需要处理负数中间结果。再往上还有基于快速傅里叶变换的算法复杂度接近 O(n log n)但只有在数万位以上才划算。实际工程里如果真需要这种规模直接用 GMP 之类的成熟库不要自己写。符号处理应当放在最外层先判断两个操作数的符号用绝对值做乘法最后根据「同号为正、异号为负」补上符号。把一个符号位塞进 limb 数组里会让每一处进位逻辑都要考虑正负得不偿失。小数则完全是另一套问题。定点小数可以记录小数点位置乘完之后调整浮点大数需要更复杂的表示。题目说「大数相乘」时默认指的是整数遇到小数要先和出题人确认。常见坑点坑点一用 32 位整数承接乘积。❌std::uint32_t cur a[i] * b[j] carry;两个接近 10⁹ 的数相乘约 10¹⁸直接溢出。✅ 用std::uint64_t承接中间结果只在写回时截断到基数以内。坑点二基数选 10⁹却用int存结果。❌int acc[...]int在常见平台上是 32 位有符号最大约 2.1×10⁹装不下乘积。✅ 用std::uint64_t或至少std::uint32_t存 limb累加用 64 位。坑点三忘记去掉高位的前导零。❌ 两个 3 位数相乘得到 6 个 limb实际结果只有 4 位输出成了001234。✅ 从尾部pop_back掉所有值为 0 的 limb注意保留至少一个表示 0。坑点四结果为零时返回空数组输出成空串。❌to_string直接遍历空数组得到空字符串。✅ 空数组特判返回0或者在乘法入口就处理零操作数。坑点五大端存储并在头部插入。❌ 每次进位都out.insert(out.begin(), carry)单次 O(n)整体退化成 O(n²) 的额外开销。✅ 小端存储进位向尾部追加最后输出时反向遍历。坑点六用std::stoi解析 9 位以上的分组。❌std::stoi(s.substr(i, 18))超出int范围抛出std::out_of_range。✅ 分组长度不超过 9或用std::stoull并确认分组长度。坑点七把符号塞进 limb。❌ 用负的 limb 表示负数导致取模、进位、比较全部要改。✅ limb 一律非负符号单独用一个bool或int保存。坑点八把「大数相乘」当成「大数加法」处理。❌ 只处理了同长度、无进位的简单情况位数不同时下标越界。✅ 结果数组开n m用i j定位双层循环覆盖所有组合。总结要点结论存储方向小端下标 0 为最低位基数选择10⁹兼顾容量与输出便利中间类型64 位无符号容纳乘积加进位结果长度最多 n m 个 limb进位传播内层循环后继续向高位推进前导零从尾部删除零值特判复杂度朴素 O(n·m)Karatsuba 约 O(n^1.585)符号与小数符号放外层小数另作处理大数相乘的代码不长错误几乎都集中在类型宽度和边界上乘积用什么承接、进位往哪写、结果长度开多少、零怎么表示。把这四个问题在动手前想清楚再用手算的小例子逐位对一遍中间数组比写完再调试快得多。

C++实现大数相乘的算法

相关推荐

CS229机器学习复习主线：从监督学习到SVM与EM的推导链

声源定位精度瓶颈：GCC-PHAT时延估计与MUSIC空间谱实践

YOLO26最新创新改进系列：样条KAN令牌主干，1×1 卷积给每个通道一个固定权重：让 YOLO26 的主干用样条函数去表达非线性！

更多资讯

实测MiMo2.6Pro：中文指令跟随与长文本抽取亮眼，代码生成仍需把关

显式状态驱动的Coding Agent：可审计、可回溯的工程化编码底座

ABB C# SDK环境配置实战：RobotStudio、PC SDK与VS版本匹配指南

财务共享服务落地五层技术架构与MVP实施路径

前端竞态问题解析与解决方案

Java万年历记事本课设：Swing实现日期算法与本地存储

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？