java - 对于 2 个数字，如何测试一个是否是另一个的整数幂？

Question

对于整数 x、y 和 n，(仅给出 x 和 y)测试是否 xⁿ = y？如果 x = 8，y = 512，则 n = 3，则为真。但如果 x = 8 且 y = 500，则 n 必须在 2.98 左右(不是整数)，因此该语句的计算结果为假。使用对数是进行此测试的最佳方法吗？

Check if one integer is an integer power of another提供了一些解决方案:

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 _x y

哪种方法计算速度更快，尤其是对于大数？

Answer 1

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

log(59049, 3)
   ===> 9.999999999999998

您是否可以对此进行补偿(通过检查答案是否“足够接近”最接近的整数)取决于您的 x 和 y 的范围.如果 y 小于 2³²，那么我认为最接近的对数可以成比例地得到一个整数(没有真正的答案是整数)是:

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

所以选择一个比这个小的epsilon，你就可以放心使用对数法了:

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， double float 中可能没有合适的 epsilon。例如，如果 y 可以大到 2⁴⁸ − 1 那么就是这种情况，因为

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

因此对于足够大的 y，您不能依赖对数:之后您需要明确地执行取幂作为检查。