Exploring Exponentiation

"""Exponentiation functions
 
Explores section "1.2.4 Exponentiation" from Structure and Interpretation of
Computer Programs (SICP) by Abelson and Sussman.
"""
 
def slow_rec_exp(a, b):
    """Slow, recursive exponent function.
 
    Calculates a**b recursively in both O(b) time and space.
    """
    if b == 0:
        return 1
    else:
        return a * slow_rec_exp(a, b - 1)
 
def slow_iter_exp(a, b):
    """Slow, iterative exponent function.
 
    Calculates a**b iteratively in both O(b) time and space.
    Note that the term 'iterative' here comes from the definition used in
    SICP. Tail-recursion optimization is assumed.
    """
    def helper(a, b, accum):
        if b == 0:
            return accum
        else:
            return helper(a, b - 1, a * accum)
    return helper(a, b, 1)
 
def fast_rec_exp(a, b):
    """Fast, recursive exponent function.
 
    Calculates a**b recursively in both O(log(b)) time and space.
    This is a python translation of the fast-expt function from page 45 of
    SICP.
    """
    if b == 0:
        return 1
    elif b % 2 == 0:
        n = fast_rec_exp(a, b / 2)
        return n * n
    else:
        return a * fast_rec_exp(a, b - 1)
 
def fast_iter_exp(a, b):
    """Fast, iterative exponent function.
 
    Calculates a**b iteratively in both O(log(b)) time and space.
    This is a python solution to exercise 1.16 from SICP. As with slow_iter_exp
    the tail-recursion optimization is assumed.
    """
    def helper(a, b, accum):
        if b == 0:
            return accum
        elif b % 2 == 0:
            a = a * a
            b = b / 2
        else:
            accum = accum * a
            b = b - 1
        return helper(a, b, accum)
    return helper(a, b, 1)