import sys,time
sys.setrecursionlimit(100000)

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

def fiba( n ):
    if n < 2: return n
    else: return fiba( n-1 ) + fiba( n-2 )
# fib and fiba are different names for same function
# we will MEMOIZE the fib function later in the code
def binFib(n):
	a,b,u,v=0,1,0,1
	while (n>0):
	  if (n%2==0):
	    dummy=a
	    a=a*a+b*b
	    b=2*dummy*b + b*b
	    n=n/2
	  else:
	    n=n-1
	    dummy=u
	    u=a*u+b*v
	    v=b*dummy+(a+b)*v
	return u

def memoize( f ):
    Table = {}
    
    def new_f( n ):
        if n in Table: return Table[n]
        result = f( n )
        Table[n] = result
        return result
    return new_f

fib=memoize(fib)
x,y=7000,38
start_time = time.time()
print(binFib(x))
print ("Time taken for binary powering solution for input ", x," was ", \
                (time.time() - start_time)," seconds.")
start_time = time.time()
print(fib(x))
print ("Time taken for memoized function for input ", x," was ", \
                (time.time() - start_time)," seconds.")
start_time = time.time()
print(fiba(y))
print ("Time taken for non-memoized recursive function for input ", y," was ", \
                (time.time() - start_time)," seconds.")