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

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

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

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

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

相关文章

来自专栏DHUtoBUAA

快速排序算法思路分析和C++源代码(递归和非递归)

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

3737
来自专栏老马说编程

计算机程序的思维逻辑 (5) - 小数计算为什么会出错?

违反直觉的事实 计算机之所以叫"计算"机就是因为发明它主要是用来计算的,"计算"当然是它的特长,在大家的印象中,计算一定是非常准确的。但实际上,即使在一些非常...

1968
来自专栏云时之间

NLP入门之形式语言与自动机学习(三)

在前边的文章中我们把简单的需要的基础知识简单的列举了一遍,包括简单的集合逻辑,还有图论以及一些的证明方法等等,接下来我们将要开始我们正式的关于形式语言的学习,所...

4106
来自专栏我的博客

算法复杂度

算法复杂度 分为时间复杂度和空间复杂度。即算法在编写成可执行程序后,运行时所需要的资源,资源包括时间资源和内存资源。 时间复杂度 在计算机科学中,算法的时间复杂...

3196
来自专栏技术之路

climits

<climits>头文件定义的符号常量 CHAR_MIN       char的最小值 SCHAR_MAX      signed char 最大值 SCHAR...

1778
来自专栏有趣的Python

玩转算法面试:(二)面试中的复杂度分析

面试中的时间复杂度分析 到底什么是大O n表示数据规模 O(f(n)) fn是关于n的一个函数。表示运行算法所需要执行的指令数,和f(n)成正比。 ? 常见...

7205
来自专栏程序员叨叨叨

5.1 基本数据类型第 5 章 CG 数据类型

本章将着重介绍Cg语言中预定义的内置(built in)的、或称为基本(primitive)的数据类型。然后介绍可以用来声明对象的各类类型,主要是数组和结构类型...

1053
来自专栏zhisheng

Java常用排序算法/程序员必须掌握的8大排序算法(下)

昨天发表的java常用排序算法/程序员必须掌握的8大算法(上),没看的可以点上面这个链接↑↑↑↑,(概念+实例+代码+排序舞蹈视频)更好的帮助你理解。 java...

4379
来自专栏ACM算法日常

10000的阶乘-HDU1042

Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

1021
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

741

扫码关注云+社区