大整数乘法的算法分析(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;

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

原文发布于微信公众号 - 杨建荣的学习笔记(jianrong-notes)

原文发表时间:2017-04-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码神联盟

语音识别 | Java 实现 AI 人工智能技术 - 语音识别功能

说到语音识别、语音翻译、图像识别、人脸识别等等,现在已经非常非常非常普及了,看过‘最强大脑’的朋友,也应该对‘小度’这个机器人有所了解,战胜国际顶尖的‘大脑’-...

2.1K6
来自专栏杨光的专栏

千亿关系链下的新增共同好友计算

本文介绍一种千亿关系链下的日新增共同好友挖掘算法 --NTE 算法。该算法基于分治的思想,将新增共好友计算问题,转换为更易于运算与实现的三角形计算问题。

9920
来自专栏算法channel

动态规划中篇:爬楼梯

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

4099
来自专栏我是攻城师

统计学里面的百分位数是什么意思

5985
来自专栏阿凯的Excel

乘积求和及符合某个条件的乘积求和

如何得到两个数组的乘积求和呢??案例如下: ? 已知每个地市的销售单价和销售数量,需要知道整个表的销售总金额,怎么做??? 普通青年做法: ? 小编客观公正...

4319
来自专栏小樱的经验随笔

CTF---密码学入门第三题 奇怪的短信

奇怪的短信分值:10 来源: Ayn 难度:易 参与人数:5117人 Get Flag:2623人 答题人数:2858人 解题通过率:92% 收到一条奇怪的...

4056
来自专栏web前端教室

坚持学一年很难,那坚持一周怎么样?[先行者课程-时间倒数-Data对象]

时间是线性的,所以依附于时间的事情也是线性发展的。例如学js,谁能一下学成高手?谁有js学习秘籍?高手只能跟你装b,却不能带你起飞。 这世界我看只有砖与狗粮是真...

2119
来自专栏程序人生

抽象的能力

人类的智商从低幼逐渐走向成熟的标志之一就是认识和运用数字的能力。当我们三四岁的时候,数数虽然能够熟练地对一百以内的数字随心所欲地倒背如流,但数字对孩童时代的我们...

3457
来自专栏算法channel

动态规划|相邻约束下的最优解

本篇进一步介绍动态规划的基本应用。 1 题目 You are a professional robber planning to rob houses alon...

3874
来自专栏海天一树

NOIP普及组初赛题型分析

初赛的考察内容的一部分是计算机的基础知识,比如进制转换,工作原理,算法原理、历史事件名人等。这些对于大部分第一次参加noip的同学来说应该比较陌生,这样的知识只...

772

扫码关注云+社区

领取腾讯云代金券