一.问题
由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。尤其是乘法运算，下面就是大整数的乘法的过程（加 减法都一样的原理）。
二.解决问题的方法
方法一（传统的相乘逐步相加）
乘法规律，一个数的第i位和另一个数的第j位相乘，一定会累加到结果的第i+j位，结果的数组一个数组元素存2位数，最后对结果整除得到进位，mod得到余数就是i+j位的数字，最后打印出来。
对于大整数比较方便的输入方法是，①按字符型处理，存储在字符串数组s1、s2中，计算结果存储在整型数组ans中。 ②通过字符的ASCII码，数字字符可以直接参与运算，i位数字与j位数字相乘的表达式为：(s1[i]-‘0’)*(s2[j]-‘0’)。 ③每一次数字相乘的结果位数是不固定的，而结果数组中每个元素只存储一位数字，所以用变量t暂存结果，对t mod运算得到的就是ans[i+j]的值，若超过1位数则进位，用变量b存储。
这种做法的时间复杂度为o(n^2)
c语言源码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int max(int a,int b){return a>b?a:b;
}int main(){char s1[205], s2[205],ans[1000];int str1[205],str2[205]；int len1, len2,i;while( scanf("%s%s", s1, s2)!=EOF){len1 = strlen(s1), len2 = strlen(s2);memset(str1,0,205);//初始化0memset(str2,0,205);memset(ans,0,1000);int len = 0;for(i = 0; i < len1; ++ i)str1[i] = s1[len1 - 1 - i] - '0';for(i = 0; i < len2; ++ i)str2[i] = s2[len2 - 1 - i] - '0';for( i = 0; i < len1; ++ i){int b = 0; //每遍历完数组a的一个数，进位b都要初始化为0for(int j = 0; j < len2 || b; ++ j)//当str[j]没遍历完，或者最高位满十需要进位，进位不为0{int t = ans[i + j] + str1[i]*str2[j] + b;ans[i + j] = t%10; //余数就是该ans[i+j]位置的数b = t/10;//进位//len = max(len, j + i);}len = i+j-1 //最终的位数}for( i = len; i >= 0; -- i) //倒置输出printf("%d", ans[i]);printf("\n");}return 0;
}方法二（分治法）
分治算法解题的一般步骤：
- 分解：将要解决的问题划分为若干个规模较小的同类问题
- 求解：当子问题划分的足够小时，用较简单的方法解决
- 合并：按原问题的要求，将子问题的解逐层合并构成原问题的解
①两个大整数在理想状态下：就是两个大整数的位数相同
现在有两个大整数X,Y; 设X, Y是n位十进制整数，分段表示如下:
即 X=A*10^(n/2)+B, Y=C*10^(n/2)+D 则:
本来可以直接算AD+BC，但是这样效率变低了，所以对AD+BC进行分解优化后得：
计算成本：3次n/2位乘法，6次不超过n位加减法，2次移位，所有加法和移位共计O(n)次运算。由此可得
理想状态下c语言代码：（不超过long long 型，后面做法会用字符串接收大整数）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define sign(x) ((x>0)?1:-1)//_int64等同于long long
//%I64d等同于%lld_int64 mutipy(_int64 a,_int64 b,int num){ //两个long long 类型的大整数相乘，后面会用字符串做法解决int s=sign(a)*sign(b);a=(a>0)?a:-a ;b=(b>0)?b:-b ;if(num==0) //递归出口，return 0;else if(num==1){ //当a,b只有一位数时，直接相乘return s*a*b; }else{_int64 A=a/(int)pow(10,(int)(num/2)); //分离大整数a的高位_int64 B=a%(int)pow(10,(int)(num/2)); //分离大整数a的低位_int64 C=b/(int)pow(10,(int)(num/2)); //分离大整数b的高位_int64 D=b%(int)pow(10,(int)(num/2)); //分离大整数b的低位_int64 AC=mutipy(A,C,(int)(num/2)); //分治计算AC_int64 BD=mutipy(B,D,(int)(num/2)); //分治计算BD_int64 ABCD=mutipy((A-B),(D-C),(int)(num/2))+AC+BD; //计算(A-B)(D-C)+AC+BDreturn s*(_int64)(AC*pow(10,(int)(num/2)+(int)(num/2))+ABCD*pow(10,(int)(num/2))+BD); //返回结果}
}
int main(){_int64 a,b,c,temp; //long long a,b,c;int len1=0,len2=0;while(scanf("%I64d %I64d",&a,&b)){temp=a;while(temp){ //计算a的位数len1++;temp=temp/10;} c=mutipy(a,b,len1);printf("%I64d\n",c); }return 0;
}其实上述有个缺陷：那就是只能是long long 类型的大整数相乘，超出了long long 型就会报错。解决方法看下面的做法
②两个大整数在非理想状态下：就是两个大整数的位数不相同
我们还是假设有两个大整数X、Y，它们的位数不相同，现在要求X*Y的乘法，我们采用分治的算法，将X、Y分别拆分为A与B、C与D，如下图:
上式一共需要进行2次xn0的乘法（AC、AD各一次）、2次yn0的乘法（AC、BC各一次）和3次加法，因而该算法的时间复杂度为
跟上面一样，对AD+BC进行分解优化得：
修改后的时间复杂度：
由于T(min(m,n))<T(m)+T(n),所以修改后的算法更好，时间复杂度：T(m+n)=O(nlog3)=O(n1.59)
非理想状态下的c语言代码：（不超过long long 型，后面做法会用字符串接收大整数）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define sign(x) ((x>0)?1:-1)
//_int64等同于long long
//%I64d等同于%lld_int64 mutipy(_int64 a,int numa,_int64 b,int numb){ //两个long long 类型的大整数相乘，后面会用字符串做法解决int s=sign(a)*sign(b);a=(a>0)?a:-a ;b=(b>0)?b:-b ;if(numa==0||numb==0) //递归出口，return 0;else if((numa==1&&numb==1)||numa==1||numb==1){ //当a,b只有一位数时，直接相乘return s*a*b; }else{int num1=numa/2; //定义了大整数a的低位的位数x0int num2=numa-num1; //定义了大整数a的高位的位数x1int num3=numb/2; //定义了大整数b的低位的位数x2int num4=numb-num3; //定义了大整数b的高位的位数x3_int64 A=a/(int)pow(10,num1); //分离大整数a的高位_int64 B=a%(int)pow(10,num1); //分离大整数a的低位_int64 C=b/(int)pow(10,num3); //分离大整数b的高位_int64 D=b%(int)pow(10,num3); //分离大整数b的低位_int64 AC=mutipy(A,num2,C,num4); //分治计算AC_int64 BD=mutipy(B,num1,D,num3); //分治计算BD_int64 ABCD=mutipy(((_int64)(A*pow(10,num1))-B),num2,(D-(_int64)(C*pow(10,num1))),num4); //计算(A*10^num1-B)(D-C*10^num3)return s*(_int64)(2*AC*pow(10,(num1+num3))+ABCD+2*BD); //返回结果 }
}
int main(){_int64 a,b,c,temp; //long long a,b,c;int len1=0,len2=0;while(scanf("%I64d %I64d",&a,&b)){temp=a;while(temp){ //计算a的位数len1++;temp=temp/10;}temp=b;while(temp){ //计算b的位数len2++;temp=temp/10;} c=mutipy(a,len1,b,len2);printf("%I64d\n",c); } return 0;
}非理想状态下的c语言代码：（任意位数相乘，可以超出longlong类型）
#include<stdio.h>
#include<string.h>
int result[255];void cal( char a[],int numa,char b[],int numb,int s){int num1=numa/2; //num1为B的位数，B属于低位的那一部分int num2=numa-num1; //num2为A的位数，A属于高位的那一部分int num3=numb/2; //num3为D的位数，D属于低位的那一部分int num4=numb-num3; //num4为C的位数，C属于高位的那一部分char A[255],B[255],C[255],D[255];int k=0;if(numa==0||numb==0) //当位数为0时return ;else if(numa==1&&numb==1){ //分治递归到当数组a和b的位数全为1时result[s]+=(a[0]-'0')*(b[0]-'0'); //直接计算，把他的结果直接加到对应数组result的位置return;}else{ //当数组a和b的位数至少有一个不为1时for(int i=0;i<num2;i++) //获取数组a的高位部分AA[k++]=a[i];k=0;for(i=num2;i<numa;i++) //获取数组a的低位部分BB[k++]=a[i];k=0;for(i=0;i<num4;i++) //获取数组b的高位部分CC[k++]=b[i];k=0;for(i=num4;i<numb;i++) //获取数组b的高位部分DD[k++]=b[i];cal(A,num2,C,num4,s+num1+num3); //AC ,在result[s+num1+num3]的位置存储AC，也是说偏移s+num1+num3位，s初始化为0cal(B,num1,C,num4,num3+s); //BC，偏移num3+s位cal(A,num2,D,num3,num1+s); //AD,偏移num1+s位cal(B,num1,D,num3,s); //BD，偏移s位}}void exchange(int result[],int len){ //将result数组中的值进行整理，转化输出int i = 0;int t,p1,p2;while(i<=len){ //以特殊数最大位数为终止条件 if(result[i] < 10); //当result[i]的值小于10，就不处理，直接保存在result[i]中else if(result[i] < 100){ //当0<=result[i]<100时t = result[i] % 10; //余数就是该位置result[i]的值p1 = result[i] / 10; //result[i]进位result[i] = t; //将余数t保存至result[i]中result[i+1] += p1; //进位把他加到result[i+1]中 }else{ //当result[i]>=100时t = result[i] % 10; //余数就是该位置result[i]的值p1 = result[i] / 10 % 10; //这是result[i]满十进位p2 = result[i] / 100; //这是result[i+1]满十进位 result[i] = t; //将余数t保存至result[i]中result[i+1] += p1; //进位把他加到result[i+1]中result[i+2] += p2; //进位把他加到result[i+2]中}i++; //位数加1}
}int main(){char a[100],b[100];int j,i=0,len1,len2;while(scanf("%s %s",a,b)!=EOF){len1=strlen(a);len2=strlen(b);cal(a,len1,b,len2,0); exchange(result,len1+len2); for(i=len1+len2-1;i>=0;){ //去高位的0去掉if(result[i]==0){ while(result[i]==0){i--;}}elsebreak;}for(j=i;j>=0;j--) //从非零的位置打印printf("%d",result[j]); printf("\n");}return 0;}
