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

《C语言中超大整数乘法运算.pdf》由会员分享，可在线阅读，更多相关《C语言中超大整数乘法运算.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、的数按图示斜线分组（横纵坐标和相等的数分为一组），把每组数的累加起来所得的和记在表格下方，见表 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、析知，存放乘积的字符数组 的长度应不小于存放乘数与被乘数的两个数组的长度之和。3、可以把第二步“计算填表”与第三四步“累加进位”放在一起完成，可以节省存储表格 2 所需的空间。4、程序关键部分是两层循环，内层循环累计一组数的和，外层循环处理保留的数字与进位。编写的程序如下：#define MAXLENGTH 1000#include#include void compute(char*a,char*b,char*c);void main(void)char aMAXLENGTH,bMAXLENGTH,cMAXLENGTH*2;puts(Input multiplier:);gets(a);pu

4、ts(Input multiplicand:);gets(b);compute(a,b,c);puts(Answer:);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(b)-1;for(i=m;i=0;i-)ai-=0;for(i=n;i=0;i-)bi-=0;cm+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

5、为纵坐标*/sum+=ai-j*bj;/*累计一组数的和*/ci+1=sum%10+0;/*算出保留的数字*/carry=sum/10;/*算出进位*/if(c0=carry+0)=0)/*if no carry,*/c0=040;/*c0 equals to space*/.效率分析：用以上算法计算 m 位整数乘以 n 位整数，需要先进行 m x n 次乘法运算，再进行约 m+n 次加法运算和 m+n 次取模运算(实为整数除法)。把这个程序稍加修改，让它自己产生乘数与被乘数，然后计算随机的 7200 位整数互乘，在 Cyrix 6x86 pr166 机器的纯 DOS 方式下耗时 7 秒(用

6、Borland C3.1 编译)。经过改进，此算法效率可以提高约 9 倍。注意到以下事实：8216547 x 96785 将两数从个位起，每 3 位分为节，列出乘法表，将斜线间的数字相加；8 216 547 96 785 将表中最后一行进行如下处理：从个位数开始，每一个方格里只保留三位数字，超出 1000 的部 分进位到前一个方格里；所以 8216547 x 96785=795238501395 也就是说我们在计算生成这个二维表时，不必一位一位地乘，而可以三位三位地乘；在累加时也是满 1000 进位。这样，我们在计算 m 位整数乘以 n 位整数，只需要进行 m x n/9 次乘法运算，再进行约

7、(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 位地乘，在最

8、不利的情况下，能够累加约 4294967295/(9999*9999)=43 次，仅能够确保任意两个不超过 172 位的整数相乘，没有什么实用价值，更不要说5 位了。请看改进后的算法的实例程序：该程序随机产生两个 72xx 位的整数，把乘数与积保存在 result.txt 中。在 Borland C+3.1 中用 BCC-3-O2-G-mh-Z-f287-pr-T-dashu.cpp 编译生成的 exe 文件在 Cyrix 6x86 pr166 的机器上运行耗时 0.82 秒。程序 2 清单：#include#include#include#include#include#define N 7

9、200/作 72xx 位的整数乘法 int max(int,int,int);int initarray(int a);void write(int a,int l);FILE*fp;void main()int a5000=0,b5000=0,k10001=0;/声明存放乘数、被乘数与积的数组 clock_t start,end;/声明用于计时的变量 unsigned long c,d,e;/声明作累加用的无符号长整数变量 int i,j,la,lb,ma,mi,p,q,t;/声明其它变量 randomize();/初始化随机数 .la=initarray(a);/产生被乘数，并返回其长度

10、lb=initarray(b);/产生乘数，并返回其长度 if(lala)?lb:la;for(q=0;q=0;i-)/累加斜线间的数，i 为横纵坐标之和 c=d;/将前一位的进位标志存入累加变量 c ma=max(0,i-la+1,i-lb+1);/求累加的下限 mi=(ila-1)?(la-1):i;/求累加的上限 for(j=ma;j999)c%=1000;/取 c 的末三位 ki=c;/保存至表示乘积的数组 k e=k0+1000*d;/求出乘积的最高位 end=clock();/停止计时 fp=fopen(result.txt,w+);/保存结果到 result.txt printf

11、(nThe elapsed time was:%3.4fn,(end-start)/CLK_TCK);/打印消耗的时间.fprintf(fp,%d,a0);/打印被乘数最高位 write(a,la);/打印被乘数其他位 fprintf(fp,%d,b0);/打印乘数最高位 write(b,lb);/打印乘数其他位 fprintf(fp,%ld,e);/打印乘积最高位 write(k,la+lb-1);/打印乘积其他位 fclose(fp);max(int a,int b,int c)int d;d=(ab)?a:b;return(dc)?d:c;int initarray(int a)int

12、q,p,i;q=N+random(100);if(q%3=0)p=q/3;else p=q/3+1;for(i=0;ip;i+)ai=random(1000);if(q%3=0)a0=100+random(900);if(q%3=2).a0=10+random(90);if(q%3=1)a0=1+random(9);return p;void write(int a,int l)int i;char string10;for(i=1;il;i+)itoa(ai,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);