Warning: Undefined array key "DOKU_PREFS" in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/common.php on line 2082
racine_entiere [Les recettes Python de Tyrtamos]

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Piste:
racine_entiere

Warning: Undefined array key -1 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1458

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

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'Alexandrie + refonte de la page] 
- +
-[modifié en mars 2015: passage à Python 3 + généralisation de la méthode de Héron d'Alexandrie] +
  
 ===== Problématique ===== ===== Problématique =====
Ligne 16: Ligne 14:
  
   * [[http://fr.wikipedia.org/wiki/Racine_carr%C3%A9e_enti%C3%A8re]]   * [[http://fr.wikipedia.org/wiki/Racine_carr%C3%A9e_enti%C3%A8re]]
 +  * [[http://fr.wikipedia.org/wiki/Algorithme_de_calcul_de_la_racine_n-i%C3%A8me]]
   * [[http://fr.wikipedia.org/wiki/Racine_carr%C3%A9e#Les_racines_carr.C3.A9es.2C_approximations_enti.C3.A8res]]   * [[http://fr.wikipedia.org/wiki/Racine_carr%C3%A9e#Les_racines_carr.C3.A9es.2C_approximations_enti.C3.A8res]]
   * etc...   * etc...
Ligne 42: Ligne 41:
             raise ValueError("Erreur: racine carrée d'un nb négatif")             raise ValueError("Erreur: racine carrée d'un nb négatif")
         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>def lrack(n, k=2): <code python>def lrack(n, k=2):
     """Racine kième entière d'un nb entier n de taille quelconque     """Racine kième entière d'un nb entier n de taille quelconque
-       Génère une exception  "ValueError" si n est négatif et k paire.+       Génère une exception "ValueError" si n est négatif et k paire.
     """     """
  
Ligne 94: Ligne 93:
                 raise ValueError("Erreur: racine paire d'un nombre négatif")                 raise ValueError("Erreur: racine paire d'un nombre négatif")
             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
-    delta = n - 1 +    km1 = k - 1  # précalcul pour gagner du temps 
-    km1 = k - 1+    delta = n
     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 signe * rac1+            if signe > 0: 
 +                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:
 </code> </code>
  
-\\ 
  
-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'était pas une puissance 5ème exacte. Par contre, vous pouvez vérifier cela:+===== 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 le nombre initial n, parce qu'on n'a pas les décimales, et que le nombre n n'était pas une puissance 5ème exacte. 
  
-<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 = rac ** k >= n > (rac - 1) ** k 
 +else: 
 +    reussite = rac ** k <= n < (rac + 1) ** k
 </code> </code>
  
-On peut vérifier aussi que si le nombre n est un entier "normal" (pas long), on trouve la bonne valeur:+On peut fabriquer une petite fonction qui vérifie que rac est bien la racine kième de n:
  
-<code python>n = 9 +<code python>def okrac(rac, n, k=2): 
-print(lrackd(n))  +    """dit si rac est la racine entière kième du nombre entier 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 
 +    else: 
 +        return rac ** k <= n < (rac + 1) ** k
 </code> </code>
  
-\\+===== Exemples d'applications ===== 
 Conséquence amusante: peut-on calculer avec ça la racine carrée normale de 2 ? Bien sûr! Il suffit d'ajouter un nombre pair de zéros et d'en retirer la moitié à la fin. Conséquence amusante: peut-on calculer avec ça la racine carrée normale de 2 ? Bien sûr! Il suffit d'ajouter un nombre pair de zéros et d'en retirer la moitié à la fin.
  
Ligne 220: Ligne 242:
 </code> </code>
  
-On a bien trouvé tous les chiffres de la fonction normale, plus d'autres! Comme on a ajouté 50 zéros (exposant forcément pair pour k=2!), il faut bien entendu déplacer la virgule de 25 positions sur la gauche pour la mettre à la bonne place. Mais si vous vous contenter de diviser par 10E25: vous vous retrouvez en nombres flottants normaux et vous perdez les chiffres supplémentaires.+On a bien trouvé tous les chiffres de la fonction normale, plus d'autres! Comme on a ajouté 50 zéros (exposant forcément pair pour k=2!), il faut bien entendu déplacer la virgule de 25 positions sur la gauche pour la mettre à la bonne place. Mais si vous vous contenter de diviser par 10E25: vous vous retrouvez en nombres flottants normaux et vous perdez les chiffres supplémentaires (autrement, utilisez le module decimal).
  
 Vous voulez plus de chiffres significatifs? Facile: voilà la racine de 2 avec 5000 chiffres après la virgule. Vous voulez plus de chiffres significatifs? Facile: voilà la racine de 2 avec 5000 chiffres après la virgule.
  
-<code python> +<code python>n = 2*10**10000 
-n = 2*10**10000 +print(lrac2(n)) 
-print(lrack(n)) +
 </code> </code>
  
Ligne 283: Ligne 304:
 </code> </code>
  
-\\ +On peut, bien sûr, vérifier que le résultat est bon avec la condition de réussite définie 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+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) +
-</code> +
- +
-De même pour la racine kième: +
- +
-<code python> +
-r**k <= n < (r+1)**k +
-</code>+
  
 \\ \\
Ligne 315: Ligne 321:
  
 résultat obtenu en moins d'1/1000 de seconde. résultat obtenu en moins d'1/1000 de seconde.
- 
-\\ 
-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>def okrac(r, n, k=2): 
-    """dit si r est la racine entière kième du nombre entier n  
-    """ 
-    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 
-</code> 
  
 \\ \\
Ligne 355: Ligne 342:
  
 <code python> <code python>
-for x in xrange(1,21): +for n in range(1,21): 
-    print("%2d" % x, frac(x,2,50))+    print("%2d" % n, frac(n,2,50))
  
  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("%2d" % x, frac(x,3,50))+    print("%2d" % n, frac(n,3,50))
  
  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("%2d" % x, frac(x,5,50))+    print("%2d" % n, frac(n,5,50))
  
  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,k)), on peut tester comme suit:
- +
-Si vous voulez vérifier que votre fonction donne bien le bon résultat, vous pouvez procéder comme suit: +
- +
-<code python>from random import randint +
-while True: +
-    k = randint(2, 20) +
-    if k % 2 == 0: +
-        s = 1 +
-    else: +
-        s = [-1, 1][randint(0, 1)] +
-    e = 10 ** randint(1, 50) +
-    n = s * randint(e, e * 10 - 1) +
-    rac = lrack(n, k) +
-    print("n=", n, "k=", k, "=> racine=", rac) +
-    if not okrac(rac, n, k): +
-        print("erreur") +
-        raise ValueError +
-</code> +
- +
-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, et ne s'arrête qu'à la 1ère erreur trouvée (s'il y en a une) ou avec Ctle-C. Vous pouvez donc laisser tourner pendant plusieurs heures, voire plusieurs jours, si nécessaire. +
- +
-Voilà un exemple de sortie: +
- +
-<code>n= 75495734 k= 18 => racine= 2 +
-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 +
-</code>   +
- +
-\\ +
-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,k)), on peut tester comme suit:+
  
 <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,k)==r:+    if lrack(n, k)==rac:
         print(r, k, n)         print(r, k, n)
     else:     else:
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
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki