##Fibonacci served 7 ways
##A collection of functions for calculating Fibonacci numbers

##1  Recursion method on two lines
def fib_rec1(n):
    if n < 2: return n  
    return fib_rec1(n - 1) + fib_rec1(n - 2)

##2  Recursion method on one line
def fib_rec2( n ):
    return n if n < 2 else fib_rec2( n - 1 ) + fib_rec2( n - 2 )


##3  Using the Binet formula
##However values become non integral due to approximate square root
##calculations and must be rounded
def fib_Binet(n):
    fi = (1 + math.sqrt(5))/2
    return int((fi**n - (-fi)**-n)/math.sqrt(5))

##4  First iterative method
def fib_iterative1(n):
    i=0
    j=1
    if n==0:
        return n
    else:
        for m in range(1,n):
            k=i+j
            i=j
            j=k
        return j

##5  Second iterative method
def fib_iterative2(n):
    i,j = 1,0
    for k in range(1,n + 1):
        i,j = j, i + j
    return j

##6  Creating a Python list
def fib_list(n):
   fibValues = [0,1]
   for i in range(2,n+1):
      fibValues.append(fibValues[i-1] + fibValues[i-2])
   return fibValues[n]

##7  Using a Python dictionary to improve recursion.
##We can use a dictionary to save previous computations in a function call,
##replacing all the repeated recursion computations by fast dictionary look-ups.
fibTable = {0:0, 1:1}
def fib_dict(n):
  
   if n in fibTable:
      return fibTable[n]
   else:
      fibTable[n] = fib_dict(n-1) + fib_dict(n-2)
      return fibTable[n]



##8 Another version of 7 using a dictionary to improve recursion
##but without preloaded values.
CACHE = {}
def fib_cached(n):
   
    if n in CACHE:
        return CACHE[n]
    if n < 2:
        return n
    else:
        CACHE[n]= fib_cached(n - 1) + fib_cached(n - 2)
        
        return CACHE[n]

#main program    
import time
import math

print("***Time comparisons of various algorithms for calculating Fibonacci numbers***")
print()
choice="y"
while choice=="y":
    select=1
    n=int(input("""
We label \"0\" as the first with position 0.
Note that the recursion algorithms may take excessive times for terms > 35
We will time 7 different algorithms!
Which Fibonacci term do you wish to calculate? """) )
    print()
    while select<9:     
        if select==1:
            print(select,"Recursion algorithm One")
            print("Fibonacci number",n,"is",fib_rec1(n))
            count = 0
            total = 0
            for count in range(10):
                start_time = time.clock()
                fib_rec1(n)
                end_time = time.clock()
                total=total + end_time - start_time
                print ("time taken",end_time - start_time)
                count+=1
            print("total = ",total," average = ",total/10)
        elif select==2:
            print(select,"Recursion algorithm Two")
            print("Fibonacci number",n,"is",fib_rec2(n))
            count = 0
            total = 0
            for count in range(10):
                start_time = time.clock()
                fib_rec2(n)
                end_time = time.clock()
                total=total + end_time - start_time
                print ("time taken",end_time - start_time)
                count+=1
            print("total = ",total," average = ",total/10)
        elif select==3:
            print(select,"Binet formula algorithm")
            print("Fibonacci number",n,"is",fib_Binet(n))
            
            count = 0
            total = 0
            for count in range(10):
                start_time = time.clock()
                fib_Binet(n)
                end_time = time.clock()
                total=total + end_time - start_time
                print ("time taken",end_time - start_time)
                count+=1
            print("total = ",total," average = ",total/10)
        elif select==4:
            fib_iterative1(n)
            print(select,"First iteration algorithm")
            print("Fibonacci number",n,"is",fib_iterative1(n))
            
            count = 0
            total = 0
            for count in range(10):
                start_time = time.clock()
                fib_iterative1(n)
                end_time = time.clock()
                total=total + end_time - start_time
                print ("time taken",end_time - start_time)
                count+=1
            print("total = ",total," average = ",total/10)
        elif select==5:
            print(select,"Second iteration algorithm")
            print("Fibonacci number",n,"is",fib_iterative2(n))
            
            count = 0
            total = 0
            for count in range(10):
                start_time = time.clock()
                fib_iterative2(n)
                end_time = time.clock()
                total=total + end_time - start_time
                print ("time taken",end_time - start_time)
                count+=1
            print("total = ",total," average = ",total/10)
        elif select==6:        
            print(select,"List based algorithm")
            print("Fibonacci number",n,"is",fib_list(n))
             
            count = 0
            total = 0
            for count in range(10):
                start_time = time.clock()
                fib_list(n)
                end_time = time.clock()
                total=total + end_time - start_time
                print ("time taken",end_time - start_time)
                count+=1
            print("total = ",total," average = ",total/10)
        elif select==7:
            print(select,"Dictionary based algorithm")
            print("Fibonacci number",n,"is",fib_dict(n))
            
            count = 0
            total = 0
            for count in range(10):
                start_time = time.clock()
                fib_dict(n)
                end_time = time.clock()
                total=total + end_time - start_time
                print ("time taken",end_time - start_time)
                count+=1
            print("total = ",total," average = ",total/10)
        elif select==8:
            print(select,"Recursion using a cache ")
            print("Fibonacci number",n,"is",fib_cached(n))
            count = 0
            total = 0
            for count in range(10):
                start_time = time.clock()
                fib_cached(n)
                end_time = time.clock()
                total=total + end_time - start_time
                print ("time taken",end_time - start_time)
                count+=1
            print("total = ",total," average = ",total/10)
##        
##        print (time.clock() - start_time, "seconds")
##        print()
        select+=1
    choice=input("Do you wish to run this again? ")