# 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>