高精度乘法的见解

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

正片开始

快速乘

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

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

18 \times 47 = (10+8) \times (40+7) = 8 \times 7 + 8 \times 40 + 10 \times 7 + 10 \times 40 = 400 + 390 + 56 = 846

。可以只拆分第二个因数：

18 \times 47 = 18 \times (40+7) = 18 \times 40 + 18 \times 7 = 720 + 126 = 846

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

这里贴上快速乘代码

CPP

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，再进行乘法会额外消耗时间，不如将相加顺序颠倒，边转换边相加)

高精度下的快速乘

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

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

具体来说，方法如下：

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

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

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

CPP

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#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！

警告！吐槽语言！

啊！！！！！！！

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

作业没写完！！！！！！

高精度乘法的见解

文章操作

快速乘

快速乘代码分析

高精度下的快速乘

时间复杂度分析

写在最后

相关推荐

评论

高精度乘法的见解