# Changer ici par votre Prenom Nom:
prenom = "Joseph" # à remplacer
nom = "Salmon" # à remplacer
extension = ".ipynb"
tp = "TP2_HMLA310"
filename = "_".join([tp, prenom, nom + extension])
filename = filename.lower()
print(filename)
# utiliser filename pour votre nom de TP
Le petit théorème de Fermat est un résultat connu de la théorie des nombres. Illustrons le dans cet exercice numériquement. Son énoncé est le suivant:
Soit $p$ un nombre premier et $a$ un entier non divisible par $p$ alors $a^{p−1} - 1 \equiv 0 [p]$.
a) Ecrire une fonction nommée 'fermat' qui prend en entrée $a$ et $p$, et qui renvoie $a^{p−1} \textrm{ mod } p$
b) Montrez que ce résultat est vrai pour $p = 13$ et $a = 16$. On testera l'égalité avec le symbole '==' et la fonction fermat.
c) Créer une liste nommée 'prems', contenant les 7 premiers nombre premiers.
d) Tester que le théorème est vrai pour les 7 premiers nombres premiers et pour tous les nombres $a$ plus petit que 100 satisfaisant la contrainte $a$ non divisibles par $p$. On pourra pour cela utiliser
def fermat(a, p):
return (a ** (p - 1)) % p
a = 6
p = 13
fermat(a, p) == 1
prems = [2, 3, 5, 7, 11, 13, 17]
a = 1
bolos = True
while a < 101 and bolos:
for p in prems:
if a % p != 0:
bolos = fermat(a, p) == 1
a += 1
print(bolos)
Calculez la série $\sum_{j=0}^n r^j$ pour $r = .75$ et $n = 10, 20, 30, 40$. On utilisera deux méthodes :
a) une solution avec une boucle sur une liste
b) une solution avec la fonction sum sur un numpy array.
Enfin comparez votre résultat à celui de la formule $(1 − r^{n+1} )/(1 − r)$
Solution liste:
import numpy as np
n_list = [10, 20, 30, 40]
for n in n_list:
print('cas n = {} :'.format(n))
liste = list(range(n + 1))
somme = 0
r = .75
for j in liste:
somme += r ** j
print("Somme par liste : {}".format(somme))
np_array = np.arange(n + 1)
somme_numpy = np.sum(r ** np_array)
print("Somme par numpy : {}".format(somme_numpy))
print("Somme formule de Gauss: {}".format((1 - r ** (n + 1)) / (1 - r)))
print('\n')
%history
Créer les vecteurs et matrices suivants sans renter les valeurs une à une:
a) array([1., 1., 1.]) (dont la taille est (3,) )
b) array([[1., 1., 1.]]) (dont la taille est (3,1) )
c) array([1, 2, 3])
d) array([ 2, 1, 0, -1, -2])
e) array([1, 2, 3, 1, 2, 3])
f) array([[1, 2, 3], [4, 5, 6]])
g) array([[0., 0., 0., 0., 0., 0.], [1., 0., 0., 0., 0., 0.], [0., 1., 0., 0., 0., 0.], [0., 0., 1., 0., 0., 0.], [0., 0., 0., 1., 0., 0.], [0., 0., 0., 0., 1., 0.]])
np.ones(3)
np.ones((1, 3))
np.arange(1, 4)
np.arange(2, -3, -1)
np.hstack((np.arange(1, 4), np.arange(1, 4)))
np.repeat(np.arange(1, 4), 2, axis=0)
np.tile(np.arange(1, 4),2)
np.reshape(np.arange(1, 7, 1), newshape=(2, 3))
np.diag(np.ones(5), k=-1)
On se propose de faire l'étude de cette suite et de comparer l'efficacité en mémoire et en temps, en passant par des boucles et des listes, ou bien par un modèle matriciel.
def fibonacci_naive(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
# pip install memory_profiler # if needed.
%load_ext memory_profiler
n = 35
%timeit fibonacci_naive(n)
3.01 s ± 75.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# %memit fibonacci_naive(n)
peak memory: 58.82 MiB, increment: 0.00 MiB
Conclusion: Cette fonction est lente, car on doit recalculer sans cesse des termes qui l'on déjà été... Par exemple pour calculer $F_{35}$ on calcule $F_{34}$ et $F_{33}$, mais le calcul de $F_{34}$ nécessite à son tour le calcul de $F_{33}$ alors que celui-ci a déjà été calculé: cette redondance des calculs s'accumulent avec l'augmentation de $n$.
def fibonacci_list(n):
l = [0, 1]
if n == 0:
return l[0]
elif n == 1:
return l
a = 0
b = 1
for i in range(0, n - 1):
b = a + b
a = b - a
l.append(b)
return l
fibonacci_list(n)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465]
%timeit fibonacci_list(n)
# %memit fibonacci_list(n)
def fibonacci_variables(n):
if n == 0:
return 0
elif n == 1:
return 1
a = 0
b = 1
for i in range(0, n - 1):
b = a + b
a = b - a
return b
print(fibonacci_variables(n))
print(fibonacci_naive(n))
9227465 9227465
%timeit fibonacci_variables(n)
2.12 µs ± 62.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
# %memit fibonacci_variables(n)
from functools import lru_cache
@lru_cache()
def fibonacci_cache(n):
if n < 2:
return n
return fibonacci_cache(n - 1) + fibonacci_cache(n - 2)
%timeit fibonacci_cache(n)
63.4 ns ± 3.8 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
# %memit fibonacci_cache(35)
import numpy as np
def fibonacci_numpy(n):
F = [[1, 1], [1, 0]]
return np.linalg.matrix_power(F, n)[0, 1]
%timeit fibonacci_numpy(n)
14.1 µs ± 244 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
# %memit fibonacci_numpy(n)