对于2个数字，如何测试其中一个是否是另一个的整数幂

Question

对于整数x、y和n(只给出x和y)，测试xⁿ=y？如果x＝8，y＝512，那么n＝3，所以这是真的。但是，如果x=8和y=500，则n必须在2.98左右(不是整数)，因此该语句的计算结果为false。使用对数是做这个测试的最佳方法吗？

检查一个整数是否是另一个整数的整数幂提供了一些解决方案：

int n = y; while(n < x) n *= y; return n == x，

while (x%y == 0)  x = x / y
return x == 1

对数法(这是我的版本)：

return ((log(y, x) % 1) == 0) // log(expression, base)

log(y，x)=log_xy

哪种方法评估得更快，尤其是对于大数字？

Answer 1

对数方法需要更加小心，因为对数函数由于使用浮点近似值而有少量的不准确性。例如3¹⁰=59049，但是：

log(59049, 3)
===> 9.999999999999998

是否可以对此进行补偿(通过检查答案是否"足够接近"最接近的整数)取决于x和y的范围。如果y小于2³²，那么我认为对数可以按比例最接近整数(而真实答案不是整数)是：

1 - log(4294967295, 65536) / 2
===> 1.049693665322593e-11

所以选择一个小于这个的ε，你可以放心地使用对数方法：

n = log(y, x);
e = round(n);
if (abs(1 - n / e) < epsilon) {
/* y == x to the power of e */
} else {
/* y not a power of x */
}

如果y的允许范围更大，则必须为epsilon找到合适的值。但要注意：对于足够大的y，双精度浮点中可能没有合适的epsilon。例如，如果y可以大到2⁴⁸−1，那么情况就是这样，因为

log(281474976710655, 16777216)
===> 2.0 exactly

因此，对于足够大的y，您不能依赖对数：您需要在之后显式执行求幂作为检查。

Answer 2

如果存在b和e的b^e=n，则数字n是完美幂。例如，216=6^3=2^3*3^3是一个完美的幂，但72=2^3*3^2不是。如果数字n是一个完美幂，则指数e必须小于log2n，因为如果e大于2^e将大于n-。此外，只需要测试素数*e*s，因为如果一个数字是复合指数的完美幂，它也将是复合分量的素数因子的完美幂；例如，2^15=32768=32^3=8^5是完美的立方根，也是完美的五次根。

我在博客上有一个实现。

Answer 3

对于相对较小的输入，我相信您的第三种方法会工作得最好。(不过，您需要更加小心地检查完整性。)

一些思考的食物：

1. 你可以很快地计算出x的幂，大致为sqrt(y)(即O(M(logy))时间)，然后用这个幂(在O(M。

2. 您可以使用相当差的对数近似来获得n上相当紧的边界。如果我知道一个在log_x(y)常数内的整数，那么我只需要检查x的常数幂。这些检查是使用爱德华·福尔克的答案中举例说明的"平方和乘法技术"最快完成的。

3. 即使在n上有一个相当宽的边界，也可以使用算术模适度大小的随机素数来显著缩小候选n的集合。利用算术模取几个中等大小的随机素数，结合中国余数定理，可以非常有效地将可能的n缩小到零或一。

使用第二个想法运行：请注意，我只需要y的顶部比特就可以获得log y的近似值，该近似值最多为一个常数；其他的都是肉汁。您应该能够使用FPU取前53位的对数，使用数字的长度进行调整，然后检查O(M(log y))时间中最接近的整数。第三个想法允许您使用随机化来检查x^n == y是否处于O(log y)时间，这是最优的。

Answer 4

对于较大的数字，日志可能会更快，但您应该对其进行基准测试。这将涉及到double和back的转换，这可能是一个问题。

我认为这可能是一个更好的解决方案：

long y = 512;
long x = 8;
if (x <= 1) return false;
while (y>1) {
// Find maximum x^(2^n) <= y
long xp = x;   // x to some maximum power
long xp2;      // experimental value of xp
while ((xp2 = xp*xp) <= y)
xp = xp2;
if (y%xp != 0) return false;  // reject
y /= xp;
}
return y == 1;

这仍然有改进的方法，我只测试了几个案例，但它似乎有效。

Answer 5

这个方法应该可以解决问题：

void toCheckPower(){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println("No of which power is checked="+n);
int pow=sc.nextInt();
int num=pow;
System.out.println("No to check power="+pow);
int sum=1;
while(sum<=pow){
sum=sum*n;
if(sum==pow){
System.out.println(pow+" is a Power of "+n);
break;
}
else if(sum>pow){
System.out.println(pow+" is not a Power of "+n);
break;
}
}
}

Answer 6

如果没有基准测试，只关注正在发生的事情，这一次应该是最快的。

int n = y; while(n < x) n *= y; return n == x;

(注意，然而，你已经从你的描述中颠倒了x&y的含义，n完全不同)

while (x%y == 0)  x = x / y;

这是做除法和模运算(本质上是第二次除法)，所以它做的工作量是原来的两倍，但它可以提前退出循环，所以它可能会赢。

return ((log(y, x) % 1) == 0)

这使用的浮点本质上是邪恶的(尽管浮点在现代CPU芯片中变得越来越好和更快)。然而，当你需要知道它是完整的还是不完整的时候，你做它的模测试它是偶数还是奇数。