fib_fun.py

# /usr/bin/env python

# Author: Perry A. Stoll <perry at pstoll dot com>
# Date: June 2017
# Copyright Perry Stoll
#
# Generate the first N fibonnaci numbers.
#
#   Note this is quite different from generating the Nth fibonnaci
#   numbers in terms of storage and laying out the computation
#
# Fun with fibonnaci
#
# or...
#
# why generators are the right thing to create possibly large
# sequences in python
#
# and why I'll never actually use non-tail recursive functions in
# production code. or ever actually, since i'm not going to use a
# functional language, much to my detriment, i'm sure.

import sys, time
from contextlib import contextmanager

# thanks SO https://stackoverflow.com/questions/5478351/python-time-measure-function
@contextmanager
def timeit_context(name):
    startTime = time.time()
    yield
    elapsedTime = time.time() - startTime
    print('[{}] finished in {} ms'.format(name, int(elapsedTime * 1000)))

# Return a generator to return a sequence of fibonnaci numbers
# note this means the entire list is never actually in memory.
def yield_fib(n):
    if n > 0:
        yield 1
    if n > 1:
        yield 1
    prevprev = prev = 1
    for i in xrange(2,n):
        cur = prevprev + prev
        yield cur
        prevprev = prev
        prev = cur

# generate a list of fibonnaci numbers and return the list
def list_fib(n):
    out = []
    if n > 0:
        out.append(1)
    if n > 1:
        out.append(1)
    prevprev = prev = 1
    for i in xrange(2,n):
        cur = prevprev + prev
        out.append(cur)
        prevprev = prev
        prev = cur
    return out


def recur_fib_memoize_internal(n,accum=None):
    # memoize partial results
    if len(accum) >= n:
        cur = accum[n-1]
        return cur

    if n == 0:
        return 0
    elif n <= 2:
        cur = 1
        accum += [1] * n
    else:
        prev = recur_fib_memoize_internal(n-1, accum)
        prevprev = recur_fib_memoize_internal(n-2, accum)
        cur = prevprev + prev
        accum.append(cur)
    return cur

# recurisve approach with memoization to return a sequence of fibonnaci numbers
# this still blows the stack somewhere pretty low
def recur_fib_memoize(n):
    accum = []
    recur_fib_memoize_internal(n,accum)
    return accum

def recur_nth_fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        v = recur_nth_fib(n-2) + recur_nth_fib(n-1)
        return v

# purely recurisve approach to return a sequence of fibonnaci numbers
# beware - ridiculously inefficient
def recur_fib(n):
    accum = []
    for i in range(1,n+1):
        accum.append(recur_nth_fib(i))
    return accum


def test_fib(fib_func):
    # avoid writing newline/be compatible with python2 or 3
    sys.stdout.write("testing fib function {}...".format(fib_func.func_name))
    x = list(fib_func(1))
    assert( len(x) == 1 )
    assert( x[0] == 1)

    x = list(fib_func(2))
    assert( len(x) == 2 )
    assert( x[0] == 1)
    assert( x[1] == 1)

    x = list(fib_func(3))
    assert( len(x) == 3 )
    assert( x[0] == 1)
    assert( x[2] == 2)

    x = list(fib_func(5))
    assert( len(x) == 5 )
    assert( x[-1] == 5)

    x = list(fib_func(6))
    assert( len(x) == 6 )
    assert( x[-1] == 8)

    x = list(fib_func(7))
    assert( len(x) == 7 )
    assert( x[-1] == 13)

    # http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
    tests = [ (20,6765),
              (30,832040),
              (40,102334155),
              (50,12586269025),
              (100,354224848179261915075)]
    if fib_func.func_name == "recur_fib":
        # too big to test for the recursive functions...
        sys.stdout.write("skipping large values for recur_fib")
    else:
        for (nn,val) in tests:
            x = list(fib_func(nn))
            assert( len(x) == nn )
            assert( x[-1] == val)
    print("\ttests passed")

def sum_fib_series(magnitude, fib_func):
    sum = 0
    for n in fib_func(10**magnitude):
        sum += n
    return sum

def time_one_fib(exp, func):
    with timeit_context('Fib function {} for 10**{}'.format(func.func_name,exp)):
        try:
            sum_fib_series(exp, func)
        except RuntimeError:
            print("  hit a recursion depth limit for {}.".format(func.func_name))
    
def time_fib():
    funcs = [recur_fib_memoize]
    for exp in range(1,4):
        for func in funcs:
            time_one_fib(exp, func)

    funcs = [yield_fib, list_fib]
    for exp in range(1,7):
        for func in funcs:
            time_one_fib(exp, func)

            
if __name__ == '__main__':
    for fib_func in (yield_fib, list_fib, recur_fib, recur_fib_memoize):
        test_fib(fib_func)
    time_fib()

results.txt

Stoll-MBP:fib pstoll$ python fib_fun.py
testing fib function yield_fib... 	tests passed
testing fib function list_fib... 	tests passed
testing fib function recur_fib... skipping large values for recur_fib 	tests passed
testing fib function recur_fib_memoize... 	tests passed
[Fib function recur_fib_memoize for 10**1] finished in 0 ms
[Fib function recur_fib_memoize for 10**2] finished in 0 ms
  hit a recursion depth limit for recur_fib_memoize.
[Fib function recur_fib_memoize for 10**3] finished in 1 ms
[Fib function yield_fib for 10**1] finished in 0 ms
[Fib function list_fib for 10**1] finished in 0 ms
[Fib function yield_fib for 10**2] finished in 0 ms
[Fib function list_fib for 10**2] finished in 0 ms
[Fib function yield_fib for 10**3] finished in 0 ms
[Fib function list_fib for 10**3] finished in 0 ms
[Fib function yield_fib for 10**4] finished in 6 ms
[Fib function list_fib for 10**4] finished in 11 ms
[Fib function yield_fib for 10**5] finished in 322 ms
[Fib function list_fib for 10**5] finished in 674 ms
[Fib function yield_fib for 10**6] finished in 28306 ms
Killed: 9
# note list_fib for 10**6 ran out of ram/swap space and was killed by the OS
# the moral being - avoid keeping huge lists in memory if you can avoid it - hence generators.