

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

The Fibonacci Numbers

The Fibonacci Numbers $F_n$ are defined by induction for all $n\in\mathbb{N}$:

$F_0 := 0$,
$F_1 := 1$,
$F_{n+2} = F_{n+1} + F_n$.

The function $\texttt{fib}(n)$ computes the number $F_n$.



In [ ]:

    
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)



In [ ]:

    
[fib(n) for n in range(19)]



In [ ]:

    
import time
import numpy             as np
import matplotlib.pyplot as plt



In [ ]:

    
m = 36
Y = []
for n in range(m):
    start = time.time()
    print(f'fib({n}) = {fib(n)}')
    stop  = time.time()
    print(stop - start)
    Y.append(stop - start)
Y = np.array(Y)



In [ ]:

    
X = np.array(range(m))
plt.figure(figsize=(12, 8))
plt.plot(X, Y) 
plt.xlabel('n')
plt.ylabel('time in seconds')
plt.title('Time to Compute the Fibonacci Numbers')
plt.show()



In [ ]:

    
plt.figure(figsize=(12,8))
plt.plot(X, Y) 
plt.yscale('log')
plt.xlabel('n')
plt.ylabel('time in seconds')
plt.title('Time to Compute the Fibonacci Numbers, Logarithmic Plot')
plt.show()

If we want to compute the Fibonacci numbers efficiently, we must not compute the valuefib(n) for a given n twice. The easiest way to achieve this is by storing the Fibnacci numbers in a list L. In the implementation below, L[n] stores the $n$-th Fibonacci number.



In [ ]:

    
def fibMem(n):
    if n <= 1:
        return n
    L    = [0 for k in range(n+1)]
    L[0] = 0
    L[1] = 1
    for k in range(2, n+1):
        L[k] = L[k-1] + L[k-2]
    return L[n]



In [ ]:

    
%%time
x = fibMem(10000)



In [ ]:

    
x



In [ ]:

    
def memoize(f):
    cache = {}
    def memoizedF(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoizedF



In [ ]:

    
fib = memoize(fib)



In [ ]:

    
fib(1000)



In [ ]:

    
fib(10000)



In [ ]:

    
import sys



In [ ]:

    
sys.setrecursionlimit(20000)



In [ ]:

    
%%time
fib(10000)



In [ ]: