Gestion des grands nombres dans le code

Question

Je travaille sur un problème de programmation où je dois gérer un nombre de 100000 chiffres. Python peut-il gérer des nombres comme celui-ci?

Answer 1

Bien sûr, il peut:

>>> s = 10 ** 100000 

Answer 2

Il semble bien fonctionner:

>>> x = 10**100000 
>>> x 
10000000000000000000000000000000000000000000000000000000000000000000000000000000 
[snip] 
00000000L 

Selon http://docs.python.org/library/stdtypes.html, « Les entiers longs ont une précision illimitée », ce qui signifie sans doute que leur taille n'est pas limitée.

Answer 3

Oui; Python 2.x a deux types d'entiers, int de taille limitée et long de taille illimitée. Cependant, tous les calculs seront automatiquement convertis en longs si nécessaire. La gestion des grands nombres fonctionne bien, mais l'une des choses les plus lentes sera si vous essayez d'imprimer les 100000 chiffres à la sortie, ou même essayez de créer une chaîne à partir de cela.

Si vous avez également besoin d'une précision en virgule fixe décimale arbitraire, il existe le module décimal.

Answer 4

Comme d'autres réponses l'indiquent, Python ne supporte les nombres entiers limités que par la quantité de mémoire disponible. Si vous voulez un soutien encore plus rapide pour eux, essayer gmpy (comme auteur et co-mainteneur de gmpy Je suis bien sûr un peu biaisé ici ;-):

$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'x+1' 
10000 loops, best of 3: 114 usec per loop 
$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y+1' 
10000 loops, best of 3: 65.4 usec per loop 

En règle générale, l'arithmétique n'est pas le goulot d'étranglement pour travailler avec ces nombres (bien que le support direct de gmpy pour certaines fonctions combinatoires et théoriques des nombres peut aider si c'est ce que vous faites avec de tels nombres). En tournant les nombres en chaînes décimales est probablement l'opération commune qui se sentent le plus lent ...:

$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'str(x)' 
10 loops, best of 3: 3.11 sec per loop 
$ python -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'str(y)' 
10 loops, best of 3: 27.3 msec per loop 

Comme vous le voyez, même dans gmpy des nombres énormes mise en chaîne peut être des centaines de fois plus lent qu'une simple addition (hélas, c'est une opération intrinsèquement compliquée!); mais en code Python natif, le rapport des temps peut aller à la stringification étant des dizaines de milliers fois plus lent qu'une simple addition, donc vous voulez vraiment faire attention à cela, surtout si vous décidez de ne pas télécharger et installer gmpy (par exemple parce que vous ne pouvez pas: par exemple, gmpy n'est actuellement pas compatible avec Google App Engine).

Enfin, un cas intermédiaire:

$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'x*x' 
10 loops, best of 3: 90 msec per loop 
$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y*y' 
100 loops, best of 3: 5.63 msec per loop 
$ python2.6 -mtimeit -s'import gmpy; x=10**100000; y=gmpy.mpz(x)' 'y*x' 
100 loops, best of 3: 8.4 msec per loop 

Comme vous le voyez, la multiplication de deux nombres énormes dans le code Python natif peut être presque 1000 fois plus lent que la simple addition, tandis qu'avec gmpy le ralentissement est inférieure à 100 fois (et ce n'est pas trop mal, même s'il n'y en a qu'un si les nombres sont déjà dans le format propre de gmpy, de sorte qu'il y a le coût de la conversion de l'autre).

Answer 5

Comme déjà souligné, Python peut gérer des nombres aussi grands que votre mémoire le permet. Je voudrais juste ajouter que plus les chiffres augmentent, plus le coût de toutes les opérations augmente. Ce n'est pas seulement pour l'impression/conversion en chaîne (bien que ce soit le plus lent), en ajoutant deux grands nombres (plus gros que ce que votre matériel peut gérer nativement) n'est plus O (1).Je ne fais que mentionner ceci pour signaler que bien que Python dissimule soigneusement les détails de travailler avec de grands nombres, vous devez toujours garder à l'esprit que ces opérations de grand nombre ne sont pas toujours comme celles sur des ints ordinaires.