• 欢迎访问速搜资源吧,如果在网站上找不到你需要的资源,可以在留言板上留言,管理员会尽量满足你!

【速搜问答】Karatsuba算法是什么

问答 admin 9个月前 (04-13) 147次浏览 已收录 0个评论

汉英对照:
Chinese-English Translation:

Karatsuba算法是一种快速乘法算法。它将两个n位数的乘法减少到最多nlog2⁡3≈n1.585一般的单位数乘法(当n时n恰好是nlog2⁡3) 是2的幂。 因此,它比传统算法更快,后者需要n2个单位数乘积。

Karatsuba algorithm is a fast multiplication algorithm. It reduces the multiplication of two n-digit numbers to a maximum of nlog2 ⁡ 3 ≈ n1.585. The general multiplication of unit numbers (when n is exactly nlog2 ⁡ 3) is a power of 2. Therefore, it is faster than the traditional algorithm, which requires the product of N2 units.

Karatsuba 算法是一种快速乘法算法。 它是由 Anatoly Karatsuba 于 1960 年发现并于 1962 年发表的。它将两个 n 位数的乘法减少到最多 nlog2⁡3≈n1.585 一般的单位数乘法(当 n 时 n 恰好是 nlog2⁡3) 是 2 的幂。 因此,它比传统算法更快,后者需要 n2 个单位数乘积。

Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It reduces the multiplication of two n-digit numbers to a maximum of nlog2 ⁡ 3 ≈ n1.585. The general multiplication of unit numbers (when n is exactly nlog2 ⁡ 3) is a power of 2. Therefore, it is faster than the traditional algorithm, which requires the product of N2 units.

历史

history

两个 n 位数相乘的标准程序需要许多与 n2 成比例的基本运算,或者采用 big-O 表示法的 O(n2)。 Andrey Kolmogorov 推测经典算法是渐近最优的,这意味着该任务的任何算法都需要Ω(n2)个基本运算。

The standard program for multiplication of two n-digit numbers requires many basic operations proportional to N2, or O (N2) using Big-O representation. Andrey Kolmogorov speculates that the classical algorithm is asymptotically optimal, which means that any algorithm for this task needs Ω (N2) basic operations.

1960 年,Kolmogorov 在莫斯科国立大学组织了一次关于控制论数学问题的研讨会,在那里他陈述了Ω(n2)猜想和计算复杂性的其他问题。在一周之内,当时一名 23 岁的学生 Karatsuba 发现了一种算法(后来被称为“分而治之”),它在 O(nlog2⁡3)基本步骤中乘以两个 n 位数,从而反驳猜想。科尔莫戈罗夫对这一发现非常不满;他在研讨会的下次会议上进行了沟通,然后终止了会议。 Kolmogorov 在世界各地的会议上做了一些关于 Karatsuba 结果的讲座(例如,参见“1962 年数学家国际会议论文集”,第 351-356 页,以及“国际数学家大会上发表的 6 篇讲座”)在斯德哥尔摩,1962 年“)并于 1962 年在苏联科学院院刊上发表了该方法。这篇文章由 Kolmogorov 撰写,包含两个关于乘法的结果,Karatsuba 算法和 Yuri Ofman 的单独结果;作为作者,它列出了“A. Karatsuba 和 Yu.Onman”。 Karatsuba 在收到出版商的重印时才发现了这篇论文。

In 1960, Kolmogorov organized a seminar on cybernetic mathematics at Moscow State University, where he presented the Ω (N2) conjecture and other problems of computational complexity. Within a week, Karatsuba, a 23-year-old student at the time, discovered an algorithm (later known as “divide and rule”), which multiplied two n-digits in the basic steps of O (nlog2 ⁡ 3) to refute the conjecture. Kolmogorov was very dissatisfied with the discovery; he communicated at the next meeting of the seminar and then terminated the meeting. Kolmogorov gave lectures on Karatsuba’s results at conferences around the world (for example, see “Proceedings of the 1962 International Conference of mathematicians”, pp. 351-356, and “six lectures at the International Congress of mathematicians”) in Stockholm, 1962, and published the method in the Journal of the Soviet Academy of Sciences in 1962. This paper, written by Kolmogorov, contains two results on multiplication, Karatsuba algorithm and Yuri ofman’s separate results; as the author, it lists “a. Karatsuba and Yu.Onman ”。 Karatsuba discovered the paper when she received a reprint from the publisher.

算法

algorithm

基本步骤

Basic steps

Karatsuba 算法的基本步骤是允许人们使用三个较小数字的乘法来计算两个大数 x 和 y 的乘积的公式,每个乘数大约是 x 或 y 的一半,加上一些加法和数字移位。 事实上,这个基本步骤是高斯复数乘法算法的推广,其中虚数单元 i 被基数的幂代替。

The basic step of Karatsuba algorithm is to allow people to use the multiplication of three smaller numbers to calculate the product of two large numbers x and Y. each multiplier is about half of X or Y, plus some addition and number shift. In fact, this basic step is a generalization of Gauss complex multiplication algorithm, in which the imaginary unit I is replaced by the power of the radix.

设 x 和 y 在某个基数 B 中表示为 n 位字符串。对于任何小于 n 的正整数,可以将两个给定的数字写为:

Let X and y be represented as n-bit strings in a cardinality B. For any positive integer less than N, two given numbers can be written as:

其中

among

这里

here

这些公式需要四次乘法,并且 Charles Babbage 知道。Karatsuba 观察到 xy 只能在三次乘法中计算,但需要额外增加几次。 如前所述,

These formulas require four multiplications, and Charles Babbage knows that. Karatsuba observed that XY can only be calculated in three multiplications, but it needs to be added several times. As mentioned earlier,

从那以后

after that

然而,当计算

However, when calculating

例子

example

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

To compute the product of 12345 and 6789, select b = 10 and M = 3. Then we use the resulting basis (BM = 1000) to decompose the input operands as follows:

12345 = 12 · 1000 + 345

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

6789 = 6 · 1000 + 789

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

There are only three integers with smaller multiplication operation, which are used to calculate three partial results:

z2 = 12×6 = 72

z2 = 12×6 = 72

z0 = 345×789 = 272205

z0 = 345×789 = 272205

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

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

我们通过添加这三个部分结果得到结果,相应地移位(然后通过在输入操作数中分解基数 1000 中的这三个输入来考虑进位):

We get the result by adding these three partial results and shift them accordingly (then consider the carry by decomposing the three inputs in Radix 1000 in the input operands)

result = z2 · B + z1 · B + z0,

result = z2 · B + z1 · B + z0,

result = 72 ·1000*1000 + 11538 · 1000 + 272205 = 83810205.

result = 72 ·1000*1000 + 11538 · 1000 + 272205 = 83810205.

注意,中间第三乘法对输入域进行操作,该输入域小于两次第一次乘法的两倍,其输出域小于四倍,并且必须从前两次乘法计算得到的 base-1000 进位 计算这两个减法时的帐户。

Note that the third multiplication in the middle operates on the input field, which is less than twice of the first multiplication twice, and its output field is less than four times, and the base-1000 carry calculated from the first two multiplications must be used to calculate the account of the two subtractions.

z1 = 283815 − 72 − 272205 = 11538.

z1 = 283815 − 72 − 272205 = 11538.


速搜资源网 , 版权所有丨如未注明 , 均为原创丨转载请注明原文链接:【速搜问答】Karatsuba算法是什么
喜欢 (0)
[361009623@qq.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址