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

1、C语言中超大整数乘法运算在计算机中，长整型(longint)变量的范围是-48至47,因此若用长整型变量做乘法运算，乘积最 多不能超过10位数。即便用双精度型(double)变量，也仅能保证16位有效数字的精度。在某些 需要更高精度的乘法运算的场合，需要用别的办法来实现乘法运算。比较容易想到的是做多位数乘法时列竖式进行计算的方法，只要写出模拟这一过程的程序，就能 实现任意大整数的乘法运算。经过查阅资料，找到一种更易于编程的方法，即列表法。下面先介绍列表法: 例如当”算8765x234时，把乘数与被乘数照如下列出，见表1：$7 I65X16141210242118153322824204表1把表

2、1中的数按图示斜线分组(横纵坐标和相等的数分为一组)，把每组数的累加起来所得的 和记在表格下方，见表2：161412102421181532282420163865563920表2从最低位的20开始，保留个位数字0，把个位以外的数2进到前一位；把次低位的39加上低 位进上来的2得41,保留个位数字1,把4进到前一位；以此类推,直至最高位的16, 16加 上低位进上来的4得20,保留0，把2进到最高位，得乘积答数2051010。163265563920216+4=2。38+7=4565+6=7156+4=6039+2=41留2留0进2留5进4留值7留说6留1进4留。进22057010表3根据以上

3、思路就可以编写C程序了，再经分析可得:1、一个m位的整数与一个n位的整数相乘，乘积为m+n-1位或m+n位。2、程序中，用三个字符数组分别存储乘数、被乘数与乘积。由第1点分析知，存放乘积的字符 数组的长度应不小于存放乘数与被乘数的两个数组的长度之和。3、可以把第二步计算填表与第三四步累加进位放在一起完成，可以节省存储表格2所需的 空间。4、程序关键部分是两层循环，内层循环累计一组数的和，外层循环处理保留的数字与进位。编写的程序如下：#define MAXLENGTH 1000#include <>#include <>void compute(char *a, char

4、 *b, char *c);void main(void)(char alMAXLENGTH, bMAXLENGTH, cMAXLENGTH * 2;puts(Mlnput multiplier :n);gets(a);puts(Mlnput multiplicand :”)； gets(b);compute(a, b, c);puts(MAnswer :n);Puts(c);getchar();)void compute(char *a, char *b, char *c)(int i, j, m, n;long sum, carry;m = strlen(a) -1;n = strlen(

5、b) -1;for (i = m; i >= 0; i-)ai -= 'O'；for (i = n; i >= 0; i-)bi -= 'O'cm + n + 2 = l0l;carry = 0;for (i = m + n; i >= 0; i-) /* i 为坐标和 */sum = carry;if (O = i-m)<0)j = 0;for (; j<=i &&j<=n; j+) /* j 为纵坐标 */sum += ai-j * bj；/* 累计一组数的和 7ci + 1 = sum % 10 + &#

6、39;O' /* 算出保留的数字 */carry = sum /10;/* 算出进位 */)if «c0 = carry+'O') = '0') /* if no carry, */c0 = '040' /* c0 equals to space */)效率分析：用以上算法计算m位整数乘以n位整数，需要先进行mxn次乘法运算，再进行约 m + n次加法运算和m + n次取模运算(实为整数除法)。把这个程序稍加修改，让它自己产生乘数 与被乘数，然后计算随机的7200位整数互乘，在Cyrix 6x86 prl66机器的纯DOS方式下

7、耗时7 秒(用Borland编译)。经过改进，此算法效率可以提高约9倍。注意到以下事实：8216547x96785将两数从个位起，每3位分为节，列出乘法表，将斜线间的 数字相加；8 216 54796 7858216547X76820736525129662501695604293957857682073652512625016956042939576827016222072429385将表中最后一行进行如下处理：从个位数开始，每一个方格里只保留三位数字，超出1000的部分进位到前一个方格里;76827016222072429385768+2727016十222222072十429取395进4

8、29=795=27238=222501395795238501395所以 8216547 x 96785 = 1395也就是说我们在计算生成这个二维表时，不必一位一位地乘，而可以三位三位地乘；在累加时也 是满1000进位。这样，我们在计算m位整数乘以n位整数，只需要进行mxn/9次乘法运算， 再进行约(m + n)/3次加法运算和(m + n)/3次取模运算。总体看来，效率约是前一种算法的9 倍。有人可能会想：既然能够三位三位地乘，为什么不4位4位甚至5位5位地乘呢那不是可以提 高16乃至25倍效率吗听我解来：本算法在累加表中斜线间的数字时，如果用无符号长整数(范 围0至95)作为累加变量，在

9、最不利的情况下(两个乘数的所有数字均是9),能够累加约 95/(999*999)=4300次，也就是能够准确计算任意两个均不超过12900(每次累加的结果,值11三 位，故4300*3=12900)位的整数相乘。如果4位4位地乘，在最不利的情况下,能够累加约 95/(9999*9999)=43次，仅能够确保任意两个不超过172位的整数相乘，没有什么实用价值，更 不要说5位了。请看改进后的算法的实例程序：该程序随机产生两个72xx位的整数，把乘数与积保存在中。在BorlandC"中用BCC -3 -02 -G -mh -Z -f287 -pr -T-编译生成的exe文件在Cyrix 6

10、x86 prl66的机器上运行耗时秒。 程序2清单：#include<>#include<>#include<>#include<>#include<>#define N 7200 作72xx位的整数乘法int max(int,int,int);int initarrayfint a);void write(int a,int I);FILE *fp;void main()(int a5000=0,b5000=0,k10001=0; 声明存放乘数、被乘数与积的数组 clock_t start, end; 声明用于计时的变量unsign

11、ed long c,d,e; 声明作累力口用的无符号长整数变量int声明其它变量randomize。; /初始化随机数la=initarray(a); 产生被乘数,并返回其长度lb=initarray(b); 产生乘数，并返回其长度if(la<lb) 如果被乘数长度小于乘数，则交换被乘数与乘数 (p=(lb>la)lb:la;for (q=0；q<p；q+) 交换被乘数与乘数t=aq/aq=bq,bq=t;t=la,la=lbjb=t; 交换被乘数的长度与乘数的长度 )start = clock();开始计时c=d=0;清空累加变量，其中CH于累加斜线间的数，d用作进位标志f

12、or(i=la+lb-2;i>=0;i-) 累加斜线间的数，i为横纵坐标之和 (c=d; 将前一位的进位标志存入累加变量cma=max(O,i-la+l,i-lb+l); 求累加的下限mi=(i>la-l)(la-l):i; 求累加的上限for(j=ma;j<=mi;j+) 计算出横纵坐标之和为i的单元内的数，并累加到C中c+=(long)aj*bi-j;d=c/1000; 求进位标志if(c>999)c%=1000; 取c的末三位ki=c; 保存至表示乘积的数组k)e=k0+1000*d; 求出乘积的最高位end = clock();停止计时fp = fopenR ”

13、w+“); 保存结果到printf(HnThe elapsed time was: %nH, (end - start) / CLK_TCK);打印消耗的时间一fprintf(fpJ%d，aO);打印被乘数最高位write(aja); 打印被乘数其他位fprintf(fp,"%d，bO);打印乘数最高位write(bjb); 打印乘数其他位fprintf(fpj%ld”,e); 打印乘积最高位write(k,la+lb-l); 打印乘积其他位fclose(fp);)max(int a,int b,int c)(int d;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+l;for(i=0;i<p;i+) ai=random(1000);if(q%3=0)a0=100+random(900);if(q%3=2)a0=10+random(90);if(q%3=l)a0=l+random(9);return p;) void write(int a,int I) int i;