[python]Avoir des "float" plus longs Résolu/Fermé

Question

Salut tout le monde,

Voilà, je "joue" sur le site "project euler" et je cherche plus particulièrement à résoudre le problème 26 (il faut peut être être inscrit pour le voir, je ne sais pas...peu importe de toutes façons)

J'essaye donc en python de trouver la périodicité de la représentation décimale d'un nombre rationnel (elle existe toujours mais elle peut être très longue). Hors apparemment python ne "connait" que 16 décimales, ce qui est manifestement insuffisant (1/19 a une période de 18 par exemple, il faut donc au moins plus de 20 décimales pour avoir une idée de sa période et même dans l'idéal 36 pour être sûr...et comme ce n'est pas la plus grande période). 

Ma question donc, quelqu'un connait-il un autre type de donnée qui prendrait plus de place en mémoire et me permettrait d'avoir une quarantaine de décimales?

Merci!

kilian · Answer

Peut être regarder du côté de Numpy:
http://numpy.scipy.org//

Mais je connais pas du tout, c'est juste qu'il y a des types de données particuliers dedans pour des applications scientifiques....

teebo · Answer

Merci,

Je viens de regarder, et en fait non il est pas capable de me donner mieux...

teebo · Answer

Bon j'ai trafiqué autrement, ce site http://pagesperso-orange.fr/jean-paul.davalan/arit/per/fractions.html?t=1%2F101 m'a bien aidé pour comprendre les mécanismes, et avec quelques test sur leur algo j'ai trouvé ma réponse

kilian · Answer

Et euh... c'est pas possible d'émuler avec des entiers par hazard?
Parce que python supporte des nombres entiers extraordinairement grands....

Après je te dis ça, je suis une quiche en math hein? Mais je suppose que c'est possible.

Melnofil · Answer

Sinon, je te propose une technique de résolution utilisant les entiers long au lieu des nombres flottant : 

>>> (10**1) % 7 
3 
>>> (10**2) % 7 
2 
>>> (10**3) % 7 
6 
>>> (10**4) % 7 
4 
>>> (10**5) % 7 
5 
>>> (10**6) % 7 
1 
# Le résultat est égal au numérateur (de la fraction 1 / 7), ce qui permet de déduire que cette fraction est périodique sur 6 chiffres et que l'on peut retrouver ainsi : 
>>> (10**6 - 1) / 7 
142857 

D'où : 1/7 = 0.(142857) 


>>> (10**1) % 8 
2 
>>> (10**2) % 8 
4 
>>> (10**3) % 8 
0 
# Le résultat de zéro nous permet de déduire que la fraction (1 / 8) n'est pas périodique et qu'il y a 3 chiffres après la virgule que l'on peut retrouver ainsi : 
>>> 10**3 / 8 
125 

D'où 1/8 = 0.125 

Je te laisse réfléchir au pourquoi et comment cette astuce fonctionne, ainsi qu'a l'algorithme implémentant cette solution sans utiliser les nombres flottants ;-)



ÉDIT : J'ai testé mon algorithme, le code tient en 24 lignes simples (comprendre : sans tricher en cumulant des lignes entre elles ;-) et sachant que je n'ai cherché à optimiser le code). Le site Euler m'a annoncé que j'ai trouvé la bonne solution (du premier coup, hourra !).

Je rajoute au passage le cas qui m'a paru le plus retords dans les premiers nombres... le 28 (si vous comprenez celui-là, tous les autres cas seront triviaux) :

>>> (10**1)%28
10
>>> (10**2)%28
16
>>> (10**3)%28
20
>>> (10**4)%28
4
>>> (10**5)%28
12
>>> (10**6)%28
8
>>> (10**7)%28
24
>>> (10**8)%28
16
# On stoppe ici, car le résultat 16 a déjà été obtenu en position 2, j'en déduis que la fraction (1/28) est périodique à partir de 8 chiffres après la virgule, mais que les 2 premiers chiffres ne font pas parti de la récursion. Donc 8-2=6 chiffres font parti de la récursion. Les chiffres peuvent être obtenus ainsi :
>>> 10**8 / 28
3571428
# Remarquez l'ajout d'un zéro initial, car je dois obtenir 8 chiffres et pas 7 !

D'où 1/28 = 0.03(571428)


Par ailleurs, pour ceux qui utilisent un autre langage de programmation ne possédant pas les entiers "illimités", sachez qu'il est possible de calculer les opérations "(10**X)%Y" sans dépasser 31bits.

[python]Avoir des "float" plus longs

5 réponses

Discussions similaires