C语言中超大整数乘法运算

C语言中超大整数乘法运算在计算机中，长整型(longint)变量的范围是-2147483648至2147483647，因此若用长整型变量做乘法运算，乘积最多不能超过10位数。即便用双精度型(double)变量，也仅能保证16位有效数字的精度。在某些需要更高精度的乘法运算的场合，需要用别的办法来实现乘法运算。比较容易想到的是做多位数乘法时列竖式进行计算的方法，只要写出模拟这一过程的程序，就能实现任意大整数的乘法运算。经过查阅资料，找到一种更易于编程的方法，即“列表法”。下面先介绍“列表法”：例如当计算8765x234时，把乘数与被乘数照如下列出，见表1：把表1中的数按图示斜线分组（横纵坐标和相等的数分为一组），把每组数的累加起来所得的和记在表格下方，见表2：从最低位的20开始，保留个位数字“0”，把个位以外的数“2”进到前一位；把次低位的39加上低位进上来的2得41，保留个位数字“1”，把“4”进到前一位；以此类推，直至最高位的16，16加上低位进上来的4得20，保留“0”，把2进到最高位，得乘积答数2051010。根据以上思路就可以编写C程序了，再经分析可得：1、一个m位的整数与一个n位的整数相乘，乘积为m+n-1位或m+n位。2、程序中，用三个字符数组分别存储乘数、被乘数与乘积。由第1点分析知，存放乘积的字符数组的长度应不小于存放乘数与被乘数的两个数组的长度之和。3、可以把第二步“计算填表”与第三四步“累加进位”放在一起完成，可以节省存储表格2所需的空间。4、程序关键部分是两层循环，内层循环累计一组数的和，外层循环处理保留的数字与进位。编写的程序如下：#defineMAXLENGTH1000#includestdio.h#includestring.hvoidcompute(char*a,char*b,char*c);voidmain(void){chara[MAXLENGTH],b[MAXLENGTH],c[MAXLENGTH*2];puts(Inputmultiplier:);gets(a);puts(Inputmultiplicand:);gets(b);compute(a,b,c);puts(Answer:);puts(c);getchar();}voidcompute(char*a,char*b,char*c){inti,j,m,n;longsum,carry;m=strlen(a)-1;n=strlen(b)-1;for(i=m;i=0;i--)a[i]-='0';for(i=n;i=0;i--)b[i]-='0';c[m+n+2]='\0';carry=0;for(i=m+n;i=0;i--)/*i为坐标和*/{sum=carry;if((j=i-m)0)j=0;for(;j=i&&j=n;j++)/*j为纵坐标*/sum+=a[i-j]*b[j];/*累计一组数的和*/c[i+1]=sum%10+'0';/*算出保留的数字*/carry=sum/10;/*算出进位*/}if((c[0]=carry+'0')=='0')/*ifnocarry,*/c[0]='\040';/*c[0]equalstospace*/}效率分析：用以上算法计算m位整数乘以n位整数，需要先进行mxn次乘法运算，再进行约m+n次加法运算和m+n次取模运算(实为整数除法)。把这个程序稍加修改，让它自己产生乘数与被乘数，然后计算随机的7200位整数互乘，在Cyrix6x86pr166机器的纯DOS方式下耗时7秒(用BorlandC3.1编译)。经过改进，此算法效率可以提高约9倍。注意到以下事实：8216547x96785将两数从个位起，每3位分为节，列出乘法表，将斜线间的数字相加；821654796785将表中最后一行进行如下处理：从个位数开始，每一个方格里只保留三位数字，超出1000的部分进位到前一个方格里；所以8216547x96785=795238501395也就是说我们在计算生成这个二维表时，不必一位一位地乘，而可以三位三位地乘；在累加时也是满1000进位。这样，我们在计算m位整数乘以n位整数，只需要进行mxn/9次乘法运算，再进行约(m+n)/3次加法运算和(m+n)/3次取模运算。总体看来，效率约是前一种算法的9倍。有人可能会想：既然能够三位三位地乘，为什么不4位4位甚至5位5位地乘呢？那不是可以提高16乃至25倍效率吗？听我解来：本算法在累加表中斜线间的数字时，如果用无符号长整数(范围0至~4294967295)作为累加变量，在最不利的情况下(两个乘数的所有数字均是9)，能够累加约4294967295/(999*999)=4300次，也就是能够准确计算任意两个均不超过12900(每次累加的结果值三位，故4300*3=12900)位的整数相乘。如果4位4位地乘，在最不利的情况下，能够累加约4294967295/(9999*9999)=43次，仅能够确保任意两个不超过172位的整数相乘，没有什么实用价值，更不要说5位了。请看改进后的算法的实例程序：该程序随机产生两个72xx位的整数，把乘数与积保存在result.txt中。在BorlandC++3.1中用BCC-3-O2-G-mh-Z-f287-pr-T-dashu.cpp编译生成的exe文件在Cyrix6x86pr166的机器上运行耗时0.82秒。程序2清单：#includeconio.h#includestring.h#includestdio.h#includestdlib.h#includetime.h#defineN7200//作72xx位的整数乘法intmax(int,int,int);intinitarray(inta[]);voidwrite(inta[],intl);FILE*fp;voidmain(){inta[5000]={0},b[5000]={0},k[10001]={0};//声明存放乘数、被乘数与积的数组clock_tstart,end;//声明用于计时的变量unsignedlongc,d,e;//声明作累加用的无符号长整数变量inti,j,la,lb,ma,mi,p,q,t;//声明其它变量randomize();//初始化随机数la=initarray(a);//产生被乘数，并返回其长度lb=initarray(b);//产生乘数，并返回其长度if(lalb)//如果被乘数长度小于乘数，则交换被乘数与乘数{p=(lbla)?lb:la;for(q=0;qp;q++)//交换被乘数与乘数t=a[q],a[q]=b[q],b[q]=t;t=la,la=lb,lb=t;//交换被乘数的长度与乘数的长度}start=clock();//开始计时c=d=0;//清空累加变量，其中C用于累加斜线间的数，d用作进位标志for(i=la+lb-2;i=0;i--)//累加斜线间的数，i为横纵坐标之和{c=d;//将前一位的进位标志存入累加变量cma=max(0,i-la+1,i-lb+1);//求累加的下限mi=(ila-1)?(la-1):i;//求累加的上限for(j=ma;j=mi;j++)//计算出横纵坐标之和为i的单元内的数,并累加到C中c+=(long)a[j]*b[i-j];d=c/1000;//求进位标志if(c999)c%=1000;//取c的末三位k[i]=c;//保存至表示乘积的数组k[]}e=k[0]+1000*d;//求出乘积的最高位end=clock();//停止计时fp=fopen(result.txt,w+);//保存结果到result.txtprintf(\nTheelapsedtimewas:%3.4f\n,(end-start)/CLK_TCK);//打印消耗的时间fprintf(fp,%d,a[0]);//打印被乘数最高位write(a,la);//打印被乘数其他位fprintf(fp,%d,b[0]);//打印乘数最高位write(b,lb);//打印乘数其他位fprintf(fp,%ld,e);//打印乘积最高位write(k,la+lb-1);//打印乘积其他位fclose(fp);}max(inta,intb,intc){intd;d=(ab)?a:b;return(dc)?d:c;}intinitarray(inta[]){intq,p,i;q=N+random(100);if(q%3==0)p=q/3;elsep=q/3+1;for(i=0;ip;i++)a[i]=random(1000);if(q%3==0)a[0]=100+random(900);if(q%3==2)a[0]=10+random(90);if(q%3==1)a[0]=1+random(9);returnp;}voidwrite(inta[],intl){inti;charstring[10];for(i=1;il;i++){itoa(a[i],string,10);if(strlen(string)==1)fprintf(fp,00);if(strlen(string)==2)fprintf(fp,0);fprintf(fp,%s,string);if((i+1)%25==0)fprintf(fp,\n);}fprintf(fp,\n);fprintf(fp,\n);}