高精度乘法的见解

MightyMathMan · 2025-11-28 23:47:10 · 算法·理论

注：本蒟蒻未专门学习过高精度算法，如此文章理论与已有算法雷同，即算本蒟蒻无知，请各位大佬见谅

正片开始

快速乘

快速幂，可谓是一个众所周知的算法了，而它的变种快速乘也是广为人知。在我的理解下，它的本质是通过二进制拆解一个因数的方式优化乘法。

在十进制下，多位数乘多位数，就是把这两个多位数的每一位相乘再相加。可以用多项式乘法的方式来理解这个过程。例如：

不知各位读者是否意识到，十进制下，每个数位有10种可能的数字。乘法是相同加数多次相加的简便运算，因此将第二个因数进行“数位拆分”时，每一个数位上都相当于做了多次加法。将十进制数转化为二进制数后，每一位上都只有可能出现0或1两种情况，要么加，要么不加，非常明了，不用处理“多次加法”，因此快速乘可以优化乘法。

这里贴上快速乘代码

long long QuickMultiply(long long a, long long b) {
    long long res = 0;
    while(b) {
        if(b & 1) res += a;
        a += a;
        b >>= 1;
    }
    return res;
} 

快速乘代码分析

观察快速乘的特性。

根据上文所讲，快速乘还是将第二个因数转化成二进制形式分解，再通过逐位相乘再相加的形式完成乘法运算。所以，res的初值赋为0。在分解b的过程中，需要从小到大读取b的二进制数位，而 b & 1和b >>= 1这两句正是实现了如此操作。如果读取到b的当前位为1，那么就加上a的相应倍数。（本蒟蒻叙述能力非常差，关于快速乘可以阅读其它大佬的帖子）

举例来讲，18 \times 47 = 18 \times (101111)_2 = 18 \times (000001)_2 + 18 \times (000010)_2 + 18 \times (000100)_2 + 18 \times (001000)_218 \times (100000)_2 = 846 (这里我们是站在上帝视角才能看到47的二进制分解，如果让程序来做的话，先二进制转换47，再进行乘法会额外消耗时间，不如将相加顺序颠倒，边转换边相加)

高精度下的快速乘

这个时候有人就会说了：你叽里咕噜讲了那么一大堆，是不是忘了标题是什么了？这当然是不可能的。

在上一节的分析中，容易发现，快速乘是倒序读取二进制的每一位，而二进制转换也同样是倒序得到二进制的每一位，因此，边转换二进制，边进行加法累加是没有问题的。将这个思路迁移到高精度上，就得到了高精度下的快速乘。

具体来说，方法如下：

1. 判断第二个因数模2的余数
2. 如果为1，则累加第1个因数
3. 将第二个因数除以2
4. 当第二个因数分解完毕后输出答案

这本质上来说还是快速乘，只不过多了亿点点细节罢了。

下面贴出代码（本蒟蒻习惯和码风可能与诸位大佬不同，请见谅）

#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>

/*
注：这里定义的函数仅仅针对于非负的快速幂，符号问题在主函数内处理
@ MightyMathMan 
*/ 

vi Add(vi a, vi b){ //两数加法 
    int la = a.size(), lb = b.size();
    int pp = 0; //pp: 进位储存器
    vi res;
    res.clear(); //避免脏数据
    if(la > lb){
        swap(la, lb);
        swap(a, b);
        //确保a小b大 
    }
    for(int i = 0; i < la; i++){
        int tmp = a[i] + b[i] + pp;
        res.push_back(tmp % 10);
        pp = tmp / 10;
    }
    for(int i = la; i < lb; i++){
        int tmp = b[i] + pp;
        res.push_back(tmp % 10);
        pp = tmp / 10;
    }
    if(pp) res.push_back(pp);
    return res;
}

vi down(vi b){ //返回b/2 
    int l = b.size(), p = 0; // p: 存储区(?) 
    vi ans;
    ans.clear();
    for(int i = l - 1; i >= 0; i--){
        p = p * 10 + b[i];
        if(ans.size() > 0 || p / 2 != 0) ans.push_back(p / 2); //避免前导0
        p %= 2;
    }
    reverse(ans.begin(), ans.end());//保证倒序存储
    if(ans.size() == 0) ans.push_back(0); //保证不为空 
    return ans;
}

bool NotZero(vi a){ //判断a是否大于0 
    return ((a.size() == 1 && a[0] == 0)? 0 : 1);
}

vi QuickMultiply(vi a, vi b){ //快速乘 
    vi res;
    while(NotZero(b)){
        if(b[0]%2) res = Add(res, a);
        a = Add(a, a);
        b = down(b);
    }
    return res;
}

int main(void){
    char fA, fB; //读取A和B 
    int gA = 1, gB = 1; //符号代表的因数 
    vi A, B;

    scanf("%c", &fA);
    if(fA == '-') gA = -1;
    else A.push_back((int)(fA - '0'));
    while(scanf("%c", &fA)){ //读入 A 
        if(fA == '\n') break;
        A.push_back((int)(fA - '0'));
    }

    scanf("%c", &fB);
    if(fB == '-') gB = -1;
    else B.push_back((int)(fB - '0'));
    while(scanf("%c", &fB)){ //读入 B 
        if(fB == '\n') break;
        B.push_back((int)(fB - '0')); 
    }

    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end()); //倒序 

    vi C = QuickMultiply(A, B);
    if(gA * gB == -1) printf("-");
    reverse(C.begin(),C.end());
    for(auto v:C) printf("%d",v);

    return 0;
} 

时间复杂度分析

（这节有一部分参考deepseek分析结果）

设 \left\vert A \right\vert = N, \left\vert B \right\vert = M（|A|表示A的长度）

Add函数时间复杂度：O(max(N,M))

down函数时间复杂度：O(l)

NotZero函数时间复杂度：O(1)

重点分析QuickMultiply： 设B的实际值为Val_B，则循环次数为 log{Val_B} 次。循环内操作：res = Add(res, a);O(N+M)（估大）；a = Add(a, a)O(N+M)（估大）；b = down(b)O(M)（估大）。

注意到，Val_B \approx 10^M，所以 log{Val_B} \approx log{10^M}，即 O(log{Val_B}) \approx O(M)，所以QuickMultiply函数的时间复杂度大致为 O(NM+M^2)

写在最后

啊，结束啦！

这个算法好像很鸡肋的样子，时间复杂度甚至比朴素算法还要大，但是它同样给我们提供了一个思想：可以将熟悉的东西迁移到不熟悉的东西上面去。

最后：恳请各位大佬帮帮本蒟蒻优化代码吧！本蒟蒻的码力已经要归零啦QWQ！

::::warning[警告！吐槽语言！] 啊！！！！！！！

这个代码100多行，谢了50多分钟，写出来复杂度比朴素算法还高，崩溃了啊！！！！！！！！！

作业没写完！！！！！！ ::::