设为首页 - 加入收藏 ASP站长网(Aspzz.Cn)- 科技、建站、经验、云计算、5G、大数据,站长网!
热搜: 创业者 数据 手机
当前位置: 首页 > 大数据 > 正文

KaraTsuba乘法——高效的大数乘法

发布时间:2021-01-16 10:27 所属栏目:125 来源:网络整理
导读:
导读:今天看Coursera课程时,看到一个牛逼的算法,叫KaraTsuba乘法。普通乘法复杂度一般都是O(n^2),而这个算法,仅有O( nlog3 )。下面,我就来介绍一下这个算法。 ? ? ? ? 首先来看看这个算法是怎么进行计算的,见下图: 图中显示了计算5678*1234的过程,首先是

今天看Coursera课程时,看到一个牛逼的算法,叫KaraTsuba乘法。普通乘法复杂度一般都是O(n^2),而这个算法,仅有O( nlog3)。下面,我就来介绍一下这个算法。

? ? ? ? 首先来看看这个算法是怎么进行计算的,见下图:

KaraTsuba乘法——高效的大数乘法

图中显示了计算5678*1234的过程,首先是拆分成abcd四个部分,然后分别计算ac,bd,(a + b)*(c+d),最后再用第三个算式的结果减去前面两个(其实得到的就是bc+ad,但是减少了乘法步骤),然后,计算式1后面加4个0,计算式2后面不加,计算式3后面加2个0,再把这三者相加,就是正确结果。好吧,看到这里,你一定觉得,这不是很复杂吗。但其实不然,在大数计算的时候,计算机中无法直接用*实现,只能自己写算法,这时候,每个人写的算法不同,差异就体现出来了。


接下来,就来证明一下这个算法的正确性。

我们假设要相乘的两个数是x * y。我们可以把x,y写成

KaraTsuba乘法——高效的大数乘法


这里的n是数字的位数。如果是偶数,则a和b都是n / 2位的。如果n是奇数,则你可以让a是n / 2 + 1位,b是n / 2位。(例如a = 12,b = 34;a = 123,b = 45)

那么x * y就变成了

KaraTsuba乘法——高效的大数乘法


进一步计算,

KaraTsuba乘法——高效的大数乘法


对比之前的计算过程。结果已经呼之欲出了这里唯一需要注意的两点就是

1. (a * d + b * c)的计算为了防止两次乘法,应该使用之前的计算

2. 这些乘法在算法里应该是递归实现的,数字很大时,先拆分,然后拆分出来的数字还是很大的话,就继续拆分,直到a * b已经是一个非常简单的小问题为之。这也是分治的思想。

(编辑:ASP站长网)

    网友评论
    推荐文章
      热点阅读