limite de calcul et suite de fibonacci

Version imprimable

17/01/2016, 20h05
Fenelon St Marie

limite de calcul et suite de fibonacci

Bonsoir tout le monde,

Je suis actuellement en Maths Spe et pour ceux qui connaissent, je dois travailler sur un TIPE (thème scientifique qui change tous les ans). Cette année, le thème étant entre autre "structures et complexité", je me suis intéressé aux différentes façons pour programmer la suite de Fibonacci, étudier la complexité etc.

Sauf que je fais face à un gros problème: les termes de la suite étant assez conséquent , pour n = 1400, on a déjà Fn = 1.7e+292, et python, pour des valeurs supérieures à 10^308 renvoie automatiquement l'infini et s'arrête de calculer.
Y a t-il un moyen pour contourner cette valeur limite? Parce qu'actuellement je ne peux pas calculer de terme supérieur à n =1476

Merci d'avance!
17/01/2016, 20h23
wiztricks

Salut,

Citation:

Envoyé par Fenelon St Marie

Sauf que je fais face à un gros problème: les termes de la suite étant assez conséquent , pour n = 1400, on a déjà Fn = 1.7e+292, et python, pour des valeurs supérieures à 10^308 renvoie automatiquement l'infini et s'arrête de calculer.

Postez du code et précisez la version de Python utilisée. Comme Python travaille avec des bignum (et que fibonacci c'est sur les entiers) vous ne devriez pas avoir de soucis sinon d'attendre que çà le fasse.

- W

1 pièce(s) jointe(s)

Merci pour votre réponse.
Je fais fonctionner Spyder avec la version 2.7 de python.
Voici le code de la version Itérative classique qui me renvoie directement "inf" et arrête le programme quand je dépasse n=1476. J
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 import time def Fibo_brutalI(n): u,v = 0.,1. for i in range(2,n+1): u,v = v,u+v return v tps1 = time.clock() print(Fibo_brutalI(1477)) tps2 = time.clock() print(tps2 - tps1)
Désolé pour la mise en forme, j'ai encore un peu de mal avec le site.

17/01/2016, 23h42
marco056

Enlève les points après le 0 et le 1.

PS : quelle drôle d'idée de travailler en python2.7 ! :roll:

Bonjour,

Python a des possibilités de calcul étonnantes! Avec la correction proposée par marco056, le calcul se fait entièrement en entier.

A titre d'exemple, voilà le résultat obtenu en 1,3 sec. pour n=100000 (cent mille): un nombre de 20899 chiffres dont voilà le début et la fin:

Code:

1
2
3
4
5
6
7
8
9
10
11
25974069347221724166155034021275915414880485386517696584724770703952534543511273
68626555677283671674475463758722307443211163839947387509103096569738218830449305
22876385313349213530267927895670105127657827163560807305053220024323311438398651
61378272381247774537783372999162146340500546698603908627509966393664092118901252
71960172105060300350586894028558103675117658251368377438684936413457338834365158
...
07243970997644514679099338144899464460978095773195360493873495002686056455569322
42296918156302939224876064708734311663842054424896287602136502469918930401125131
03835085621908060270866604873585849001704200923929789193938125116798421788115209
25913043557232163566089560351438388393901895316627435560997001569978028923636234
9895374653428746875

18/01/2016, 20h24
marco056

Citation:

Envoyé par tyrtamos

Bonjour,

Python a des possibilités de calcul étonnantes! Avec la correction proposée par marco056, le calcul se fait entièrement en entier.

A titre d'exemple, voilà le résultat obtenu en 1,3 sec. pour n=100000 (cent mille): un nombre de 20899 chiffres dont voilà le début et la fin:

Tu as quoi comme bécane ? :mouarf:
Chez moi, c'est 0.09772499999999695 secondes avec 100000... :zoubi:
18/01/2016, 20h52
tyrtamos

Bonjour,

Citation:

Envoyé par marco056

Tu as quoi comme bécane ? :mouarf:
Chez moi, c'est 0.09772499999999695 secondes avec 100000... :zoubi:

J'ai un PC assez puissant (core i7, ram:16GO), et le temps de calcul me semble bon dans tout ce que je fais.

Mais il y a une différence dans la mesure des temps de calcul entre les différents OS (time.clock() et time.time()).

Pour l'instant, je suis sous Windows et toi?
18/01/2016, 20h55
marco056

Citation:

Envoyé par tyrtamos

Bonjour,

J'ai un PC assez puissant (core i7, ram:16GO), et le temps de calcul me semble bon dans tout ce que je fais.

Mais il y a une différence dans la mesure des temps de calcul entre les différents OS (time.clock() et time.time()).

Pour l'instant, je suis sous Windows et toi?

Tu as raison, je suis sous linux et le comportement est différent (cpu, je crois, pour moi).
C'était une blague, tu avais le droit d'avoir un vieux pc sous la main...
18/01/2016, 21h17
tyrtamos

Citation:

Envoyé par marco056

tu avais le droit d'avoir un vieux pc sous la main...

J'ai aussi un vieux PC d'une dizaine d'année (ram:500Mo) qui marche très bien sous Linux Mint v17! :D
20/01/2016, 10h44
Fenelon St Marie

Merci beaucoup pour toutes vos réponses! Le programme marche effectivement sans soucis pour des très grosses valeurs de n. Pour n = 100 000, j'obtient le résultat en 3.28s avec la fonction time.clock.
Ca commence à faire une bonne différence avec la machine de marco056, pourtant j'ai un core i3 avec 4G de RAM sous windows et je trouvais ça pas trop mal pour faire du python :calim2:

J'ai vu que vous trouviez ça bizarre de programmer sous python 2.7, il y a une grosse différence avec python 3.4?
20/01/2016, 12h43
tyrtamos

Bonjour,

Citation:

Envoyé par Fenelon St Marie

Pour n = 100 000, j'obtient le résultat en 3.28s avec la fonction time.clock.
Ca commence à faire une bonne différence avec la machine de marco056, pourtant j'ai un core i3 avec 4G de RAM sous windows et je trouvais ça pas trop mal pour faire du python :calim2:

Il y a une différence entre Windows et Linux sur ce que mesure time.clock(): je crois que sur Linux, on mesure le temps passé par le seul calcul sur le CPU, ce qui donne un résultat plus faible.

Citation:

Envoyé par Fenelon St Marie

J'ai vu que vous trouviez ça bizarre de programmer sous python 2.7, il y a une grosse différence avec python 3.4?

Python 2.7 marche bien mais est un produit mort: il n'y aura plus aucune évolution.

Python 3 est sorti il y a 7 ans en décembre 2008,! C'est donc maintenant le Python "normal", et il intègre des améliorations en permanence. La plus connue est le traitement des chaines de caractères: on travaille maintenant en unicode, ce qui simplifie beaucoup les problèmes d'encodage. On a aussi une modification du calcul entre entiers: la division entre 2 entiers donne un flottant (ça donnait un entier avec Python 2). Etc... (voir la doc). En contrepartie, il y a une "rupture de compatibilité": les changements font que les programmes écrits en Python 2 nécessitent en général d'être modifiés pour être exécutés sous Python 3 (il y a un logiciel qui facilite cette conversion: 2to3.py).

En résumé, on travaille maintenant en Python 3, sauf si on a une "bonne" raison (je ne parle pas des mauvaises... :D) de rester en Python 2, par exemple: nécessité d'utiliser un module externe qui n'existe pas (encore) en Python 3, ou modification mineure d'un programme de grande taille écrit en Python 2.
20/01/2016, 14h46
wiztricks

Citation:

Envoyé par tyrtamos

En résumé, on travaille maintenant en Python 3, sauf si on a une "bonne" raison (je ne parle pas des mauvaises... :D) de rester en Python 2, par exemple: nécessité d'utiliser un module externe qui n'existe pas (encore) en Python 3, ou modification mineure d'un programme de grande taille écrit en Python 2.

Ce sont de bonnes raisons pour des développeurs.
Dans l'enseignement, c'est une autre histoire: on travaille avec la version de Python que le professeur a demandé d'utiliser ou utilise. Cela lui évite d'avoir à mettre à jour ses cours/exos tous les 18 mois et çà ne change pas grand chose à ce qu'il va pouvoir enseigner surtout s'il utilise Python non pas pour enseigner l'informatique mais pour enseigner une matière qui a besoin d'outils pour calculer: physique, biologie, finance, dao,...

- W