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

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

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

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

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

相关文章

来自专栏linjinhe的专栏

C++右值引用和移动语义学习小结

在 C++11 之前,将一个对象移动(move)到另一个对象的通用做法只有 copy constructor 或者 copy assignment ,然后销毁原...

733
来自专栏CDA数据分析师

如何用纯SQL查询语句可以实现神经网络?

在这篇文章中,我们将纯粹用SQL实现含有一个隐藏层(以及带 ReLU 和 softmax 激活函数)的神经网络。这些神经网络训练的步骤包含前向传播和反向传播,...

1133
来自专栏悦思悦读

决策树告诉你Hello Kitty到底是人是猫

Hello Kitty,一只以无嘴造型40年来风靡全球的萌萌猫,在其40岁生日时,居然被其形象拥有者宣称:HelloKitty不是猫! 2014年八月,研究 H...

3107
来自专栏racaljk

Leetcode 566. Reshape the Matrix 矩阵变形(数组,模拟,矩阵操作)

在MATLAB中,reshape是一个非常有用的函数,它可以将矩阵变为另一种形状且保持数据不变。 已知一个由二维数组表示的矩阵,和两个正整数r(行),c(列)...

642
来自专栏AIUAI

Caffe2 - (二十三) Detectron 之 utils 函数(1)

48712
来自专栏深度学习与计算机视觉

理解深层神经网络中的迁移学习及TensorFlow实现

什么是迁移学习 在深度学习中,所谓的迁移学习是将一个问题A上训练好的模型通过简单的调整使其适应一个新的问题B。在实际使用中,往往是完成问题A的训练出的模型有更完...

35010
来自专栏tkokof 的技术,小趣及杂念

算一算N阶乘的尾随零个数

既然要求解阶乘值的尾随零个数,直观的方法就是首先算出阶乘值,然后对10取模来计算尾随零个数,代码如下:

621
来自专栏华章科技

程序员必须知道的十大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较,但这种状况并不常见。...

732
来自专栏人工智能

Tensorflow下Char-RNN项目代码详解

前言 Char-RNN,字符级循环神经网络,出自于Andrej Karpathy写的The Unreasonable Effectiveness of Recu...

48610
来自专栏Bingo的深度学习杂货店

最小方差划分

给一个数组,求一个k值,使得前k个数的方差 + 后面n-k个数的方差最小 解题思路: 如果不考虑方差的概念,这题可以简化为 “给一个数组,求一个k值,使得前k个...

2913

扫码关注云+社区