Question

求高手帮忙——大整数乘法的算法

Answer 1

就是高精度乘
模拟小学时学乘法竖式的方法
比如123*456
首先用一个数组a保存123
a[0]=1;a[1]=2;a[2]=3;
再用另外一个数组b保存456
b[0]=4;b[1]=5;b[2]=6;
做三次高精乘单精，如下：
a乘以b[0]，得到c0数组为
c0[0]=a[0]*b[0]=4
c0[1]=a[1]*b[0]=8
c0[2]=a[2]*b[0]=12
a乘以b[1]，得到c1数组为
c1[0]=a[0]*b[1]=5
c1[1]=a[1]*b[1]=10
c1[2]=a[2]*b[1]=15
同理，a乘以b[2]，得到c2数组为
c2[0]=6
c2[1]=12
c2[2]=18
下一步，是c0c1c2三个数组，依次移位相加，得到数组d，如下：
c0[0]c0[1]c0[2]
______c1[0]c1[1]c1[2]
____________c2[0]c2[1]c2[2]
--------------------------------
_d[0]d[1]d[2]d[3]d[4]
_413282718
最后一步，是对d数组的整理啦
从个位开始，每一位，如果大于9，则求模，前一位进位
for(i=4;i>0;i--)
__if(d[i]>9)
__{
____d[i-1]+=d[i]/10;
____d[i]=d[i]%10;
__}
经过整理，数组d各元素如下：
d[0]d[1]d[2]d[3]d[4]
56088
因此，依次输出，得到56088
123*456=56088
大数相乘亦此道理也~