Java ArithmeticException BigInteger将溢出支持范围

Question

我正在研究一种算法来检查数字是否是素数，并且需要处理非常大的数字，因此我使用的是BigInteger类。问题是引发此异常时，ArithmeticException BigInteger会溢出支持范围。

Exception in thread "main" java.lang.ArithmeticException: BigInteger would overflow supported range
    at java.math.BigInteger.reportOverflow(Unknown Source)
    at java.math.BigInteger.checkRange(Unknown Source)
    at java.math.BigInteger.<init>(Unknown Source)
    at java.math.BigInteger.shiftLeft(Unknown Source)
    at java.math.BigInteger.pow(Unknown Source)
    at Kitas.main(Kitas.java:118)

以及抛出异常的行：

b = BigInteger.valueOf(2).pow((int) (35*(Math.pow(2, counter))));

一旦计数器达到26的值，就会引发异常。

Answer 1

(int) (35 * Math.pow(2, 26)) == (int) (2348810240d) = Integer.MAX_VALUE

结果是，您试图将2的功率提高到Integer.MAX_VALUE，所以结果将超过Integer.MAX_VALUE二进制数。BigInteger不够大，存储这么大的数字也是不切实际的。

Java内置的任何东西都不能让您测试这么大的数字的原始性。

Answer 2

BigInteger使用int[]来存储数组的值。这意味着数字不能大于2^(Integer.Max_Value)，因为如果大于这一点，数组的索引(存储在一个int中)将大于数组的最大大小。

在26岁时，您要存储的号码是：

2^(35*[2^26]) = 2^2348810240 

这里使用的两个(2,348,810,240)的功率略大于(2^31-1)，这是由于实现BigInteger的内部存储而可以存储在BigInteger中的最大值。超过26的柜台只会使这个问题更严重。

如果您真的需要处理这么大的数字，您可能需要编写自己版本的BigInteger，它使用其他东西来存储其值，从而允许更多的存储空间。可能是像这样的二维数组：int[][] storage，因为它可以容纳2^(2^(2^32-1)-1)的值。如果您需要的更多，您可以继续增加数组的尺寸，直到您耗尽您的计算机内存-如果完全填充一个int还不能做到这一点(我想它会)。

有关更多信息，请参见文档。