有趣的算法（十一） ——分治法：大数相乘

有趣的算法（十一）——分治法：大数相乘

（原创内容，转载请注明来源，谢谢）

太大的两个数字相乘，有可能会超出计算机的位数，需要人工进行转化。

1、原始解法

最原始的解法，是乘法的逐个位对应的相乘后相加，这里需要的时间复杂度是O(n2)。

2、尝试优化

用分治法的思想进行优化，即将一个大的数字拆成两半的长度（不是数值的1/2，是字面上的折成两半），再进行计算。例如：

假设两个n位的二进制数A和B相乘，可以先将A分解成A1*2n/2+A2（A1为前面一半的位，A2为后一半的位，这里乘以2n/2是一个二进制的位移操作，即位移n/2位），同理B分解为B1*2 n/2+B2。

则A*B=( A1*2 n/2+A2)*(B1*2 n/2+B2)=A1*B1*2n +(A1*B2+A2*B1)*2 n/2+A2*B2。这里的位移运算和加法运算的复杂度都是O(n)，故考虑这里的乘法，其复杂度主要是考虑n/2位的乘法四次：A1*B1、A1*B2、A2*B1、A2*B2。

即T(n)=4T(n/2)+θ(n)，根据算法中的master定理，算出结果是O(n2)。结果和上面的算法是一样的，但是有了分析思路。

3、再次优化

master定理中，n的阶数和T(n)=4T(n/2)+θ(n)中的4这个系数密切相关，对于当前场景来说，就是4次乘法太多了，要想办法减少乘法次数。

考虑到A1*B2+A2*B1= (A1- A2)*( B1-B2) + A1* B1 + A2 * B2，这里的A1* B1 + A2 * B2在整个A1*B1*2n+(A1*B2+A2*B1)*2 n/2+A2*B2中也可以用到，故可以减少一次乘法计算，只需要3次计算。

即T(n)=3T(n/2)+θ(n)，由master定理，得到结果是O(nlog3)≈O(n1.59)，达到优化的目的。

4、其他

如果折成一半的时候，还是数字太长，可以再折成一半，以此类推

相乘的关键是思想，实现这个的代码本身比较简单，就不详细描述。

——written by linhxx 2018.01.18