在《大数阶乘之计算从入门到精通－大数的表示》中,我们学习了如何表示和存储一个大数.在这篇文章中,我们将讨论如何对大数做乘法运算,并给出一个可以求出一个大整数阶乘的所有有效数字的程序.
大整数的存储和表示已经在上一篇文章做了详细的介绍.其中最简单的表示法是:大数用一个字符型数组来表示,数组的每一个元素表示一位十进制数字,高位在前,低位在后.那么,用这种表示法,如何做乘法运算呢?其实这个问题并不困难,可以使用模拟手算的方法来实现.回忆一下我们在小学时,是如何做一位数乘以多位数的乘法运算的.例如：2234*8.
我们将被乘数表示为一个数组A[],a[1],a[2],a[3],a[4]分别为2,2,3,4,a[0]置为0.
Step1:从被乘数的个位a[4]起,取出一个数字4.
Step2:与乘数8相乘,其积是两位数32,其个位数2作为结果的个位,存入a[4],十位数3存入进位c.
Step3:取被乘数的上一位数字a[3]与乘数相乘,并加上上一步计算过程的进位C,得到27,将这个数的个位7作为结果的倒数第二位,存入a[3],十位数2存入进位c.
Step4：重复Step3,取a[i]（i依次为4,3,2,1）与乘数相乘并加上c,其个位仍存入a[i], 十位数字存入c,直到i等于1为止.
Step5:将最后一步的进位c作为积的最高位a[0].
这一过程其实和小学学过的多位数乘以一位数的珠算乘法一模一样,学过珠算乘法的朋友还有印象吗?
在计算大数阶乘的过程中,乘数一般不是一位数字,那么如何计算呢?我们可以稍作变通,将上次的进位加上本次的积得到数P, 将P除以10的余数做为结果的本位,将P除以10的商作为进位.当被乘数的所有数字都和乘数相乘完毕后,将进位C放在积的最前面即可.下面给出C语言代码.
一个m位数乘以n位数,其结果为m+n-1,或者m+n位,所以需首先定义一个至少m+n个元素的数组,并置前n位为0.
计算一个m位的被乘数乘以一个n位的整数k,积仍存储于数组a
[cpp] view plaincopyprint?
01.void mul(unsigned char a[],unsigned long k,int m,int n)
02.{
03.int i;
04.unsigned long p;
05.unsigned long c=0;
06.
07.for ( i=m+n-1; i>=n;i--)
08.{
09.p= a[i] * k +c;
10.a[i]=(unsigned char)( p % 10);
11.c= p / 10;
12.}
13.
14.while (c>0)
15.{
16.a[i]=(unsigned char)( c % 10);
17.i--;
18.c /=10;
19.}
20.}
21.
22.int main(int argc,char* argv[])
23.{
24.int i;
25.unsigned char a[]={0,0,0,2,3,4,5};
26.mul(a,678,4,3);
27.i=0;
28.while ( a[i]==0)
29.i++;
30.for (;i
