C++ 高精度乘法运算的实现

前言C 的内置整数类型宽度有限。unsigned long long通常也只有 64 位能表示的最大值约为 1.8×10^19十进制不过 20 位。计算阶乘、组合数、大整数幂、密码学中间值或者处理长度上万位的数字时内置类型会溢出。所谓「高精度运算」arbitrary-precision arithmetic就是自己用数组或容器保存每一位按竖式规则逐位计算。本文只讨论非负整数的乘法这是高精度运算的核心减法涉及借位和符号除法更复杂可以在此基础上扩展。实现采用「小端存储」最低位放在下标 0最高位放在末尾。这样进位方向与下标增长方向一致循环写起来最自然。一个常见误解是「把long long换成__int128就够了」。__int128是 GCC/Clang 的扩展不是标准 C宽度仍然固定而且在 MSVC 上不可用。真正的高精度必须把数字拆成多个「肢」limb由程序自己管理进位。一、数据表示与复杂度最直观的表示是十进制字符串。每个字符是一位范围 0 到 9乘法的中间结果最大是9*99999用int足够。另一种常见做法是以 10^9 为基把每 9 位十进制数字压进一个 32 位整数这样同样长度的数字只需要约九分之一的循环次数。两种表示的算法结构完全一样只是进位阈值不同。表示每个元素范围中间结果上限特点十进制位0 到 999直观、易调试循环次数多10^9 进制0 到 999999999约 10^18需要 64 位中间变量循环次数少二进制肢体0 到 2^32-1约 2^64适合底层库输出十进制要额外转换设两个数分别有 n 位和 m 位竖式乘法的每一位都要与另一个数的每一位相乘时间复杂度是 O(n×m)。结果最多有 nm 位因为两个 n 位数相乘不超过 10^(2n)。空间复杂度是 O(nm)。二、竖式乘法的下标关系把 a 和 b 都按小端存放a[0]是个位a[1]是十位依此类推。a 的第 i 位乘以 b 的第 j 位结果的量级是 10^(ij)所以这个乘积要累加到result[ij]上。如果先把所有a[i]*b[j]累加到一个足够宽的数组里最后再统一处理进位那么数组元素可能达到 n×81 的量级需要更宽的类型。更常见的做法是边乘边进位对每个 i维护一个进位carry内层循环处理 j算出cur result[ij] a[i]*b[j] carry把cur % 10留在原位把cur / 10作为新的进位。内层结束后还要把剩余的进位继续向高位传播。这里有两个边界必须注意。第一结果数组要开 nm 个元素不能只开 nm-1虽然最高位经常是 0但进位传播可能用到它。第二内层循环结束后的进位可能不止一位要用循环而不是一次赋值。三、完整实现下面的类支持从十进制字符串构造、转回字符串、以及两个非负整数相乘。构造函数会校验字符、去掉前导零并把单独的「0」规范化为一位。// 适用于 C17#include cstddef#include iostream#include stdexcept#include string#include vectorclass BigUInt {public:BigUInt() : digits_(1, 0) {}explicit BigUInt(const std::string text) {if (text.empty()) {digits_.push_back(0);return;}for (char ch : text) {if (ch 0 || ch 9) {throw std::invalid_argument(not a decimal integer);}}std::size_t begin 0;while (begin 1 text.size() text[begin] 0) {begin;}for (std::size_t i text.size(); i begin; --i) {digits_.push_back(text[i - 1] - 0);}}std::string str() const {std::string out;out.reserve(digits_.size());for (auto it digits_.rbegin(); it ! digits_.rend(); it) {out.push_back(static_castchar(0 *it));}return out;}BigUInt operator*(const BigUInt rhs) const {BigUInt result;// n m 位全部先置零result.digits_.assign(digits_.size() rhs.digits_.size(), 0);for (std::size_t i 0; i digits_.size(); i) {int carry 0;for (std::size_t j 0; j rhs.digits_.size(); j) {const int cur result.digits_[i j] digits_[i] * rhs.digits_[j] carry;result.digits_[i j] cur % 10;carry cur / 10;}// 内层结束后继续向高位传播std::size_t k i rhs.digits_.size();while (carry 0) {const int cur result.digits_[k] carry;result.digits_[k] cur % 10;carry cur / 10;k;}}result.trim();return result;}private:void trim() {while (digits_.size() 1 digits_.back() 0) {digits_.pop_back();}}std::vectorint digits_; // 小端digits_[0] 是个位};int main() {BigUInt a(12345678901234567890);BigUInt b(98765432109876543210);std::cout (a * b).str() \n;BigUInt zero(0);std::cout (a * zero).str() \n;return 0;}对拍推演可以验证几个关键点。以 99×99 为例a{9,9}、b{9,9}结果数组初始为 4 个 0。i0 时内层得到digits[0]1、digits[1]9、进位 8传播到digits[2]8i1 时digits[1]变成 0、进位 9digits[2]变成 8、进位 9传播到digits[3]9。最后结果是{1,0,8,9}输出 9801。这个结果符合竖式乘法的预期。while (carry 0)里没有显式检查k是否越界是因为结果数组开了 nm 位而两个 nm 位以内的数相乘不会超过这个长度如果要在接口层支持任意输入仍可在循环里加一个防御性判断或者在调试构建里用at()检查。把这一条写进注释比默默依赖不变量更安全。四、进一步优化与边界O(n×m) 的竖式乘法在几千位以内足够用。位数继续增大时可以考虑 Karatsuba 算法把每个数拆成高低两半用三次规模减半的乘法组合出结果时间复杂度约为 O(n^1.585)。再往上Schönhage-Strassen 之类的快速傅里叶变换方法可以做到接近 O(n log n)但实现复杂、常数大通常只出现在专门的大数库中。这些是算法层面的结论不代表在某个具体输入上一定更快实际选择要结合位数分布和测量。如果改用 10^9 进制核心循环只需要把阈值换掉并把中间变量换成 64 位// 适用于 C17#include cstdint#include vectorconstexpr std::uint64_t kBase 1000000000ULL;// 假设 a、b、result 都是小端、每个元素小于 kBasevoid multiplyLimbs(const std::vectorstd::uint32_t a,const std::vectorstd::uint32_t b,std::vectorstd::uint32_t result) {result.assign(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) {std::uint64_t cur result[i j] static_caststd::uint64_t(a[i]) * b[j] carry;result[i j] static_caststd::uint32_t(cur % kBase);carry cur / kBase;}std::size_t k i b.size();while (carry 0) {std::uint64_t cur result[k] carry;result[k] static_caststd::uint32_t(cur % kBase);carry cur / kBase;k;}}}这里a[i] * b[j]最大约 10^18加上result和carry后仍在std::uint64_t的范围约 1.8×10^19内。若把基改成 10^10乘积就会逼近 10^20uint64_t不再够用必须换更宽的中间类型或降低基。符号是另一个维度。本文的类只处理非负整数要支持负数最干净的做法是单独保存一个符号位乘法的绝对值部分复用上面的逻辑最后按「同号为正、异号为负」设置结果符号。不要在每一位上引入负数否则进位规则会变得非常难推导。常见坑点❌ 用int保存 10^9 进制的a[i]*b[j]carry。✅ 中间结果用std::uint64_t或long long否则有符号溢出是未定义行为。❌ 结果数组只开nm-1位最高位进位写越界。✅ 开nm位最后再统一去掉前导零。❌ 内层循环结束后只执行一次result[k] carry。✅ 用while (carry 0)继续向高位传播。❌ 输入全为 0 时输出空串或前导零没有去掉。✅ 构造时跳过前导零并保证至少保留一个 0 位输出前调用trim。❌ 把负号当成普通字符处理或者直接在每位上存负数。✅ 绝对值与符号分离乘法只算绝对值最后再定符号。❌ 用double或long double计算大数指望它精确。✅ 浮点只有有限有效位必须用整数数组逐位计算。❌ 空字符串输入导致访问text[0]越界。✅ 构造前判断空串显式返回表示 0 的对象或抛异常。❌ 相乘时复用被乘数的结果数组却没有清零。✅ 每次乘法重新分配并全部置零避免残留旧值影响进位。总结要点做法存储顺序小端存放最低位在下标 0核心公式result[ij] a[i] * b[j]边乘边进位结果长度n m 位最后去前导零中间类型十进制位用int10^9 进制用uint64_t符号单独保存符号绝对值参与运算复杂度竖式 O(nm)Karatsuba、FFT 用于更大规模高精度乘法并不神秘它就是把小学竖式翻译成数组下标的算术。真正容易出错的是进位边界、结果长度和中间类型只要把这三处写成不变量并在注释里说明为什么不会越界代码就经得起推敲。需要更高性能时再在清晰的竖式实现之上替换算法而不是一开始就写一个难以验证的快速版本。