fibonacci.py

#!/usr/bin/env python

# O(2^n), O(n)
def fib1(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib1(n-1) + fib1(n-2)

# O(n), O(n)
def fib2(n, f={ 0: 0, 1: 1 }):
    if n in f:
        return f[n]
    f[n] = fib2(n-1) + fib2(n-2)
    return f[n]

# O(n), O(1)
def fib3(n):
    f1, f2 = 0, 1
    for i in xrange(n):
        f2, f1 = f2 + f1, f2
    return f1


def mmul(m1, m2):
    m = []
    row1 = len(m1)
    row2 = len(m2)
    col2 = len(m2[0])

    for r in xrange(row1):
        row = []
        for c in xrange(col2):
            new = 0
            for k in xrange(row2):
                new += m1[r][k] * m2[k][c]
            row.append(new)
        m.append(row)
    return m

# O(logn), O(logn)
def fib4(n):
    def calc_coefs(n):
        e = [[1, 0],
             [0, 1]]
        c = [[0, 1],
             [1, 1]]
        if n == 0:
            return e
        elif n == 1:
            return c

        if n & 1:
            return mmul(calc_coefs(n-1), c)
        else:
            coef = calc_coefs(n/2)
            return mmul(coef, coef)

    return mmul([[0, 1]], calc_coefs(n))[0][0]

# O(logn), O(logn)
def fib5(n):
    def fib_iter(n, f2, f1, p, q):
        if n == 0:
            return f1
        if n & 1:
            return fib_iter(n-1, f1*q+f2*(q+p), f1*p+f2*q, p, q)
        else:
            return fib_iter(n/2, f2, f1, p*p+q*q, q*(q+2*p))

    return fib_iter(n, 1, 0, 0, 1)

if __name__ == '__main__':
    import sys
    import time
    import getopt

    n, nums = 262144, 3
    funcs = [fib3, fib4, fib5]

    def usage():
        print "Usage: %s [-f '<fun1> <fun2>...' | --functions='<fun1> <fun2>...'] [n] [nums]" % sys.argv[0]

    def getargs():
        if len(sys.argv) < 2:
            return
        try:
            global n, nums, funcs
            opts, args = getopt.getopt(sys.argv[1:], "hf:", ["help", "functions="])

            if len(args) > 0:
                n = int(args[0])
            if len(args) > 1:
                nums = int(args[1])

            for opt, arg in opts:
                if opt in ("-h", "--help"):
                    usage()
                    sys.exit()
                elif opt in ("-f", "--functions"):
                    funcs = [globals()[f] for f in arg.split()]
        except:
            usage()
            sys.exit(1)

    def timing(func, *args):
        start = time.clock()
        rtn = func(*args)
        end = time.clock()
        return (rtn, func.__name__, end - start)

    getargs()
    if not funcs:
        sys.exit(1);
    else:
        fmtstr = '%6d: ' + '%-6.3f ' * len(funcs)

    for i in xrange(n, n + nums):
        rtns = [timing(func, i) for func in funcs]
        print fmtstr % tuple([i] + [t for (_, _, t) in rtns])

Usage example: ./fibonacci.py -f 'fib1 fib2 fib5' 1 30