Karatsuba算法是什么

Karatsuba算法是一种快速乘法算法。它将两个n位数字的乘法减少到nlog2⁡3≈n1.585的最大值。一般的单位数乘法(当n为n时，n恰好是nlog23)是2的幂。所以比传统算法要快，传统算法需要n2个单位数的乘积。

Karatsuba算法是一种快速乘法算法。它是由Anatoly Karatsuba在1960年发现的，并于1962年出版。它将两个n位数字的乘法减少到nlog2⁡3≈n1.585的最大值。一般的单位数乘法(当n为n时，n恰好是nlog23)是2的幂。所以比传统算法要快，传统算法需要n2个单位数的乘积。

历史

两个N位数字相乘的标准过程需要许多与n2成比例的基本运算，在大0符号中是O(n2)。安德雷·柯尔莫哥洛夫推测经典算法是渐近最优的，这意味着这个任务的任何算法都需要ω (N2)基本运算。

1960年，科尔莫戈罗夫在莫斯科国立大学组织了一次控制论数学问题研讨会，他在会上陈述了ω (N2)猜想和其他计算复杂性问题。一周之内，当时23岁的学生Karatsuba发现了一个算法(后来称为“除与规则”)，用o (nlog 23)的基本步乘以两个n位数来反驳这个猜想。Kolmogorov对这个发现非常不满；他在研讨会的下一次会议上进行了沟通，然后结束了会议。Kolmogorov于1962年在斯德哥尔摩举行的世界各地的会议上就Karatsuba的结果发表了一些演讲(例如，见《1962年国际数学家大会论文集》，第351-356页，以及《国际数学家大会上发表的六篇演讲》)，并于1962年在《苏联科学院学报》上发表了这一方法。这篇文章，Kolmogorov写的，包含了关于乘法的两个结果，Karatsuba算法和Yuri Ofman如作者所言，它列举了“a .卡拉津巴和余。Onman”。Karatsuba在收到出版商的再版时发现了这篇论文。

算法

基本步骤

Karatsuba算法的基本步骤是允许人们用三个较小的数字相乘，计算出两个大数字x和y的乘积的公式，每个乘数约为x或y的一半，加上一些加法和数字移位。这个基本步骤其实是高斯复数乘法算法的一个扩展，其中虚数单位I用基数的幂代替。

设x和y表示为基数b中的n位字符串，对于任何小于n的正整数，两个给定的数可以写成:

其间

这里

这些公式需要四次乘法，查尔斯·巴贝奇知道。Karatsuba观察到xy只能用三次乘法计算，但需要增加数倍。如前所述，

从那时起

然而，在计算时

例子

要计算12345和6789的乘积，选择B = 10，m = 3。然后我们使用获得的基(Bm = 1000)分解输入操作数，如下所示:

12345 = 12 1000 + 345

6789 = 6 1000 + 789

只有三个整数的乘法运算较小，用于计算三个部分结果:

z2 = 12×6 = 72

z0 = 345×789 = 272205

Z1 =(12+345)×(6+789)z2 z0 = 357×795 72 272205 = 283815 72 272205 = 11538

我们通过将这三个部分结果相加并相应地移动它们来获得结果(然后通过在输入操作数中以基数1000分解这三个输入来考虑进位):

结果= z2 B + z1 B + z0，

result = 72 1000 * 1000+11538 1000+272205 = 83810205。

请注意，中间的第三种方法对输入域进行运算，该域小于前两次乘法的两倍，其输出域小于四倍，这两次减法的计算必须基于前两次乘法计算的1000进位。

Z1 = 283815 72 272205 = 11538。