大整数的乘法运算.doc

《大整数的乘法运算.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、，见表1：87658765216141210232421181534322824204表1表2把每个空格所在的行列的数字的乘积填入空格中，得表2。把表2中的数按图示斜线分组（横纵坐标和相等的数分为一组），把每组数的累加起来所得的和记在表格下方，见表3：161412102421181532282420163865563920表3最后把表格下方一行数作如下处理，见表4：从最低位的20开始，保留个位数字“0”，把个位以外的数“2”进到前一位；把次低位的39加上低位进上来的2得41，保留个位数字“1”，把“4”进到前一位；以此类推，直至最高位的16，1

3、6加上低位进上来的4得20，保留“0”，把2进到最高位，得乘积答数2051010。163865563920216+4=2038+7=4565+6=7156+4=6039+2=41留0进2留5进4留1进7留0进6留1进4留0进22051010表4根据以上思路就可以编写C程序了，再经分析可得：1、一个m位的整数与一个n位的整数相乘，乘积为m+n-1位或m+n位。2、程序中，用三个字符数组分别存储乘数、被乘数与乘积。由第1点分析知，存放乘积的字符数组的长度应不小于存放乘数与被乘数的两个数组的长度之和。3、可以把第二步“计算填表”与第三四步“累加进位”

4、放在一起完成，可以节省存储表格2所需的空间。4、程序关键部分是两层循环，内层循环累计一组数的和，外层循环处理保留的数字与进位。编写的程序如下：程序1清单：/*multiply.c*//*11/20/2008*/#defineM1000#include#includevoidcompute(char*a,char*b,char*c);voidmain(void){chara[M],b[M],c[M*2];puts("Inputmultiplier:");gets(a);puts("Inputmultiplic

5、and:");gets(b);compute(a,b,c);puts("Answer:");puts(c);//etchar();}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]='';carry=0;for(i=m+n;i>=0;i--)/*i为坐标和*/{sum=carry;if((j=i

6、-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]='40';/*c[0]equalstospace*/}效率分析：用以上算法计算m位整数乘以n位整数，需要先进行mxn次乘法运算，再进行约m+n次加法运算和m+n次取模运算(实为整数除法)。把这个程序稍加修改，让它自己产生乘

7、数与被乘数，然后计算随机的7200位整数互乘，在Cyrix6x86pr166机器的纯DOS方式下耗时7秒(用BorlandC3.1编译)。经过改进，此算法效率可以提高约9倍。注意到以下事实：8216547x96785将两数从个位起，每3位分为节，列出乘法表，将斜线间的数字相加；8216547967857682073652512628016956042939576827016222072429395将表中最后一行进行如下处理：从个位数开始，每一个方格里只保留三位数字，超出1000的部分进位到前一个方格里；768270162220724293957

8、68+2727016+222222072+429=795=27238=222501395795238501395所以8216547x96785=795