In [1]:

    

import numpy as np

n = 100


    

In [2]:

    

def fib1(n):
    """ dynamic programming based Fibonacci computation (with np.array, (O(n)  memory)) """
    a = np.zeros(n)
    a[0] = a[1] = 1
    for i in range(2,n):
        a[i] = a[i-1] + a[i-2]
    return a[-1]


    

In [3]:

    

%%timeit
fib1(n)


    

    




The slowest run took 16.65 times longer than the fastest. This could mean that an intermediate result is being cached 
10000 loops, best of 3: 29.2 µs per loop

In [4]:

    

def fib2(n):
    """ dynamic programming based Fibonacci computation (with list, (O(n) memory)) """
    a = [1, 1]
    for i in range(2,n):
        a.append(a[i-1] + a[i-2])
    return a[-1]


    

In [5]:

    

%%timeit
fib2(n)


    

    




100000 loops, best of 3: 17 µs per loop

In [6]:

    

def fib3(n):
    """ recursive Fibonacci computation """
    if n == 1 or n == 2:
        return 1.
    else:
        return fib2(n-1) + fib2(n-2)


    

In [7]:

    

%%timeit
fib3(n)


    

    




10000 loops, best of 3: 33.1 µs per loop

In [8]:

    

def fib4(n):
    """ dynamic programming based Fibonacci computation (O(1) memory) """
    m1 = 1
    m2 = 1
    i = 3
    while i < (n + 1):
        curr = m1 + m2
        m1 = m2
        m2 = curr
        i += 1
    return curr


    

In [9]:

    

%%timeit
fib4(n)


    

    




100000 loops, best of 3: 9.64 µs per loop

In [ ]: