The Fibonnaci Series

Here we have a relatively fast, though memory intensive, program to find the N^th Fibonnaci Number. This uses Prof. Edsgar W Dijkstra's algorithm as described in this paper. In brief the idea is:

F(2n-1) = F(n-1)² + F(n)²
F(2n) = ( 2 F(n-1) + F(n) ) F(n)

Without further ado, here we are:

# Program to compute the Nth term of the Fibonacci series.
# Rohit Krishna Kumar
# A big list to store the numbers we have already generated
fib_list = [None] * 10**5

def fib(n):
    if(n == 1):
        return 1
    if(n == 0):
        return 0
    if(fib_list[n] != None):
        return fib_list[n]
    # By definition: Fib(n) = Fib(n-1) + Fib(n-2)            
    if(fib_list[n-1] != None and fib_list[n-2] != None):
        fib_list[n] = fib_list[n-1] + fib_list[n-2]
        return fib_list[n]
    # In Honour Of Fibonnaci. Dijikstra's method.
    if(n % 2 == 0):
        fib_list[n] = (2 * fib((n/2) -1 ) + fib(n/2))*fib(n/2)
        return fib_list[n]
    else:        
        fib_list[n] = ((fib(((n+1)/2) - 1))**2 + (fib((n+1)/2))**2)
        return fib_list[n]