##                                                                TP matrices


## Exercice: 

def dimensions(A):
    return len(A),len(A[0])



def affiche(A):
    for ligne in A:
        print(A)


def matrice_nulle(n,p):
    return [ [0 for j in range(p)] for i in range(n)]

def identite(n):
    In = matrice_nulle(n,n)
    for i in range(n):
        In[i][i] =1
    return In


def copie_matrice(A):
    n,p = dimensions(A)
    C = [ [A[i][j] for j in range(p)] for i in range(n)]
    return C

# cette copie fonctionne à condition que les coefficients de la matrice soient immutables.
# On utilisera copy.deecopy pour une copie profonde



## Exercice: opérations matricielles

def somme_matrice(A,B):
    n,p = dimensions(A)
    q,r = dimensions(B)
    assert (n,p)  == (q,r)
    C = matrice_nulle(n,p)
    for i in range(n):
        for j in range(p):
                C[i][j] =  A[i][j] + B[i][j]
    return C

def mult_scalaire(A,mu):
    n,p = dimensions(A)
    C = matrice_nulle(n,p)
    for i in range(n):
        for j in range(p):
                C[i][j] =  mu*A[i][j]
    return C


def produit_matrice(A,B):
    n,p = dimensions(A)
    q,r = dimensions(B)
    assert p == q
    C = matrice_nulle(n,r)
    for i in range(n):
        for j in range(r):
            for k in range(p):
                C[i][j] = C[i][j]  + A[i][k]*B[k][j]
    return C

## Exponentiation 

def exponaif(A,n):
    P = identite(len(A))
    for k in range(n):
        P = produit_matrice(A,P)
    return P

import numpy
A = [[0,1], [1,1]]

exponaif(A,46)
"""[[1134903170, 1836311903], [1836311903, 2971215073]]"""

# utilisation de la fonction matrix_power de la librairie numpy.linalg  
B =  numpy.linalg.matrix_power(A,46)
"""array([[ 1134903170,  1836311903],
       [ 1836311903, -1323752223]])"""
# Les coefficients de B sont des entiers codés sur 32 bits
""">>> type(B[0,0])
<class 'numpy.int32'>
"""
# Le plus grand entier relatif représentable sur 32 bits est 2^31 -1 .
# Or 2971215073 > 2^31 -1 . Il y a dépassement de capacité, cet entier est représenté par 2971215073 -2**32 qui vaut -1323752223


## Exercice: exponentiation rapide

# exponentiation rapide en iteratif

def exporap(x,n):
    e = n # exposant 
    a = x # nombre à exponentier
    p = 1 # produit
    while e != 0:
        if e%2 == 1:
            e = e - 1
            p = a*p
        e = e//2
        a = a*a
    return p


def exporap_matrice(X,n):
    e = n # exposant 
    A = X # matrice à exponentier
    P = identite(len(X)) # produit
    while e != 0:
        if e%2 == 1:
            e = e - 1
            P = produit_matrice(A,P)
        e = e//2
        A = produit_matrice(A,A)
    return P

# complexité logarithmique


## Exercice: nombre de Fibonacci




def fibo_mat(n):
    A = [[0,1], [1,1]]
    return exporap_matrice(A,n)[0][1]


# algo classique de complexité linéaire

def fibo(n):
    if n == 0 or n == 1:
        return n
    f_1 = 0
    f_2 = 1
    for i in range(0,n-1): # n-1 itérations
        temp = f_1 + f_2
        f_1 = f_2
        f_2 = temp
    return(temp)

# Chronométrage et comparaison entre fibo et fibo_mat

from time import time

indices = [10**k for k in range(4,6)]

for n in indices:
    t0 = time()
    fibo_mat(n)
    t1 =time()
    print(t1-t0)
# 0.07 pour  10**5
# 0.84 pour 500 000
# 2.48s pour 10**6
# 129 s pour 10**7

for n in indices:
    t0 = time()
    fibo(n)
    t1 =time()
    print(t1-t0)

# 1.64. pour  10**5
# 40s  pour 500 000
# 162 s pour 10**6
# environ 100 fois pour 10**7  plus car complexité quadratique et non linéaire à cause de la croissance des entiers 


t0 = time()
fibo(1000000)
t1 =time()
print(t1-t0)

t0 = time()
fibo_mat(500000)
t1 =time()
print(t1-t0)