CODEWITHSUNDEEP
pythonlogarithm
omega
omega

Reputation: 43863

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

Upvotes: 5

Views: 15421

Answers (6)

Agahowa
Agahowa

Reputation: 1

I think I have a nice simple way of doing it (without calling a library) recursively:

def is_power_of(number, base):
  if number < base:
    return number == 1
  return is_power_of(number/base, base)

Upvotes: 0

Quint
Quint

Reputation: 1214

Here's a constant-time solution that handles every special case mentioned in the comments so far:

import math

def is_power(a, b, precision=14):
    if a == 1 or a == b:
        return True
    if b in (0, 1):
        return False
    return round(math.log(a, b), precision).is_integer()

Behavior for each special case:

a b is_power(a, b)
3^10 3 True ✔️
3^129 3 True ✔️
2 1 False ✔️
1 1 True ✔️
1 0 True ✔️
17^3 17 True ✔️

Upvotes: 0

paxdiablo
paxdiablo

Reputation: 881633

First, assuming you have a specific logarithm operator (many languages provide logarithms to base 10 or base e only), logab can be calculated as logxb / logxa (where x is obviously a base that your language provides).

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

So one way or another, you have a way to get logarithm to a specific base. From there, if the log of b in base a is an integer(note 1), then b is a power of a.

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 in {0, 1}:
        return num == base
    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 in {0, 1}:
        return num == base
    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 in {0, 1}:
        return num == base
    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.

(Note 1) Keep in mind here the possibility that floating point imprecision may mean it's not exactly an integer. You may well have to use a "close enough" comparison.

Upvotes: 10

Sachin Kumar
Sachin Kumar

Reputation: 11

>>>(math.log(int(num),int(base))).is_integer()

This will return a boolean value either true or false. This should work fine. Hope it helps

Upvotes: -1

Akavall
Akavall

Reputation: 86208

A very simple solution could go like this:

def ispower(n, base): 

    if n == base:
        return True

    if base == 1:
        return False

    temp = base

    while (temp <= n):
        if temp == n:
            return True
        temp *= base

    return False

Result:

>>> ispower(32, 2)
True
>>> ispower(81, 3)
True
>>> ispower(625, 5)
True
>>> ispower(50, 5)
False
>>> ispower(32, 4)
False
>>> ispower(2,1)
False
>>> ispower(1,1)
True

Upvotes: 5

Robᵩ
Robᵩ

Reputation: 168646

>>> def isPower(n, b):
...   return b**int(math.log(n, b)+.5)==n
... 
>>> isPower(128, 2)
True
>>> isPower(129, 2)
False
>>> isPower(3**10, 3)
True
>>> isPower(3**129, 3)
True
>>> isPower(10**500, 10)
True
>>> isPower(10**(10**6), 10)
True

EDIT: This code does fail for 1,1:

>>> isPower(1,1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in isPower
ZeroDivisionError: float division by zero

I'll leave it to the OP to decide if he wants to apply the trivial fix or rewrite his requirements.

Upvotes: 0

Related Questions