Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente | |||
racine_entiere [2015/03/14 09:36] tyrtamos |
racine_entiere [2015/03/15 09:31] (Version actuelle) 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' | + | |
===== Problématique ===== | ===== Problématique ===== | ||
Ligne 16: | Ligne 14: | ||
* [[http:// | * [[http:// | ||
+ | * [[http:// | ||
* [[http:// | * [[http:// | ||
* etc... | * etc... | ||
Ligne 42: | Ligne 41: | ||
raise ValueError(" | raise ValueError(" | ||
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) | ||
- | rac1, i = n, 1 | + | rac1, i = n, 0 # i = compteur du nb de positions binaires utilisées |
while rac1 != 0: | while rac1 != 0: | ||
rac1 >>= 1 | rac1 >>= 1 | ||
- | i += 1 # i = compteur du nb de positions binaires utilisées | + | i += 1 |
rac1 = 1 << (i >> 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 | + | delta = n |
while True: | while True: | ||
rac2 = (rac1 + n // rac1) >> 1 | rac2 = (rac1 + n // rac1) >> 1 | ||
- | if rac2 >= rac1 and delta <= 1: | + | if delta <= 1 and rac2 >= rac1: |
return rac1 | return rac1 | ||
delta = abs(rac2 - rac1) # on garde pour la prochaine boucle | delta = abs(rac2 - rac1) # on garde pour la prochaine boucle | ||
Ligne 84: | Ligne 83: | ||
<code python> | <code python> | ||
""" | """ | ||
- | | + | |
""" | """ | ||
Ligne 94: | Ligne 93: | ||
raise ValueError(" | raise ValueError(" | ||
else: | else: | ||
+ | # le calcul sera fait avec n>0 et on corrigera à la fin | ||
signe, n = -1, abs(n) | signe, n = -1, abs(n) | ||
else: | else: | ||
Ligne 99: | Ligne 99: | ||
# 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 = n, 0 | + | rac1, i = n, 0 # i = compteur du nb de positions binaires utilisées |
- | while rac1 > 0: | + | while rac1 != 0: |
rac1 >>= 1 | rac1 >>= 1 | ||
- | i += 1 # i = compteur du nb de positions binaires utilisées | + | i += 1 |
rac1 = 1 << (i // k) | rac1 = 1 << (i // k) | ||
# calcul de la racine en partant de la racine approchée rac1 | # calcul de la racine en partant de la racine approchée rac1 | ||
- | | + | |
- | | + | |
while True: | while True: | ||
rac2 = (km1 * rac1 + n // (rac1 ** km1)) // k | rac2 = (km1 * rac1 + n // (rac1 ** km1)) // k | ||
- | if rac2 >= rac1 and delta <= 1: | + | if delta <= 1 and rac2 >= rac1: |
- | | + | |
+ | return rac1 | ||
+ | return -rac1 | ||
delta = abs(rac2 - rac1) # on garde pour la prochaine boucle | delta = abs(rac2 - rac1) # on garde pour la prochaine boucle | ||
rac1 = rac2 | rac1 = rac2 | ||
Ligne 189: | Ligne 191: | ||
</ | </ | ||
- | \\ | ||
- | Bien entendu, si par exemple vous prenez la racine entière 5ème ci-dessus et que vous calculiez sa puissance 5, vous ne retrouvez pas le nombre initial n: parce qu'on n'a pas les décimales, et que le nombre n n' | + | ===== Vérification que la racine entière obtenue est la bonne ===== |
+ | |||
+ | Bien entendu, si par exemple vous prenez la racine entière 5ème ci-dessus et que vous calculiez sa puissance 5, vous ne retrouvez pas exactement | ||
- | <code python>n = 157046427221351911140**5 # ce qui donne 95530115674158268117011886873321123603202109596146187950666441653568720214191812971191238942582400000 | + | En fait, la condition qui vérifie que la racine kième de n obtenue est correcte est la suivante: |
- | print(lrackd(n,5)) | + | |
- | 157046427221351911140 | + | <code python>if n < 0: |
+ | reussite | ||
+ | else: | ||
+ | reussite = rac ** k <= n < (rac + 1) ** k | ||
</ | </ | ||
- | On peut vérifier aussi que si le nombre n est un entier " | + | On peut fabriquer une petite fonction qui vérifie |
- | <code python>n = 9 | + | <code python>def okrac(rac, |
- | print(lrackd(n)) | + | """ |
- | 3 | + | n et rac peuvent être positifs ou négatifs |
+ | k est toujours positif | ||
+ | """ | ||
+ | if n < 0 and k % 2 == 0: | ||
+ | # n négatif pour un exposant pair: erreur | ||
+ | return False | ||
+ | |||
+ | if (n > 0 and rac < 0) or (n < 0 and rac > 0): | ||
+ | # n et rac ne sont pas de même signe: erreur | ||
+ | return False | ||
+ | |||
+ | # vérif que rac est bien la racine kième de n | ||
+ | if n < 0: | ||
+ | return rac ** k >= n > (rac - 1) ** k | ||
+ | | ||
+ | return rac ** k <= n < (rac + 1) ** k | ||
</ | </ | ||
- | \\ | + | ===== Exemples d' |
Conséquence amusante: peut-on calculer avec ça la racine carrée normale de 2 ? Bien sûr! Il suffit d' | Conséquence amusante: peut-on calculer avec ça la racine carrée normale de 2 ? Bien sûr! Il suffit d' | ||
Ligne 220: | Ligne 242: | ||
</ | </ | ||
- | On a bien trouvé tous les chiffres de la fonction normale, plus d' | + | On a bien trouvé tous les chiffres de la fonction normale, plus d' |
Vous voulez plus de chiffres significatifs? | Vous voulez plus de chiffres significatifs? | ||
- | <code python> | + | <code python>n = 2*10**10000 |
- | n = 2*10**10000 | + | print(lrac2(n)) |
- | print(lrack(n)) | + | |
</ | </ | ||
Ligne 283: | Ligne 304: | ||
</ | </ | ||
- | \\ | + | On peut, bien sûr, vérifier |
- | 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é | + | |
- | * 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. | + | |
- | + | ||
- | 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 | + | |
- | </ | + | |
\\ | \\ | ||
Ligne 315: | Ligne 321: | ||
résultat obtenu en moins d' | résultat obtenu en moins d' | ||
- | |||
- | \\ | ||
- | Voilà comment, pour des valeurs n et k entières quelconques (et n éventuellement signé si k est pair), on peut vérifier que la fonction r=lrack(n, k) donne un résultat correct: | ||
- | |||
- | <code python> | ||
- | """ | ||
- | """ | ||
- | if k % 2 == 0: | ||
- | if r < 0 or k < 0: | ||
- | return False | ||
- | else: | ||
- | if (n < 0 and r > 0) or (n > 0 and r < 0): | ||
- | return False | ||
- | r, n = abs(r), abs(n) | ||
- | if r ** k <= n and (r + 1) ** k > n: | ||
- | return True | ||
- | else: | ||
- | return False | ||
- | </ | ||
\\ | \\ | ||
Ligne 355: | Ligne 342: | ||
<code python> | <code python> | ||
- | for x in xrange(1,21): | + | for n in range(1,21): |
- | print(" | + | print(" |
1 1.00000000000000000000000000000000000000000000000000 | 1 1.00000000000000000000000000000000000000000000000000 | ||
Ligne 383: | Ligne 370: | ||
<code python> | <code python> | ||
- | for x in xrange(1,21): | + | for n in range(1,21): |
- | print(" | + | print(" |
1 1.00000000000000000000000000000000000000000000000000 | 1 1.00000000000000000000000000000000000000000000000000 | ||
Ligne 411: | Ligne 398: | ||
<code python> | <code python> | ||
- | for x in xrange(1,21): | + | for n in range(1,21): |
- | print(" | + | print(" |
1 1.00000000000000000000000000000000000000000000000000 | 1 1.00000000000000000000000000000000000000000000000000 | ||
Ligne 437: | Ligne 424: | ||
\\ | \\ | ||
- | Revenons maintenant à la fonction initiale lrack(). | + | Pour vérifier que les puissances parfaites trouvent bien leur solutions (c'est à dire que si %%n=rac**k%% au départ, on retrouve bien rac par lrack(n, |
- | + | ||
- | Si vous voulez vérifier que votre fonction donne bien le bon résultat, vous pouvez procéder comme suit: | + | |
- | + | ||
- | <code python> | + | |
- | while True: | + | |
- | k = randint(2, 20) | + | |
- | if k % 2 == 0: | + | |
- | s = 1 | + | |
- | else: | + | |
- | s = [-1, 1][randint(0, | + | |
- | e = 10 ** randint(1, 50) | + | |
- | n = s * randint(e, e * 10 - 1) | + | |
- | rac = lrack(n, k) | + | |
- | print(" | + | |
- | if not okrac(rac, n, k): | + | |
- | print(" | + | |
- | raise ValueError | + | |
- | </ | + | |
- | + | ||
- | Grâce au module random, ce code tire au hasard: | + | |
- | * le niveau de la racine k (2=carré, 3=cubique, etc...) de 2 à 20 | + | |
- | * le signe positif ou négatif (positif seul si n est pair) | + | |
- | * le nombre de chiffres du nombre n dont on va calculer la racine | + | |
- | * le nombre n lui-même avec le bon nombre de chiffres | + | |
- | + | ||
- | Ensuite, le calcul de la racine est faite, ainsi que le test de validité okrac(). | + | |
- | + | ||
- | Le calcul boucle indéfiniment, | + | |
- | + | ||
- | Voilà un exemple de sortie: | + | |
- | + | ||
- | < | + | |
- | n= -80962953866247211039394800262871750 k= 17 => racine= -113 | + | |
- | n= 4891253697941566905308674563740 k= 4 => racine= 47027841 | + | |
- | n= 48320171439282366839527268276313841988 k= 10 => racine= 5866 | + | |
- | n= 28779456330615571989554676685839 k= 11 => racine= 724 | + | |
- | n= 6825613759962 k= 15 => racine= 7 | + | |
- | n= 715795763040540816210823765134136685 k= 12 => racine= 972 | + | |
- | n= 1451040758 k= 20 => racine= 2 | + | |
- | n= 90553084163348580 k= 14 => racine= 16 | + | |
- | n= -97240360265942765704021091296670265 k= 7 => racine= -99601 | + | |
- | n= 6615729409 k= 11 => racine= 7 | + | |
- | n= 81819 k= 16 => racine= 2 | + | |
- | n= 393297733166051962579054 k= 2 => racine= 627134541518 | + | |
- | n= -63604085714835362844892630682339055540675047 k= 7 => racine= -1809842 | + | |
- | n= -338002881675985173683343 k= 15 => racine= -37 | + | |
- | n= 15040819 k= 14 => racine= 3 | + | |
- | n= 4208005 k= 4 => racine= 45 | + | |
- | n= 36225492918 k= 20 => racine= 3 | + | |
- | n= 31334006275758284427290851387 k= 18 => racine= 38 | + | |
- | n= 958616917940483554478054936796488650914 k= 17 => racine= 196 | + | |
- | n= 262776679529 k= 15 => racine= 5 | + | |
- | </ | + | |
- | + | ||
- | \\ | + | |
- | Pour vérifier que les puissances parfaites trouvent bien leur solutions (c'est à dire que si %%x=r**n%% au départ, on retrouve bien r par lrack(n, | + | |
<code python> | <code python> | ||
- | r = 7 | + | rac = 7 |
k = 2 | k = 2 | ||
while True: | while True: | ||
- | n = r**k | + | n = rac**k |
- | if lrack(n, | + | if lrack(n, k)==rac: |
print(r, k, n) | print(r, k, n) | ||
else: | else: |