# -*- coding: utf-8 -*-
"""
Created on Tue Sep  9 14:41:12 2014

@author: denis.conduche
"""

import sys as sys # pour changer la limite du nombre d'appels recursifs
import time as t  # pour mesurer les temps

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


def Fibo_iter(n):
    # les variables u_k2 et u_k1 représentent u_k-2 et u_k-1
    u_k2,u_k1=0,1
    if n <= 0:
        return n
    for i in range(1,n):
        u_k=u_k1+u_k2
        u_k2=u_k1
        u_k1=u_k
    return u_k

def Fibo_memo(n):
    L=[-1]*(n+1)
    L[0]=0
    L[1]=1
    def Fibo_rec(k):
        if L[k] == -1: #La case de L n'est pas remplie
            L[k]=Fibo_rec(k-2)+Fibo_rec(k-1)
        return L[k]
    return Fibo_rec(n)

def Fibo_mieux(n):
    """ Mémoïsation et formule récursive efficace"""
    L=[-1]*(n+1)
    L[0]=0
    L[1]=1
    def Fibo_rec(k):
        if L[k] == -1: #La case de L n'est pas remplie
            if k%2 == 0:
                L[k]=2*Fibo_rec(k//2)*Fibo_rec(k//2-1)+Fibo_rec(k//2)**2
            else:
                L[k]=Fibo_rec(k//2)**2+Fibo_rec(k//2+1)**2
#            L[k]=Fibo_rec(k-2)+Fibo_rec(k-1)
        return L[k]
    return Fibo_rec(n)

def chronometre(fonction,arg_fonc):
    debut = t.time()
    fonction(arg_fonc)
    fin = t.time()
    return fin - debut


""" Tests :"""

sys.setrecursionlimit(10000)
   #
n=6401
print('n = ',n,', temps en secondes')
#print(Fibo_naif(n))
for fibo in [Fibo_iter,Fibo_memo,Fibo_mieux]:
    print(str(fibo), ' :' ,chronometre(fibo,n))