#! /usr/bin/env python
# -*- coding: utf-8 -*-
"""
Calculs des premiers éléments de la suite de Fibonacci.
Référence : http://fr.wikipedia.org/wiki/Suite_de_Fibonacci
Application de l'algorithme logarithmique
http://fr.wikipedia.org/wiki/Suite_de_Fibonacci#Algorithme_logarithmique
"""
def fibo2(n):
    """Renvoie F_{n-1}, F_n"""
    if n == 0:  # cas de base
        return 1, 0  # F_{-1}, F_0
    else:         # récurrence
        f_k_1, f_k = fibo2(n//2)        # F_{k-1}, F_k   avec k = n/2
        f2_k = f_k**2                   # F_k^2
        if n%2 == 0:  # n pair
            return f2_k + f_k_1**2,    f_k*f_k_1*2 + f2_k       # F_{2k-1}, F_{2k}
        else:         # n impair
            return f_k*f_k_1*2 + f2_k, (f_k + f_k_1)**2 + f2_k  # F_{2k},   F_{2k+1}
 
def fibonacci_item_logarithmic(n):
    """Renvoie F_n"""
    return fibo2(n)[1]

if __name__ == '__main__':
    i = input("Suite de Fibonacci. Donnez l'indice de l'élément souhaité ? ")
    print("Élément de la suite : "),
    printfibonacci_item_logarithmic(i)
    print('Premiers éléments de la suite : ')
    for j in range(10):
        print(j,fibonacci_item_logarithmic(j))