大整数乘法的算法分析(r12笔记第42天)

昨天看了下Paxos协议，比我想象的要复杂。每次都没能耐着性子看完。但是隐隐感觉就跟钓鱼一般（尽管我没用真实试过），如果有耐性，能坚持还是能够明白的。

于是乎，我拿起了大学学习的一本算法书，突然发现里面有很多我早已忘记的东西，记得有一个算法我琢磨了好几天，结果老师上课几分钟就讲完了，所以大学里算法课真是让人费神的课程，工作以后算法自己去写的场景还是少很多，我们更多是去用，但是实际证明不是不重要，而是我们自己没有重视。

如果让自己的写一些，就会发现真是漏洞百出。

我看了一个有意思的问题，是关于大整数的乘法。在计算机里是使用二进制，所以通常对于数值的计算，假设X和Y都是n的二进制整数，那么算法XY的执行代价其实会很高，比如222*333即三位数和三位数的乘法，需要9次运算（步运算）才能得到结果。如果这个数字很大，比如100位，那么计算机本身去做这个事情程序里的数值类型就会受限。我们怎么去解决这类问题，一种比较直接的思想就是分而治之。

根据课本中的精髓，是把X和Y拆分成两部分，因为是二进制的n位整数，所以就把这个整数分成两部分。

所以二进制数X就会分为下面两部分A和B,每部分占用n/2位，假设n是2的幂，对于Y也是如此，分为C和D两部分

所以X=A2n/2+B Y=C2n/2+D

按照这个思路，XY的结果就是：

XY=(A2n/2+B) (C2n/2+D)=AC2n+(AD+BC)2n/2+BD

所以上面的运算的复杂度就是4次n/2位证书的乘法（AC,AD,BC,BD），3次加法，2次移位（2n和2n/2）,所以这样看来整体来看这种算法没有什么改进，如果要得到一个精确的理论值，那就是

当n>1的时候 T(n)=4T(n/2)+O(n)

其实就是这种情况下T(n)=O(n2)

所以上面忙活了一圈，发现竟然没有什么改进，我们也不能气馁，可以对上面的结果再进行推敲。

XY=(A2n/2+B) (C2n/2+D)=AC2n+(AD+BC)2n/2+BD

=AC2n+(（A-B）(D-C)-AC+BD)2n/2+BD

这个地方很多同学说搞这么复杂干嘛，其实就是做了一些成本的缩减。

这个复杂度就需要3次的n/2位数的乘法（AC,BD,(A-B)(D-C)）

6次的加法，减法和2次的移位

这个时间复杂度就是当n>1时， T(n)=3T(n/2)+O(n)

这个改进是多大呢，T(n）=O(nlog3) 因为log3的值是1.59

所以T(n)=O(n1.59)

这样就会由此得出，这个算法的意义所在，在大批量的数据运算中，这个改进可是一个相当可观的优化。

而对于时间复杂度的计算，而二分查找中也有类似的思路。

比如查看两个数的平均值

middle=(left+right)/2 这个逻辑没错，但是如果两个数都很大，就很可能会出现溢出的情况，所以就需要迂回解决。 可以使用下面的形式来避免。 middle=left+(right-left)/2;

所以说算法博大精深，细节决定成败，水平高低就体现在这些地方。