时间戳

首页 > 解决方案 > 如何在一系列数字上比较各种乘法算法

python - 如何在一系列数字上比较各种乘法算法

问题描述

在 MITOpencourseware（6.006 第 12 课）中进行 MIT 讲座时，我遇到了 4 种乘法算法（将两个 n 位数字相乘）-

  1. O(n^2) 复杂度的普通朴素方法
  2. Karatsuba 算法 - O(n^1.584)
  3. Toom-Cook(Toom3) - O(n^1.465)
  4. Schonhage-Strassen - O(nlog(n)log(log(n)))

现在要研究的是，在哪个阈值点（即 n 的值），一种方法作为更好的算法超越了另一种方法。有人提到以上所有内容都在 gmpy 包中。

为了尝试这一点，我参考了以下链接中的 gmpy2 包文档 - https://gmpy2.readthedocs.io/en/latest/intro.html

然而，在浏览本文档的部分内容时，gmpy2 似乎更多的是处理大量数字。特别是，我没有找到实现上述 4 种算法的单独函数。那么 gmpy2 的任何部分是否实现了这些算法，所以我可以根据 n（位数）绘制这些算法的运行时间？

标签： pythonmultiplicationkaratsubagmpystrassen

解决方案

我是gmpy2的维护者。

gmpy2不直接实现任何乘法算法。它只是调用在GMP中实现的算法

许多年前，我编写了一个纯 Python 实现的多精度算术。它使用 naive、Karatsuba、Toom-3、Toom-4 和 Nussbaumer 卷积进行乘法运算。（有趣的是，如果您选择足够大的精度，递归调用 Toom-4、Toom-3、Karatsuba 的纯 Python 解决方案可能比 Python 中使用并用 C 编写的 Karatsuba 唯一版本更快。） 几种不同的除法算法也得到实施。

很容易修改代码并添加全局变量来计算每个步骤的执行次数。

可以在DecInt找到

推荐阅读