大整数的乘法（分治法）

article/2025/9/14 6:44:49

通常执行一次加法或乘法运算所需的计算时间看作一个仅取决于计算机硬件处理速度的常数。这个仅在参加运算的整数能在计算机硬件对整数的表示范围内直接处理才是合理的。若要精确地表示大整数并在计算结果中要求精确得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。

问题描述：假设有两个大整数X、Y，分别设X=1234、Y=6789。现在要求X*Y的乘积，小学的算法就是把X与Y中的每一项去乘，但是这样的乘法所需的时间复杂度为O(N^2)，(因为每一位要逐个去乘)，所以效率比较低下。那我们可以采用分治的算法，将X、Y拆分成四部分，如下图:

在这里插入图片描述
则X可表示为：

同理Y也可以表示出来。

所以现在将一个大的整数分成了两部分，问题规模减小，这样直接相乘就会写成
在这里插入图片描述

但是这样你会发现，最后还是要计算4次n/2位整数的乘法，以及三次加法，根据master定理最后会发现T(n)=O(n^2);所以说这其实没有改进成功，要改进成功，就需要通过将算式变形来减少乘法的次数，对此，我们写成如下形式：

在这里插入图片描述
这样就能减少乘法的次数，（只做了AC,BD (A-B)(D-C)三次乘法）,由master定理可得T（n）=O(n^log3),优化成功。

#include<iostream>
#include<cmath>using namespace std;int divideConquer(int X, int Y, int n){int x = abs(X);int y = abs(Y);if( x == 0 || y == 0){return 0;}else if( n == 1){return x * y;}else{int A = x / pow(10, n / 2);int B = x - A * pow(10, n / 2);int C = y / pow(10, n / 2);int D = y - C * pow(10, n / 2);int AC = divideConquer(A, C, n / 2);int BD = divideConquer(B, D, n / 2);int ABCD = divideConquer((A - B), (D - C), n / 2) + AC + BD;return AC*pow(10, n) + ABCD * pow(10, n / 2) + BD;}
}int main(){cout << divideConquer(1234, 9876, 4) << endl;return 0;
}