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

发布于 2024-09-01 07:11:18 字数 195 浏览 11 评论 0原文

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

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

I'm doing some large integer computing, and I need to raise a BigInteger to the power of another BigInteger. The .pow() method does what I want, but takes an int value as an argument. The .modPow method takes a BigInteger as an argument, but I do not want an answer congruent to the value I'm trying to compute.

My BigInteger exponent is too large to be represented as an int, can someone suggest a way to work around this limitation?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

复古式 2024-09-08 07:11:18

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

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

You shouldn't try to calculate the power of an extremely large number with another extremely large number. The resulting number would use huge amounts of memory. If you calculate a.pow(b) it will have approximately log(a)*b digits. If b is too large to fit in an integer then for even quite small values of a the result will have several billion digits.

Try to rethink what you are trying to achieve and how to achieve it without doing this operation.

无悔心 2024-09-08 07:11:18

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

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

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

The practical solution is to convert the exponent from a BigInteger to an int.

If you cannot do this because the exponent is too large, your algorithm is unimplementable. The resulting number would almost certainly be too large to represent as a BigInteger. (A BigInteger uses an array of bytes to represent the number, and the maximum size of a Java array is 2**31 - 1 elements no matter how large the heap is.) And even if you implemented a "BiggerInteger" class that would represent the number, you would soon be pushing the limits of the physical memory size of your machine. (And the time taken to do calculate N.pow(M) would be ... NP-tricky ... O((MlogN)^M) I think).

Of course, if the number you are taking the power of is 0, 1 or -1, then the result will easily fit in a BigInteger. But in those cases, there are better ways to calculate the power :-).

一腔孤↑勇 2024-09-08 07:11:18

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

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

希望这个答案有帮助。

You can't find the the value of "Java BigInteger to-the-power BigInteger" because according to JavaDoc "BigInteger must support values in the range -2^Integer.MAX_VALUE (exclusive) to +2^Integer.MAX_VALUE (exclusive) and may support values outside of that range."

So, Java BigInteger does not support anything above 2^Integer.MAX_VALUE. Tha's why pow method does not take any argument above int.

Hope this answer helps.

め七分饶幸 2024-09-08 07:11:18

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

指数大于或等于 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,您可以根据需要定义比例和舍入模式。

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

Assuming we've already accepted the fact that we shouldn't do this for the reasons outlined in all of the previous answers, here's a working solution that can be used for testing purposes only:

Exponent greater than or equal to 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;
}

This will work for both positive and negative bases. You might want to handle 0 to the power of 0 according to your needs, since that's technically undefined.

Exponent can be both positive or negative

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));
}

This uses the first method to return a BigDecimal with 2 decimal places, you can define the scale and rounding mode as per your needs.

Again, you should not do this in a real-life, production-level system.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文