Fibonacci Number methods w/timing

fibonacci_number.py

import timeit
#import sys


# Implementation:
def matmult(A, B):
    # multiplies 2x2 matrix
    def val(i, j):
        return (A[i][0] * B[0][j]) + (A[i][1] * B[1][j])
    return ((val(0, 0), val(0, 1)),
            (val(1, 0), val(1, 1)),)


def matrix_power(A, n):
    if n == 0:
        return ((1, 0), (0, 1))
    if n % 2 == 1:
        return matmult(A, matrix_power(A, n - 1))
    else:
        root = matrix_power(A, n / 2)
        return matmult(root, root)


def fib_matrix(n):
    M = ((0, 1), (1, 1))
    return matrix_power(M, n)[0][1]


#-------------------------------------#

def fib_num_rec(x):
    if x == 0:
        return 0
    elif x == 1:
        return 1

    return fib_num_rec(x - 2) + fib_num_rec(x - 1)


#-------------------------------------#

def fib_num_rec_acc(n):
    def fib_num_rec_acc_in(n, x0, x1):
        if n == 0:
            return x0
        return fib_num_rec_acc_in(n - 1, x1, x0 + x1)

    return fib_num_rec_acc_in(n, 0, 1)


#-------------------------------------#

def fib_num_imp(x):
    x0 = -1
    x1 = 1
    num = x0 + x1

    for n in range(x):
        x0 = x1
        x1 = num
        num = x0 + x1

    return num


#-------------------------------------#

memo = {0: 0, 1: 1}


def fib_memo(n):
    if not n in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]


#-------------------------------------#

memo_arr = [0, 1]


def fib_memo_arr(n):
    if len(memo_arr) < n:
        memo_arr.append(fib_memo_arr(n - 1) + fib_memo_arr(n - 2))
    return memo_arr[n - 1]


#-------------------------------------#

# Testing & Timing:
def testit(f, rng):
    func_name = f.func_name

    print func_name + ":"
    print "Works: " + \
        str([f(x) for x in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34])

    stmt = "[%s(x) for x in range(%d)]" % (func_name, rng)
    setup = "from __main__ import %s" % (func_name)
    number = 10 ** 6
    print "Time: %f\n" \
          % (timeit.timeit(stmt, setup=setup, number=number))


# Main:
if __name__ == '__main__':
    rng = 100
    testit(fib_memo, rng)
    testit(fib_memo_arr, rng)
    testit(fib_num_imp, rng)
    testit(fib_num_rec_acc, rng)
    #testit(fib_num_rec, rng)
    testit(fib_matrix, rng)