def hanoi(n, a, b, c):
    '''Print the sequence of moves to move n disks from peg a to peg b using
    peg c as a spare peg.'''
    if n == 1:
        print 'Move from peg', a, 'to peg', b
    else:
        hanoi(n - 1, a, c, b)
        print 'Move from peg', a, 'to peg', b
        hanoi(n - 1, c, b, a)
        
def power(x, n):
    '''Compute x**n recursively.'''
    if n == 0:
        # Base case, x**0 == 1
        return 1
    # Recursively compute x**(n/2) (integer division)
    temp = power(x, n / 2)
    if n % 2 == 0:
        return temp * temp
    else:
        return x * temp * temp
        
def mat_mult(mat_a, mat_b):
    '''Multiply the two matrices mat_a and mat_b together.'''
    n = len(mat_a)
    m = len(mat_b[0])
    p = len(mat_a[0])
    # n x m matrix for the result.
    mat_c = [[0] * m for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(p):
                mat_c[i][j] += mat_a[i][k] * mat_b[k][j]
    return mat_c
    
def mat_power(mat_a, n):
    '''Compute mat_a**n, where mat_a is a square matrix.'''
    if n == 0:
        # Base case, return the identity matrix.
        mat_one = [[0] * len(mat_a) for i in range(len(mat_a))]
        for i in range(len(mat_one)):
            mat_one[i][i] = 1
        return mat_one
    else:
        mat_temp = mat_power(mat_a, n / 2)
        if n % 2 == 0:
            return mat_mult(mat_temp, mat_temp)
        else:
            return mat_mult(mat_a, mat_mult(mat_temp, mat_temp))
            
def slow_fib(n):
    '''Compute the nth Fibonacci number using the reccurence
    f(n) = f(n - 1) + f(n - 1), f(0) = f(1) = 1'''
    if n == 0 or n == 1:
        # Base case.
        return 1
    else:
        return slow_fib(n - 1) + slow_fib(n - 2)
        
def fast_fib(n):
    '''Compute the nth Fibonacci number iteratively, storing the values in
    a list.'''
    # List of length n + 2 to handle special casea of n == 0, n == 1
    fib = [0] * (n + 2)
    fib[0] = 1
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]
    
def binary_search(list_a, value, low, high):
    '''Search for value in list_a[low:high + 1].  Return the index if found,
    otherwise return -1.'''
    if low == high:
        if list_a[low] == value:
            return low
        else:
            return -1
    else:
        mid = (low + high) / 2
        if list_a[mid] < value:
            return binary_search(list_a, value, mid + 1, high)
        else:
            return binary_search(list_a, value, low, mid)
            
def faster_fib(n):
    '''Compute the nth Fibonacci number using matrix exponentiation.'''
    mat_fib =  [[1, 1],[1, 0]]
    mat_fib_n = mat_power(mat_fib, n)
    return mat_fib_n[1][0] + mat_fib_n[1][1]
    
if __name__ == '__main__':
    # 3 disk Towers of Hanoi
    hanoi(3, 1, 3, 2)

    # All print the same value.
    print slow_fib(20)
    print fast_fib(20)
    print faster_fib(20)
    
    # slow_fib is too slow for n = 200 (exponential growth).
    print fast_fib(200)
    print faster_fib(200)
    
    # Short test for binary_search.  As an exercise, prove it is correct.
    list_a = range(1000)
    for i in range(1000):
        assert binary_search(list_a, i, 0, len(list_a) - 1) == i
    assert binary_search(list_a, -1, 0, len(list_a) - 1) == -1
    assert binary_search(list_a, len(list_a), 0, len(list_a) - 1) == -1