Python 2.7 program to check whether two integer powers are equal, WITHOUT computing the powers.

equal_powers.py

# Python 2.7 program to check whether two integer powers are equal,
# WITHOUT computing the powers.
#
# Author: David Radcliffe, 1 December 2013.

ALLOW_ZERO_TO_ZERO = True
# If True, assume that 0 to the 0 is 1.
# If False, assume that 0 to the 0 is undefined.

# Return the sign of a^b. There are four possible results
#   1  if a^b > 0
#  -1  if a^b < 0
#   0  if a^b = 0
# None if a^b is undefined

def sign_power(a, b):
    if a > 0:
        return 1
    elif a < 0:
        if b % 2 == 0:
            return 1
        else:
            return -1
    elif b > 0:
        return 0
    elif b == 0 and ALLOW_ZERO_TO_ZERO:
        return 1
    else:
        return None

# The following function determines whether the powers
# a1^b1 and a2^b2 are equal. We assume that a1, a2, b1, b2 are integers.

def equal_powers(a1, a2, b1, b2):

    # Ensure that a1^b1 and a2^b2 are both defined and have the same sign.
    sgn = sign_power(a1, b1)
    if sgn is None or sgn != sign_power(a2, b2):
        return False

    # If signs are both zero then the powers are equal.
    if sgn == 0:
        return True

    # Force the bases to be non-negative integers.
    a1 = abs(a1)
    a2 = abs(a2)

    # Handle the case where a1=b1=0 or a2=b2=0.
    if a1 == 0:
        return a2 == 1 or b2 == 0
    if a2 == 0:
        return a1 == 1 or b1 == 0
    

    # Swap numbers if needed to ensure that a1 <= a2.
    if a1 > a2:
        a1, a2, b1, b2 = a2, a1, b2, b1

    while a1 > 1:

        # If bases are equal, check that exponents are equal.
        if a1 == a2:
            return b1 == b2

        # Check that one base divides the other.
        if a2 % a1 != 0:
            return False

        # Reduce to a simpler case, using the fact that
        #(a1)^(b1) = (a2)^(b2) is equivalent to (a1)^(b1-b2) = (a2/a1)^(b2),
        # which is obtained by dividing both sides by (a1)^(b2).
        a2 /= a1
        b1 -= b2

        # Swap numbers if needed to ensure that a1 <= a2
        if a1 > a2:
            a1, a2, b1, b2 = a2, a1, b2, b1

    # Left side equals 1. Check that right side also equals 1.
    return a2 == 1 or b2 == 0
  
def test_equal_powers():
    print equal_powers(10, 10**6, 6, 1)     # True
    print equal_powers(100, 1000, 3, 2)     # True
    print equal_powers(128, 4, 2, 7)        # True
    print equal_powers(0, 1, 0, -400)       # True
    print equal_powers(-4, 2, -4, -8)       # True
    print equal_powers(0, -1, 0, 2)         # True
    print equal_powers(-4, 2, -4, -7)       # False
    print equal_powers(3, -3, 7, 7)         # False
    print equal_powers(2, 4, 3, 2)          # False
    print equal_powers(2, 10000, 10000, 2)  # False
    print equal_powers(0, -1, 0, 1)         # False