Outils pour utilisateurs
racine_entiere
Différences
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 22:50] 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** | ||
| [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 28: | 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 43: | 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 82: | Ligne 86: | ||
| | | ||
| """ | """ | ||
| + | |||
| # initialisation du signe et traitement des cas particuliers | # initialisation du signe et traitement des cas particuliers | ||
| signe = +1 | signe = +1 | ||
| Ligne 87: | 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 107: | 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 137: | 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 143: | 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 157: | 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 278: | 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 | ||
| + | </ | ||
| \\ | \\ | ||
racine_entiere.txt · Dernière modification: 2015/03/15 09:31 de tyrtamos
Outils de la page
Sauf mention contraire, le contenu de ce wiki est placé sous les termes de la licence suivante : CC Attribution-Noncommercial-Share Alike 4.0 International
