这是一段Java代码。
import java.util.Scanner;
import java.math.*;
class power1 {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
long a=in.nextLong();
BigInteger b=in.nextBigInteger();
long res=power(a,b);
System.out.println(res);
}
public static long power(long x,BigInteger n) {
int b=(int)(Math.pow(10,9)+7);
long m;
if (n.compareTo(BigInteger.ZERO)==0)
return 1;
if(n.compareTo(BigInteger.ONE)==0)
return x;
if ((n.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO)==0))
{
m = power(x,n.divide(BigInteger.valueOf(2)));
return (m * m)%b;
}
else return (x * power(x,n.subtract(BigInteger.valueOf(1)))%b);
}
}
考虑到它是一个 BigInteger,这应该适用于 b 的任何值。 但是当我输入非常大的 b 值时,我会收到错误
Exception in thread "main" java.lang.StackOverflowError
at java.math.MutableBigInteger.divideKnuth(Unknown Source)
at java.math.MutableBigInteger.divideKnuth(Unknown Source)
at java.math.BigInteger.remainderKnuth(Unknown Source)
at java.math.BigInteger.remainder(Unknown Source)
at java.math.BigInteger.mod(Unknown Source)
有办法解决吗?
最佳答案
您应该实现以下算法:
recursivePower(base, exp):
if (exp == 0)
return 1;
if (exp == 1)
return base;
if (exp%2 == 0) {
temp = recursivePower(base, exp/2);
return temp*temp;
temp = recursivePower(base, (exp-1)/2);
return temp*temp*base;
这将大大减少您使用的通话次数。另一件事是扩大堆栈的大小。使用 java Test -Xss2048k
运行您的应用程序 - 尝试不同的大小。
最后但并非最不重要的一点是始终使用 BigInteger。
public static BigInteger recursivePower (BigInteger base, BigInteger exp) {
if (exp.compareTo(BigInteger.ZERO) == 0)
return BigInteger.ONE;
if (exp.compareTo(BigInteger.ONE) == 0)
return base;
if (exp.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0) {
BigInteger temp = recursivePower(base, exp.divide(BigInteger.valueOf(2)));
return temp.multiply(temp);
}
BigInteger temp = recursivePower(base, (exp.subtract(BigInteger.valueOf(1)).divide(BigInteger.valueOf(2))));
return temp.multiply(temp).multiply(base);
}
public static void main(String []args){
System.out.println(recursivePower(BigInteger.valueOf(2), BigInteger.valueOf(80)).toString());
}
关于java - 使用 BigInteger 和递归求 A 的 B 次方,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40521796/