omega omega - 3 months ago 14
Python Question

how to check if a number is a power of base b?

In python, how can you check if a number n is an exact power of base b?

Note: it needs to be generalized to any base which is given as a parameter.

Here is what I got:

Assume n and base are integers > 0.

import math
def is_power(n,base):
return math.log(n,base) == base**n

Answer

Assuming you have a specific logarithm operator, logab can be calculated as logxb / logxa and, if the log of X in base Y is an integer, then X is a power of Y.

But Python goes one better since it can work out the logarithm for an arbitrary base without that tricky equality above.

So I'd start with the following code, now with added edge-case detection:

# Don't even think about using this for negative powers :-)

def isPower (num, base):
    if base == 1 and num != 1: return False
    if base == 1 and num == 1: return True
    if base == 0 and num != 1: return False
    power = int (math.log (num, base) + 0.5)
    return base ** power == num

See for example the following complete program which shows this in action:

import math

def isPower (num, base):
    if base == 1 and num != 1: return False
    if base == 1 and num == 1: return True
    if base == 0 and num != 1: return False
    power = int (math.log (num, base) + 0.5)
    return base ** power == num

print isPower (127,2)       # false
print isPower (128,2)       # true
print isPower (129,2)       # false
print

print isPower (26,3)        # false
print isPower (27,3)        # true
print isPower (28,3)        # false
print isPower (3**10,3)     # true
print isPower (3**129,3)    # true
print

print isPower (5,5)         # true
print isPower (1,1)         # true
print isPower (10,1)        # false

If you're the sort that's worried about floating point operations, you can do it with repeated multiplications but you should test the performance of such a solution since it's likely to be substantially slower in software than it is in hardware. That won't matter greatly for things like isPower(128,2) but it may become a concern for isPower(verybignum,2).

For a non-floating point variant of the above code:

def isPower (num, base):
    if base == 1 and num != 1: return False
    if base == 1 and num == 1: return True
    if base == 0 and num != 1: return False
    testnum = base
    while testnum < num:
        testnum = testnum * base
    return testnum == num

But make sure it's tested against your largest number and smallest base to ensure you don't get any performance shocks.

Comments