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
下一步，是c0
c1
c2三个数组，依次移位相加，得到数组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]
_4
13
28
27
18
最后一步，是对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]
5
6
0
8
8
因此，依次输出，得到56088
123*456=56088
大数相乘亦此道理也~