Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Prochaine révision Les deux révisions suivantes | ||
racine_entiere [2015/03/09 14:15] tyrtamos |
racine_entiere [2015/03/10 11:32] tyrtamos |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
====== Calcul de la racine kième entière d'un nombre entier de longueur quelconque ====== | ====== Calcul de la racine kième entière d'un nombre entier de longueur quelconque ====== | ||
- | **En cours de modification!** | + | **En cours de modification** |
[modifié en mars 2015: passage à Python 3 + généralisation de la méthode de Héron d' | [modifié en mars 2015: passage à Python 3 + généralisation de la méthode de Héron d' | ||
Ligne 30: | Ligne 30: | ||
C'est tout de même une méthode qui a environ 2000 ans, et qui est très efficace! Chapeau Héron! | C'est tout de même une méthode qui a environ 2000 ans, et qui est très efficace! Chapeau Héron! | ||
- | Voilà le code proposé | + | Voilà le code proposé: |
<code python> | <code python> | ||
Ligne 45: | Ligne 45: | ||
# trouve une valeur approchée de la racine (important pour les grds nb) | # trouve une valeur approchée de la racine (important pour les grds nb) | ||
- | rac1, i = 1, 1 | + | rac1, i = n, 1 |
- | while i <= n: | + | while rac1 != 0: |
- | rac1 <<= 1 | + | rac1 >>= 1 |
- | i <<= 2 | + | i += 1 # i = compteur du nb de positions binaires utilisées |
- | rac1 >>= 1 | + | rac1 = 1 << (i >> 1) |
# calcule la racine en partant de la racine approchée rac1 | # calcule la racine en partant de la racine approchée rac1 | ||
+ | delta = n - 1 | ||
while True: | while True: | ||
rac2 = (rac1 + n // rac1) >> 1 | rac2 = (rac1 + n // rac1) >> 1 | ||
- | if rac2 == rac1: | + | if rac2 >= rac1 and delta <= 1: |
- | return rac2 | + | return |
+ | delta = abs(rac2 - rac1) # on garde pour la prochaine boucle | ||
rac1 = rac2 | rac1 = rac2 | ||
</ | </ | ||
Ligne 84: | Ligne 86: | ||
| | ||
""" | """ | ||
+ | |||
# initialisation du signe et traitement des cas particuliers | # initialisation du signe et traitement des cas particuliers | ||
signe = +1 | signe = +1 | ||
Ligne 89: | Ligne 92: | ||
if n < 0: | if n < 0: | ||
if k % 2 == 0: | if k % 2 == 0: | ||
- | raise ValueError(" | + | raise ValueError(" |
else: | else: | ||
signe, n = -1, abs(n) | signe, n = -1, abs(n) | ||
else: | else: | ||
- | return n # n = 0 ou 1 | + | return n # ici n = 0 ou 1 |
# trouve une valeur approchée de la racine (important pour les grds nb) | # trouve une valeur approchée de la racine (important pour les grds nb) | ||
- | | + | |
- | while x < n: | + | while rac1 > 0: |
- | | + | |
- | i += 1 | + | i += 1 # i = compteur du nb de positions binaires utilisées |
rac1 = 1 << (i // k) | rac1 = 1 << (i // k) | ||
Ligne 109: | Ligne 112: | ||
if rac2 >= rac1 and delta <= 1: | if rac2 >= rac1 and delta <= 1: | ||
return signe * rac1 | return signe * rac1 | ||
- | delta = abs(rac2 - rac1) | + | delta = abs(rac2 - rac1) # on garde pour la prochaine boucle |
rac1 = rac2 | rac1 = rac2 | ||
</ | </ | ||
Ligne 139: | Ligne 142: | ||
<code python> | <code python> | ||
- | """ | + | """ |
+ | | ||
+ | | ||
# initialisation du signe et traitement des cas particuliers | # initialisation du signe et traitement des cas particuliers | ||
signe = +1 | signe = +1 | ||
Ligne 145: | Ligne 151: | ||
if n < 0: | if n < 0: | ||
if k % 2 == 0: | if k % 2 == 0: | ||
- | raise ValueError(" | + | raise ValueError(" |
else: | else: | ||
signe, n = -1, abs(n) | signe, n = -1, abs(n) | ||
else: | else: | ||
- | return n # n = 0 ou 1 | + | return n # ici n = 0 ou 1 |
# trouve rac1 et rac2 qui encadrent de plus près la valeur cherchée de la racine | # trouve rac1 et rac2 qui encadrent de plus près la valeur cherchée de la racine | ||
Ligne 159: | Ligne 165: | ||
rac1 >>= 1 | rac1 >>= 1 | ||
- | # calcule par dichotomie la racine kième de n qui est entre rac1 et rac2 | + | # calcule par dichotomie la racine |
while rac1 != rac2: | while rac1 != rac2: | ||
r = (rac1 + rac2) >> 1 | r = (rac1 + rac2) >> 1 | ||
Ligne 280: | Ligne 286: | ||
Mais voilà: comment être sûr que tous mes chiffres sont bons? Je n'ai pas trouvé sur le web de valeurs de racine de 2 qui dépassaient les 100 chiffres. Pourtant, c'est simple, et j'ai déjà donné la solution plus haut: | Mais voilà: comment être sûr que tous mes chiffres sont bons? Je n'ai pas trouvé sur le web de valeurs de racine de 2 qui dépassaient les 100 chiffres. Pourtant, c'est simple, et j'ai déjà donné la solution plus haut: | ||
* r*r donne bien un résultat légèrement inférieur à 2: 10001 chiffres dont les 5000 premiers sont 1.9999....998 (avec n = carré parfait, r*r serait exactement égal à n) | * r*r donne bien un résultat légèrement inférieur à 2: 10001 chiffres dont les 5000 premiers sont 1.9999....998 (avec n = carré parfait, r*r serait exactement égal à n) | ||
- | * (r+1)*(r+1) donne bien un résultat légèrement supérieur à 2: 10001 chiffres dont les 5000 premiers sont 2.000...000 suivis d'une liste de chiffres non nuls | + | * (r+1)*(r+1) donne bien un résultat légèrement supérieur à 2: 10001 chiffres dont les 5000 premiers sont 2.000...000 suivis d'une liste de chiffres non nuls. |
+ | |||
+ | En résumé, la racine carrée entière de n est correcte quand la condition suivante est satisfaite: | ||
+ | |||
+ | <code python> | ||
+ | r*r <= n < (r+1)*(r+1) | ||
+ | </ | ||
+ | |||
+ | De même pour la racine kième: | ||
+ | |||
+ | <code python> | ||
+ | r**k <= n < (r+1)**k | ||
+ | </ | ||
\\ | \\ |