Differences

This shows you the differences between two versions of the page.

random:exploring_exponentiation [2011/10/14 14:23] (current)
grant created
Line 1: Line 1:
 +====== Exploring Exponentiation ======
 +
 +<code python>
 +"""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)
 +</code>
random/exploring_exponentiation.txt · Last modified: 2011/10/14 14:23 by grant