操作BigInteger的复杂度是什么？

Question

BigInteger类中的multiply、divide和pow方法目前的复杂度是什么？文档中（以及其他任何地方）都没有提到计算复杂度。

- PythonPower

---

你可以查看源代码。 - uckelman

实际上我已经尝试过了。但是似乎需要很多知识才能进行分析。我希望在StackOverflow阅读这篇文章的人刚好有那些知识。也许这太乐观了？ - PythonPower

你提到Java 7是有特定的原因吗？BigInteger自Java 1.1版本就存在了。 - Joachim Sauer

我提到Java 7是因为我想考虑目前正在进行的变化。 - PythonPower

请将以下与编程有关的内容从英语翻译成中文。仅返回翻译后的文本：（我已将此问题编辑为适用于所有Java版本...因为现在几乎没有人关心Java-7及以前的版本。） - Stephen C

Answer 1

如果你查看 JDK 中提供的 BigInteger 代码，我认为 multiply(..) 方法具有O(n^2) 的时间复杂度（实际上这个方法是 multiplyToLen(..)）。其他方法的代码有些复杂，但你可以自己看一下。

注意：这是针对 Java 6 的，我假设在 Java 7 中不会有所不同。

- Bozho

---

乘法有几个复杂性问题：http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations... 你能区分O（n ^ 2）和O（n ^ 1.585）或O（n ^ 1.465）吗？ - Joey

我相信Java 7有所改变，但是我无法记起搜索到的细节，因为它们很少。 - PythonPower

Rössel：存在其他乘法算法，但Java 6不使用它们。当乘以大数时，您肯定会注意到传统算法和Karatsuba乘法之间的区别。除非您正在用数字填充主存储器，否则其他算法的跳跃较小。 - Charles

OpenJDK 8采用自适应策略，工作效果更佳。对于大量的n值，其复杂度低于O(n^2)。另请参见https://dev59.com/ZW7Xa4cB1Zd3GeqPuNN9#20037505 - Max Barraclough

Answer 2

如@Bozho的回答中所述，Java 8及更高版本使用比Java 7及早期版本中朴素的O(N^2)算法更有效率的算法来实现乘法和除法。

Java 8的乘法根据相乘的数字大小自适应地使用朴素的O(N^2)长乘法算法、Karatsuba算法或三路Toom-Cook算法。后两者的时间复杂度分别为O(N^1.58)和O(N^1.46)。

Java 8的除法根据被除数和除数的长度自适应地使用Knuth的O(N^2)长除法算法或Burnikel-Ziegler算法。后者是指一个2N位数除以一个N位数的除法，时间复杂度为2K(N) + O(NlogN)，其中K(N)是两个N位数的Karatsuba乘法时间。

同样，其他一些操作也已经进行了优化。

文档中没有提及计算复杂性（也没有在其他地方提到）。

Java 8的源代码中提到了一些复杂性的细节。 javadocs不提及复杂度的原因是它在理论上和实际上都是具体实现的。 （正如某些操作的复杂度在Java 7和8之间有明显不同的表现。）

- Stephen C

Answer 3

有一个新的“更好”的BigInteger类，由于保守主义和缺乏有用的回归测试（大数据集），它没有被sun jdk使用。做出更好算法的那个人可能在评论中讨论了旧的BigInteger。

这是链接：http://futureboy.us/temp/BigInteger.java

- i30817

Answer 4

进行测量。使用逐渐增加的操作数进行操作，并在图表上绘制时间。 不要忘记热身JVM（多次运行）以获得有效的基准结果。

如果操作是线性O（n），二次方O（n ^ 2），多项式或指数，应该很明显。

编辑：虽然您可以给出算法的理论界限，但实际上可能并不那么有用。首先，复杂度并不给出因素。一些线性或亚二次算法只是因为它们消耗了太多的时间和资源而不适合手头的问题（例如Coppersmith-Winograd矩阵乘法）。 然后，您的计算可能具有所有仅通过实验才能检测到的技巧。有准备算法，它们没有解决问题，只是加速了真正的求解器（矩阵条件）。有次优的实现。随着长度的增加，您的速度可能会急剧下降（缓存丢失，内存移动等）。因此，为了实际目的，我建议进行实验。

最好的方法是每次将输入的长度加倍，然后比较时间。而且，你可以找出一个算法是否具有n^1.5或n^1.8的复杂度。只需将输入长度乘以四倍，如果是1.5，则只需要一半的时间，而不是两倍。如果你将长度增加256倍，那么对于1.8，你再次获得了近乎一半的时间。

- Thorsten S.

---

可能会起作用。我需要测试大量的n值。如果我测量了两个n位BigIntegers（t_0）和两个2n位BigIntegers（t_1）相乘所需的时间，那么我可能会预期复杂度为O（n ^（log2（t_1 / t_0）））。总的来说，我对经验方法有点怀疑（可能不公平）。 - PythonPower

这是一个困难的方法，虽然。从 先验 的角度来看，没有理由认为单一算法被使用，而不是算法组合。因此，从10位数字扩展到1000位数字的比例可能与从1000位数字扩展到3000位数字的比例不同。 - Charles