如何在不进行模运算的情况下将 Java BigInteger 提高到 BigInteger 的幂?
我正在做一些大整数计算,我需要将一个 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 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
您不应该尝试用另一个极大数来计算一个极大数的幂。得到的数字将使用大量的内存。如果计算
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 approximatelylog(a)*b
digits. Ifb
is too large to fit in an integer then for even quite small values ofa
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.
实际的解决方案是将指数从 BigInteger 转换为 int。
如果因为指数太大而无法做到这一点,那么您的算法就无法实现。所得数字几乎肯定会太大而无法表示为 BigInteger。 (BigInteger 使用字节数组来表示数字,Java 数组的最大大小是
2**31 - 1
元素,无论堆有多大。)即使您实现了一个代表数字的“BiggerInteger”类,您很快就会突破机器物理内存大小的限制。 (计算N.pow(M)
所需的时间将是... NP-tricky ...O((MlogN)^M)
我认为) 。当然,如果您要取幂的数字是
0
、1
或-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 calculateN.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 aBigInteger
. But in those cases, there are better ways to calculate the power :-).您找不到“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.
假设我们已经接受了这样一个事实,即由于之前所有答案中概述的原因,我们不应该这样做,这是一个仅可用于测试目的的可行解决方案:
指数大于或等于 0
这适用于正碱和负碱。您可能希望根据您的需要处理 0 的 0 次方,因为这在技术上是未定义的。
指数可以是正数也可以是负数
这使用第一种方法返回具有 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
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
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.