Java 的 BigInteger class

Question

Java的BigInteger class使用什么算法进行乘法和除法，它们各自的时间复杂度是多少？

Java 的 BigInteger class 使用什么基本类型 - byte、short、int 等 - 为什么？

Java 的 BigInteger class 如何处理其原始类型已签名这一事实？如果答案是它就可以了而且它真的很乱，那我 need/want 就知道这些了。我真正想知道的是它是否像某些 python 库那样作弊，因为它们不是用 python 编写的？

Answer 1

原因：对于大多数平台来说，它是最快的。

Answer 2

我查看了 BigInteger here 的源代码。这是我的发现。

BigInteger 没有 "cheat"。在 Java 中，"cheating" 是通过使用所谓的 "native" 函数来实现的。请参阅 java.lang.Math 以获得相当广泛的列表。

BigInteger 使用 int 来表示其数据。

private transient int[] words;

是的，它很乱。有很多类似的东西。

Answer 3

Oracle 的 java.math.BigInteger class 经历了从 Java 7 到 Java 8 的一些广泛改进。您可以通过检查 grepcode.com 上的源代码来亲自了解。不作弊，都是纯正的java.

在内部，它使用一个 sign-magnitude representation 的整数，使用一个 int 值的数组来存储大小。回想一下 java int 是一个 32 位值。使用所有 32 位而不考虑符号。这个大小也很方便，因为两个 int 的乘积适合 java long.

从 Java 8 开始，BigInteger class 添加了一些高级算法，例如 Karatsuba 和 Toom-Cook 乘法，以提高数千位整数的性能。

Java's BigInteger class