大整数乘法的算法分析(r12笔记第42天)-阿里云开发者社区

开发者社区> 人工智能> 正文

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

简介:    昨天看了下Paxos协议,比我想象的要复杂。每次都没能耐着性子看完。但是隐隐感觉就跟钓鱼一般(尽管我没用真实试过),如果有耐性,能坚持还是能够明白的。   于是乎,我拿起了大学学习的一本算法书,突然发现里面有很多我早已忘记的东西,记得有一个算法我琢磨了好几天,结果老师上课几分钟就讲完了,所以大学里算法课真是让人费神的课程,工作以后算法自己去写的场景还是少很多,我们更多是去用,但是实际证明不是不重要,而是我们自己没有重视。

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

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

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

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

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

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

图片.png

所以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;

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

 

版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章