如何在不进行模运算的情况下将 Java BigInteger 提高到 BigInteger 的幂？

Question

我正在做一些大整数计算，我需要将一个 BigInteger 提高到另一个 BigInteger 的幂。 .pow() 方法执行我想要的操作，但采用 int 值作为参数。 .modPow 方法采用 BigInteger 作为参数，但我不希望答案与我尝试计算的值一致。

我的 BigInteger 指数太大而无法表示为 int，有人可以建议一种方法来解决此限制吗？

Answer 1

您不应该尝试用另一个极大数来计算一个极大数的幂。得到的数字将使用大量的内存。如果计算a.pow(b)，它将大约有log(a)*b 位。如果 b 太大而无法放入整数，那么即使 a 的值非常小，结果也将有数十亿位。

尝试重新思考您想要实现的目标以及如何在不执行此操作的情况下实现它。

Answer 2

实际的解决方案是将指数从 BigInteger 转换为 int。

如果因为指数太大而无法做到这一点，那么您的算法就无法实现。所得数字几乎肯定会太大而无法表示为 BigInteger。 （BigInteger 使用字节数组来表示数字，Java 数组的最大大小是 2**31 - 1 元素，无论堆有多大。）即使您实现了一个代表数字的“BiggerInteger”类，您很快就会突破机器物理内存大小的限制。 （计算 N.pow(M) 所需的时间将是... NP-tricky ... O((MlogN)^M) 我认为） 。

当然，如果您要取幂的数字是 0、1 或 -1，那么结果将很容易适合 <代码>BigInteger。但在这些情况下，有更好的方法来计算功率:-)。

Answer 3

您找不到“Java BigInteger to-the-power BigInteger”的值，因为根据JavaDoc“BigInteger必须支持-2^Integer.MAX_VALUE（不包括）到+2^Integer.MAX_VALUE（不包括）范围内的值并且可能支持该范围之外的值。”

因此，Java BigInteger 不支持任何高于 2^Integer.MAX_VALUE 的值。这就是为什么 pow 方法不接受任何高于 int 的参数。

希望这个答案有帮助。

Answer 4

假设我们已经接受了这样一个事实，即由于之前所有答案中概述的原因，我们不应该这样做，这是一个仅可用于测试目的的可行解决方案：

指数大于或等于 0

BigInteger pow(BigInteger base, BigInteger exponent) {
    BigInteger result = BigInteger.ONE;
    for (BigInteger i = BigInteger.ZERO; i.compareTo(exponent) != 0; i = i.add(BigInteger.ONE)) {
        result = result.multiply(base);
    }
    return result;
}

这适用于正碱和负碱。您可能希望根据您的需要处理 0 的 0 次方，因为这在技术上是未定义的。

指数可以是正数也可以是负数

BigDecimal allIntegersPow(BigInteger base, BigInteger exponent) {
    if (BigInteger.ZERO.compareTo(exponent) > 0) {
        return BigDecimal.ONE.divide(new BigDecimal(pow(base, exponent.negate())), 2, RoundingMode.HALF_UP);
    }
    return new BigDecimal(pow(base, exponent));
}

这使用第一种方法返回具有 2 位小数的 BigDecimal，您可以根据需要定义比例和舍入模式。

同样，您不应该在现实生活中的生产级系统中执行此操作。