有趣的算法(十一) ——分治法:大数相乘

有趣的算法(十一)——分治法:大数相乘

(原创内容,转载请注明来源,谢谢)

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

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

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2018-01-18

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏跟着阿笨一起玩NET

treeview 绑定文件夹和文件

441
来自专栏码匠的流水账

zuul自定义SimpleHostRoutingFilter

zuul的SimpleHostRoutingFilter主要用来转发不走eureka的proxy,里头是使用httpclient来转发请求的,但是有时候我们需要...

1272
来自专栏james大数据架构

CSS好看的按钮

好看的按钮 <style> .btn { BORDER-RIGHT: #7b9ebd 1px solid; PADDING-RIGHT: 2px; BORDE...

1997
来自专栏张善友的专栏

弹出式模态窗体选择文本控件

2006年就要到来了,最近比较忙,很少更新blog,今天发一个模态窗体选择文本控件辞旧迎新.新年在发几个asp.net2.0 webPart控件同各位分享: ...

1907
来自专栏菩提树下的杨过

基于sliverlight + wcf的web 文字版IM 示例

演示地址: http://task.24city.com/default.html 预览界面: ? 一、布局 采用Grid布局,5行2列 第一行:为登录/注册信...

3226
来自专栏张善友的专栏

通过SmtpClient发送Exchange会议邮件

看到C#中调用Outlook API 发起会议 ,这个完全可以用SMTP方式实现的,下面我的项目中使用的代码: 对于.NET而言,从2.0开始,发邮件已经是一件...

1929
来自专栏王磊的博客

MySQL数据库工具类之——DataTable批量加入MySQL数据库(Net版)

MySQL数据库工具类之——DataTable批量加入数据库(Net版),MySqlDbHelper通用类希望能对大家有用,代码如下: using MySql....

3619
来自专栏王磊的博客

Net连接mysql的公共Helper类MySqlHelper.cs带MySql.Data.dll下载

MySqlHelper.cs代码如下: using System; using System.Collections.Generic; using System...

4399
来自专栏c#开发者

about store RecordField submit emptystring issue

operate screenshot When click save button submit to change,trace store before...

3437
来自专栏互联网开发者交流社区

STC-单片机控制系统

1103

扫码关注云+社区