Integer exponentiation

integer_exponentiation.py

import math

# Python ≥ 3.5

def recursive_linear(b, n):
    if n < 0:
        return (1/b) * recursive_linear(b, n+1)
    if n == 0:
        return 1
    else:
        return b * recursive_linear(b, n-1)

def recursive_log(b, n):
    if n == 0:
        return 1
    else:
        p = recursive_log(b, int(n/2))
        b = 1/b if n<0 else b
        return p*p * (b if n % 2 else 1)

def iterative_linear(b, n):
    p = 1
    b = 1/b if n < 0 else b
    for _ in range(abs(n)):
        p *= b
    return p

def iterative_log_left2right(b, n):
    p = 1
    b = 1/b if n<0 else b
    n = abs(n)  # If n<0
    for i in range(n.bit_length() - 1, -1, -1):
        bit = (n >> i) & 1
        p *= p * (b if bit else 1)
    return p

def iterative_log_right2left(b, n):
    p = 1
    b = 1/b if n<0 else b
    n = abs(n)  # If n<0
    for i in range(n.bit_length()):
        bit = (n >> i) & 1
        p *= b if bit else 1
        b *= b
    return p

def iterative_log_right2left_whileloop(b, n):
    p = 1
    b = 1/b if n<0 else b
    n = abs(n)  # If n<0
    while n:
        bit = n % 2
        p *= b if bit else 1
        b *= b
        n //= 2
    return p

# Test
def test():
    functions = (recursive_linear,
                 recursive_log,
                 iterative_linear,
                 iterative_log_left2right,
                 iterative_log_right2left,
                 iterative_log_right2left_whileloop,
                 )
    for f in functions:
        for b in range(-100, 100):
            for n in range(-100, 100):
                try:
                    expected = b**n
                except ZeroDivisionError:
                    continue
                actual = f(b, n)
                isclose = math.isclose(expected, actual)
                try:
                    assert(isclose)
                except AssertionError:
                    print(f.__name__, b, n, expected, actual)
                    return

test()