大整数的乘法运算.doc

大整数的乘法运算－C语言版 在计算机中，长整型(long int)变量的范围是 -2147483648 至 2147483647，因此若用长整型变量做乘法运算，乘积最多不能超过 10位数。即便用双精度型(double)变量，也仅能保证 16 位有效数字的精度。在某些需要更高精度的乘法运算的场合，需要用别的办法来实现乘法运算。 比较容易想到的是做多位数乘法时列竖式进行计算的方法，只要写出模拟这一过程的程序，就能实现任意大整数的乘法运算。经过查阅资料，找到一种更易于编程的方法，即“列表法”。 下面先介绍“列表法”： 例如当计算8765 x 234时，把乘数与被乘数照如下列出，见表1： 8 7 6 5 8 7 6 5 2 16 14 12 10 2 3 24 21 18 15 3 4 32 28 24 20 4 表 1 表 2 把每个空格所在的行列的数字的乘积填入空格中，得表2。把表2中的数按图示斜线分组（横纵坐标和相等的数分为一组），把每组数的累加起来所得的和记在表格下方，见表 3： 16 14 12 10 24 21 18 15 32 28 24 20 16 38 65 56 39 20 表 3 最后把表格下方一行数作如下处理，见表4： 从最低位的 20 开始，保留个位数字“0”，把个位以外的数“2”进到前一位；把次低位的 39 加上低位进上来的 2 得 41，保留个位数字“1”，把“4”进到前一位；以此类推，直至最高位的 16，16 加上低位进上来的4得 20，保留“0”，把2进到最高位，得乘积答数 2051010。 16 38 65 56 39 20 2 16+4=20 38+7=45 65+6=71 56+4=60 39+2=41 留0进2 留5进4 留1进7 留0进6 留1进4 留0进2 2 0 5 1 0 1 0 表 4 根据以上思路就可以编写C 程序了，再经分析可得： 1、一个m 位的整数与一个 n 位的整数相乘，乘积为m+n-1 位或m+n 位。 2、程序中，用三个字符数组分别存储乘数、被乘数与乘积。由第 1 点分析知，存放乘积的字符数组 的长度应不小于存放乘数与被乘数的两个数组的长度之和。 3、可以把第二步“计算填表”与第三四步“累加进位”放在一起完成，可以节省存储表格 2所需的空间。 4、程序关键部分是两层循环，内层循环累计一组数的和，外层循环处理保留的数字与进位。 编写的程序如下： 程序 1 清单： /* multiply.c */ /* 11/20/2008 */ #define M 1000 #include stdio.h #include string.h void compute(char *a, char *b, char *c); void main(void) { char a[M], b[M], c[M * 2]; puts(Input multiplier :); gets(a); puts(Input multiplicand :); gets(b); compute(a, b, c); puts(Answer :); puts(c); //etchar(); } 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--) /* i 为坐标和 */ { sum = carry; if ((j = i - m) 0) j =