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

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

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

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

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 条评论
登录 后参与评论

相关文章

来自专栏Soul Joy Hub

自动微分(Automatic Differentiation)简介

http://blog.csdn.net/aws3217150/article/details/70214422 现代深度学习系统中(比如MXNet, Tens...

3183
来自专栏WeaponZhi

使用Octave来学习Machine Learning(二)

前言 上一篇我们介绍了 Octave 的一些基本情况,大家对 Octave 应该已经有了一个基本的了解,我相信看这篇文章的朋友已经在自己的电脑中安装好 Ocat...

3196
来自专栏大数据挖掘DT机器学习

用python实现决策树ID3算法,对隐形眼镜类型预测

本节讲解如何预测患者需要佩戴的隐形眼镜类型。 1、使用决策树预测隐形眼镜类型的一般流程 (1)收集数据:提供的文本文件(数据来源于UCI数据库) (2)准备数据...

3657
来自专栏刘望舒

算法(一)时间复杂度

前言 算法很重要,但是一般情况下做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的...

1738
来自专栏互联网大杂烩

算法岗面试

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包...

642
来自专栏人工智能LeadAI

pytorch入门教程 | 第二章:Autograd

autograd自动微分 假如我们有一个向量x=(1,1)当成input,经过一系列运算得到了output变量y,如下图所示: ? 如图所示,向量x经过与4和自...

35112
来自专栏King_3的技术专栏

leetcode-887-三维形体投影面积

在 N * N 的网格中,我们放置了一些与 x,y,z 三轴对齐的 1 * 1 * 1 立方体。

702
来自专栏尾尾部落

[剑指offer] 连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候...

491
来自专栏编程

扣丁学堂浅谈Python视频教程之random模块详解

今天扣丁学堂小编给大家详细介绍一下关于Python视频教程之random模块详解,,首先用于生成伪随机数之所以称之为伪随机数,是因为真正意义上的随机数(或者随机...

20910
来自专栏章鱼的慢慢技术路

统计计算学生成绩类问题汇总

1314

扫描关注云+社区