For integers x, y, and n, (only x and y are given) test if xn = y? If x = 8, y = 512, then n = 3 so that is true. But if x = 8 and y = 500, n would have to be around 2.98 (not an integer) so the statement evaluates as false. Is using a logarithm the best method to do this test?
Check if one integer is an integer power of another offers some solutions:
int n = y; while(n < x) n *= y; return n == x,
while (x%y == 0) x = x / y
return x == 1
and the logarithm method (this is my version):
return ((log(y, x) % 1) == 0) // log(expression, base)
log(y, x) = log x y
Which method evaluates faster, especially for big numbers?
The logarithm method needs more care, because the logarithm function has a small amount of inaccuracy due to the use of floating-point approximations. For example 310 = 59049, but:
log(59049, 3)
===> 9.999999999999998
Whether you can compensate for this (by checking to see if the answer is "close enough" to the nearest integer) depends on the range of your x and y. If y is less than 232, then I think the closest the logarithm can proportionately get to an integer (without the true answer being an integer) is:
1 - log(4294967295, 65536) / 2
===> 1.049693665322593e-11
so pick an epsilon smaller than this and you can use the logarithm method with confidence:
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 */
}
If the allowable range for y is bigger, then you'll have to find the appropriate value for epsilon. But beware: for large enough y, there might be no suitable epsilon in double-precision floating-point. For example, if y can be as large as 248 − 1 then that's the case, because
log(281474976710655, 16777216)
===> 2.0 exactly
So for large enough y, you can't rely on the logarithm: you'll need to explicitly perform the exponentiation afterwards as a check.