大整数乘法

1.算法原理

如果我们想要计算两个较大的数字相乘的时候,由于计算机硬件限制可能无法计算,因此我们可以将每个乘数用加法和乘法做分解,当分解到每个因子只是一位数的时候,乘法就很简单了,这也是一种分治法。

(1)分解:首先将2个大整数a(n位)、b(m位)分解为两部分:

ahal bhbl

然后,

其中ah、al为n/2位,bh、bl为m/2位。两个大整数a、b相乘转换成了4个乘法运算,而乘数的位数变为了原来的一半。

(2)求解子问题。继续分解每个乘法运算,直到分解有一个乘数为1位数时停止分解,进行乘法运算并记录结果。

(3)合并。将计算出的结果相加并回溯,求出最终结果。

2.算法设计

(1)数据结构。将两个大数以字符串的形式输入,然后定义结构体Node,其中s[]数组用于存储大数,注意是倒序存储!(因为乘法加法运算中有可能出现进位,倒序存储时可以让进位存储在数组的末尾)。l表示长度,c表示幂次。两个大叔的初始次幂是0.如下所示:

 

(2)划分函数。其中,cp()函数用于将一个n位的数分成两个n/2的数并存储,记录它的次幂和长度。

 

(3)乘法运算。定义的mul()函数用于将两个数进行相乘,不断进行分解,直到有一个乘数为1位时停止,让这两个数相乘,并记录结果回溯。

 

(4)合并函数

add()函数将分解得到的数进行相加合并。

 

3.完整代码

 

4.复杂度分析

递推可得,T(n)=4x(Tn/2x)+(2x-1)O(n)。地推最终规模为1,令n=2x,则x=logn,那么有:

T(n)=n2