如何实现存储在vector中的两个大整数的高效相乘运算

你当前在用的是常规竖式模拟乘法，时间复杂度为O(n*m)（n、m为两个大整数的数位长度），针对大数场景有不少更高效的实现思路：

• 基数放大优化：这是改造成本最低的优化手段，如果你现在vector每个元素存的是单十进制位（0-9），可以把每个位的基数改成10^9（对应9位十进制数，刚好不超过32位int的乘积上限），直接把运算次数降到原有的1/9，数位长度在万级以内的时候，收益比复杂的优化算法更明显。
• Karatsuba分治乘法：时间复杂度约为O(n^1.585)，比常规竖式快很多，适合数万位级别的大整数相乘。核心思路是把两个大数拆成高低两半，把原本需要的4次子乘法减少到3次，通过加减法置换乘法次数降低复杂度，你已经实现了大整数加法，只需要额外补充大整数减法、数位左移（末尾补零对应乘基数的N次方）逻辑即可快速实现。
• FFT/NTT基乘法：适合十万位以上的超大整数相乘，时间复杂度可以做到O(n log n)，是目前工业级大整数库的主流实现方案。原理是大整数乘法本质上是数位系数的卷积运算，通过快速傅里叶变换（FFT）可以把卷积运算从O(n²)降到O(n log n)，如果担心浮点精度问题可以用快速数论变换（NTT）在模域下做整数运算，完全避免精度误差。

另外你当前的伪代码也可以做小优化，不需要每次算完一行乘积就调用一次加法函数，可以先把所有乘积按偏移量累加到同一个数组，最后统一处理一次进位，能省去大量加法函数的调用开销，优化后逻辑参考：

// 假设base为你使用的数位基数，比如10、10^9等
vector<int> res(v1.size() + v2.size(), 0);
for (int i = 0; i < v1.size(); i++) {
    for (int j = 0; j < v2.size(); j++) {
        res[i + j] += v1[i] * v2[j];
    }
}
// 统一处理进位
int carry = 0;
for (int i = 0; i < res.size(); i++) {
    int total = res[i] + carry;
    res[i] = total % base;
    carry = total / base;
}
// 最后去除前导零即可得到最终结果

内容的提问来源于stack exchange，提问作者thankyoubasedgod39