Écrire une fonction Python,
nommée encadre_racine()
, qui respecte la spécification
suivante :
Paramètres | un entier naturel n |
---|---|
Valeur renvoyée | un couple de valeurs encadrant $\sqrt{2}$, encadrement d'amplitude inférieure ou égal à $10^{-n}$ |
On procèdera par balayage.
- Une solution
- Une amélioration
- Une autre solution
def encadre_racine(n, depart):
"""
encadrement de √2 par balayage
amplitude <= 10^(-n)
"""
x = depart
while x*x <= 2:
x = x + 10**(-n)
return (x-10**(-n), x)
>>> encadre_racine(3, 1) (1.4139999999999544, 1.4149999999999543)
Le temps d'exécution de encadre_racine(9, 1)
par exemple montre que notre première
fonction seule est peu efficace.
On cherche donc à l'améliorer en faisant moins de pas.
Pour cela :
- Il suffit d'encadrer à l'unité : $a_0 \leqslant \sqrt{2} \leqslant b_0$.
- Puis partir de $a_0$ pour obtenir un encadrement d'ordre ≤ $10^{-1}$ : $a_1 \leqslant \sqrt{2} \leqslant b_1$.
- On part ensuite de $a_1$ pour obtenir un encadrement d'ordre ≤ $10^{-2}$, etc...
def encadre_racine(n, depart):
"""
encadrement de √2 par balayage
amplitude <= 10^(-n)
"""
x = depart
while x*x <= 2:
x = x + 10**(-n)
return (x-10**(-n), x)
def encadre_racine2(n):
x = 1
for k in range(0,n+1):
x, y = encadre_racine(k, x)
return x, y
>>> encadre_racine2(9) (1.4142135619999998, 1.414213563)
Remarque
Avec :
>>> encadre_racine(9, 1) (1.414213562272181, 1.414213563272181)
L'encadrement obtenu n'est donc pas tout à fait le même bien que l'on s'appuie sur la même fonction. On retrouve là le problème des arrondis lorsqu'on calcule avec des flottants. Ce qui nous mène à la solution de l'onglet suivant dans laquelle on essaie d'éviter les flottants.
Dans cette solution, on essaie d'éviter le cumul d'erreur dû aux calculs sur flottants. On travaille pour cela sur les entiers.
def encadre_racine_entier(n, depart):
"""
encadrement de √2 par balayage
amplitude <= 10^(-n)
"""
y = depart * 10**n
while y*y <= 2*10**(2*n):
y = y + 1
return ((y-1)/10**n, y/10**n)
>>> encadre_racine_entier(4, 1) (1.4142, 1.4143)
On est bien sûr confronté au même problème de lenteur.
Voici une proposition d'accélération :
def utilitaire_encadre_racine_entier(n, depart):
y = depart*10
while y*y <= 2*10**(2*n):
y = y + 1
return (y-1, y)
def accelere_encadre(n):
x = 1
for k in range(1,n+1):
x, y = utilitaire_encadre_racine_entier(k, x)
return x/10**n, y/10**n
>>> accelere_encadre(10) (1.4142135623, 1.4142135624)