java - BigInteger 上的操作有多复杂？

Question

这些方法的复杂性是什么，目前multiply是什么？文档中（也没有其他任何地方）没有提到计算复杂性。dividepowBigInteger

Answer 1

如果您查看BigInteger（与 JDK 一起提供）的代码，在我看来它 multiply(..)具有O(n^2)（实际上方法是multiplyToLen(..)）。其他方法的代码稍微复杂一些，但你可以自己看。

注意：这是针对 Java 6 的。我认为它在 Java 7 中不会有所不同。

Answer 2

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

给你http://futureboy.us/temp/BigInteger.java

Answer 3

As noted in the comments on @Bozho's answer, Java 8 and onwards use more efficient algorithms to implement multiplication and division than the naive O(N^2) algorithms in Java 7 and earlier.

Java 8 multiplication adaptively uses either the naive O(N^2) long multiplication algorithm, the Karatsuba algorithm or the 3 way Toom-Cook algorithm depending in the sizes of the numbers being multiplied. The latter are (respectively) O(N^1.58) and O(N^1.46).

Java 8 division adaptively uses either Knuth's O(N^2) long division algorithm or the Burnikel-Ziegler algorithm. (According to the research paper, the latter is 2K(N) + O(NlogN) for a division of a 2N digit number by an N digit number, where K(N) is the Karatsuba multiplication time for two N-digit numbers.)

Likewise some other operations have been optimized.

---

There is no mention of the computational complexity in the documentation (nor anywhere else).

Some details of the complexity are mentioned in the Java 8 source code. The reason that the javadocs do not mention complexity is that it is implementation specific, both in theory and in practice. (As illustrated by the fact that the complexity of some operations is significantly different between Java 7 and 8.)

Answer 4

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

如果运算是线性 O(n)，二次 O(n^2)，多项式或指数应该是显而易见的。

编辑：虽然您可以为算法提供理论界限，但它们在实践中可能没有那么有用。首先，复杂性并没有给出因素。一些线性或次二次算法根本没有用，因为它们占用了太多时间和资源，不足以解决手头的问题（例如 Coppersmith-Winograd 矩阵乘法）。那么你的计算可能包含你只能通过实验检测到的所有问题。有一些准备算法对解决问题没有任何作用，但可以加速真正的求解器（矩阵调节）。有次优的实现。长度越长，您的速度可能会急剧下降（缓存丢失、内存移动等）。因此，出于实际目的，我建议进行实验。

最好的办法是每次将输入的长度加倍并比较时间。是的，您确实会发现算法是否具有 n^1.5 或 n^1.8 复杂度。只需将输入长度增加四倍，您只需要 1.5 而不是 2 的一半时间。如果将长度乘以 256 倍，您将再次获得 1.8 的近一半时间。