乘法计算列表法-资格问答-漫游猫

大整数的乘法在计算机中，长整形（long int）变量的范围是-2147483648至2147483647，因此若用长整形变量做乘法运算，乘积最多不能超过10位数。

即便用双精度（double）变量，也仅能保证16位有效数字的精度。在某些需要更高精度的乘法运算场合，需要用别的办法来实现运算。比较容易想到的是做多位数乘法时列竖式进行计算的方法，只要写出模拟这一过程的程序，就能实现任意大整数的乘法运算。经过查阅资料，找到一种更易于编程的方法，即“列表法”。下面先介绍“列表法”:例如当计算8765*234时，把乘数和被乘数照如下列出，见表1：8765*161412102242118153322824204 表一161412102421181532282420163865563920163865563920216+4=2038+7=4565+6=7156+4=6039+2=41留2留0进2留5进4留1进7留0进6留1进4留0进22051010根据以上思路就可以编写C程序了，再经分析可得：1，一个m位的整数与一个n位的整数相乘，乘积为m+n-1位或m+n位。

2，程序中，用三个字符数组分别存储乘数，被乘数与乘积。由第1点分析知，存放乘积的字符数组饿长度应不小于存放乘数与被乘数的两个数组的长度之和。

3，可以把第二步“计算填表”与第三四步“累加进位”放在一起完成，可以节省存储表格2所需的空间。

4，程序关键部分是两层循环，内层循环累计一数组的和，外层循环处理保留的数字和进位。[cpp] view plain copy#define MAXLENGTH 1000#include <stdio.h>#include <string.h>void compute(char * a, char * b,char *c){int i,j,m,n;long sum,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--) { sum=carry; if((j=(i-m))<0) j=0; for(;j<=i&& j <=n;j++) sum += a[i-j]b[j]; c[i+1] = sum %10 + '0'; carry = sum/10; } if((c[0]=carry+'0')=='0') c[0] = '/040'; }int main(){ char a[MAXLENGTH],b[MAXLENGTH],c[MAXLENGTH*2]; puts("Input multiplier"); gets(a); puts("Input multiplier"); gets(b); compute(a,b,c); puts("Answer:"); puts(c); getchar();}效率分析：用以上算法计算m位整数乘以n位整数，需要先进行m*n次乘法，再进行约m+n次加法运算和m+n次取模运算（实为整数除法）。把这个程序稍加修改，让它自己生产乘数和被乘数，然后计算机随机的7200为整数互乘。经过改进，此算法效率可以提高约9倍。注意到以下事实：8216547*96785 将两数从个位起，每3位分为节，列出乘法表，将斜线间的数字相加：8216547 96 7858216547*76820736525129662501695604293957857682073652512625016956042939576827016222072429395将表中最后一行进行如下处理：从个位数开始，每一个方格里只保留三个数字，超出1000的部分进位到前一个方格里：76827016222072429395768+27=79527016+222=27238222072+429=222501留395进429795238501395所以8216547*96785 = 795238501395 也就是说我们在计算生成这个二维表时，不必一位一位的乘，而可以三位三位的乘；在累加时也是满1000进位。这样，我们计算m位整数乘以n位整数，只需要进行m*n/9次乘法运算，再进行约（m+n）/3次加法运算和（m+n）/3次去摸运算。总体看来，效率是前一种算法的9倍。有人可能会想：既然能用三位三位的乘，为什么不能4位4位的乘，甚至5位。听我解来：本算法在累加表中斜线间的数字时，如果用无符号长整数（范围0至~4294967295）作为累加变量，在最不利的情况下（两个乘数的所有数字均为9），能够累加约4294967295/（999*999）=4300次，也就是能够准确计算任意两个约不超过12900（每次累加的结果“值”三位，故4300*3=12900）位的整数相乘。如果4位4位地乘，在最不利的情况下，能过累加月4294967295/(9999*9999)=43次，仅能够确保任意两个不超过172位的整数相乘，没什么实用价值，更不要说5位了。[cpp] view plain copy#include <stdio.h>#include <string.h>#include <conio.h>#include <stdlib.h>#include <time.h>#define N 7200 //做72xx位的整数乘法int max(int a,int b,int c){int d = (a >b) a:b;return (d>c) d:c;}int initarray(int a[]){ int q,p,i; q = N + random(100); if(q%3 ==0)p =q/3; elsep =q/3+1; for(i=0;i <p;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); return p; }void write(int a[],int l){ int i; char string[10]; for(i=1;i<l;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,""); } fprintf(fp,""); fprintf(fp,"");}FILE * fp;int main(){ int a[5000]={0},b[5000]={0},k[10001]={0}; unsigned long c,d,e;//申明作累加用的无符号长整数变量 int i,j,la,lb,ma,mi,p,q,t; randomize();//初始化随机数la = initarray(a);//被乘数lb = initarray(b);//乘数if(la < lb)//如果被乘数长度小于乘数，则交换被乘数与乘数{p = (lb > la) lb:la;for(q=0;q<p;q++) t=a[q],a[q]=b[q],b[q]=t;t =la,la=lb,lb =t;} c=d=0;for(i=la+lb-2;i>=0;i--)//累加斜线间的数，i位横纵坐标之和{c=d;//将前一位的进位标志存入累加变量Cma =max(0,i-la+1,i-lb+1);//求累加的下限 mi = (i > la) (la-1):i;//求累加的上限for(j=ma;;j<=mi;j++){ c+=a[j]b[i-j];}d=c/1000;//求进位标志if(c>999)c%=1000;//取c的后3位 k[i] = c;//保存至表示乘积的数组k[]}e = k[0] + 1000*d;//求出乘积的最高位fp = fopen("res.txt","w+");fprintf(fp,"%d",a[0]);//打印被乘数的最高位write(a,la);//打印被乘数其他位数fprintf(fp,"%d",b[0]);//打印乘数的最高位write(b,lb);//打印乘数其他位数fprintf(fp,"%d",e);//打印乘积的最高位write(k,la+lb-1);//打印乘积其他位数fclose(fp);}