How do I ensure that a number is a power of another number using logarithmic property in Python3?

Question

I want to check if a number x is an exponential power of another number, y. I understand mathematics: use logarithms.

However, when I did this approach in Python3, using log() function, I got weird results. I wanted to test whether 243 is a power of 3, which it is, my code returned False. My code is as follows:

power = log(n, 3)
if (int(power)) == power:
    return True

I get 4.999999999999999 as the result in power. I read about the precision and other tactical details pertaining to floating points and logarithms in Python3 and I tried those solutions but none of them gave me the answer that I know is correct as far as basic maths is concerned.

I tried this:

from math import log
from decimal import Decimal, Context

class Power:
    def power_func(self, n: int) -> bool:
        if n == 0:
            return False
        ctx = Context(prec=20)
        power = log(n, Decimal(3))
        if (int(power)) == power:
            return True
        return False

I think I am missing some basics of Python here but not sure how to proceed further. I know other solutions to do the task but I wanted to achieve this using logarithms in Python3.

Answer 1

Don't use logarithms; they rely on real arithmetic to work correctly, which Python cannot do.

Instead, use repeated squaring to approach n from the base.

def is_power_of(n, b):
    y = b
    # Compute y = b**2, b**4, ..., b**2**i until y reaches or exceeds n
    # i = 1
    while y < n:
        y = y * y
        # i *= 2

    # If we overshoot, divide by b until we either
    # reach n or get a non-zero remainder
    while y > n:
        y, r = divmod(y, b)
        # i -= 1
        if r:
            return False
    else:
        return y == n

Note that if the function returns true, i will be the value such that b**i == n.

Answer 2

Using log from Previous Post

from math import log

def is_power(a, b):
  " check if a is a power of b (i.e. b is base)"
  if b == 1 or a == 0: return False
  return return b ** int(round(log(a, b))) == a


print(is_power(243, 3))  # returns True

This should work for practical numbers

It may be worth noting that while this solution isn't totally infallible for large values, depending as it does on floating-point accuracy, a would have to be spectacularly large for that to be a problem. E.g., with b = 2, a = 2**(2**53 + 1) and IEEE 754 floats, this can't possibly work, but you'd need approximately 1.2 PB of RAM and a machine with an address space bigger than 2**48 to be able to represent that value of a in the first place. --Mark Dinkinson

Yes, there's no computer in existence with enough memory to hold integers large enough for this to plausibly fail. But I didn't mention that, because if the OP was surprised that log() may not be exact in all cases, they're not quite ready to appreciate an argument about the far-flung limits of theoretical possibilities ;-) – Tim Peters

Performance

Compared to powers methods such as is_power_of routine used in @chepner solution

for k in range(1, 300):
    num = 3**k
    assert is_power_of(num, 3) == is_power(num, 3)

There are no asserts so the two methods equal at least up till 3^300 =136891479058588375991326027382088315966463695625337436471480190078368997177499076593800206155688941388250484440597994042813512732765695774566001 (144 digits)

num = 3**300
%timeit is_power_of(num, 3)--uses powers
100000 loops, best of 3: 136 µs per loop

%timeit is_power(num, 3)--uses log
100000 loops, best of 3: 2.71 µs per loop

Thus, log method is over 50X faster for large numbers However, the two methods are comparable for smaller numbers

Answer 3

return 3**math.ceil(power) == n or 3**math.floor(power) == n

Answer 4

It seems like the question insists to use and handle log(), but naively it's impossible to achieve perfect precision for computer like @DarryIG implied.

Without log(), a better approach is probably not using multiplication from base number since it will take a lot of repeat calculation. Instead, go with division and check remainder for quicker converge. As long as y%b is not integer, we can immediately terminate the computation.

def isPower(n,b):
  y = n
  while y % b == 0: y /= b
  return y == 1