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

Question

在麻省理工学院的MITOpencourseware讲座（6.006第12讲）中，我偶然提到了4种乘法算法（将两个n位数相乘）——

1. 具有O（n^2）复杂性的普通朴素方法
2. Karatsuba算法-O（n^1.584）
3. 图姆库克（Toom3）-O（n^1.465）
4. Schonhage Strassen-O（非直瞄（n）对数（对数（n）））

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

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

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

Answer 1

我是gmpy2的维护者

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

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

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

它可以在DecInt找到