对于整数 x、y 和 n,(仅给出 x 和 y)测试是否 xn = 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
哪种方法计算速度更快,尤其是对于大数?
最佳答案
对数方法需要更加小心,因为对数函数由于使用 float 近似而有少量不准确。例如 310 = 59049,但是:
log(59049, 3)
===> 9.999999999999998
您是否可以对此进行补偿(通过检查答案是否“足够接近”最接近的整数)取决于您的 x 和 y 的范围.如果 y 小于 232,那么我认为最接近的对数可以成比例地得到一个整数(没有真正的答案是整数)是:
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 可以大到 248 − 1 那么就是这种情况,因为
log(281474976710655, 16777216)
===> 2.0 exactly
因此对于足够大的 y,您不能依赖对数:之后您需要明确地执行取幂作为检查。
关于java - 对于 2 个数字,如何测试一个是否是另一个的整数幂?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13846267/