Manejo de números grandes en el código

Question

Estoy trabajando en un problema de programación en el que necesito manejar un número de 100000 dígitos. ¿Python puede manejar números como este?

Answer 1

seguro de que puede:

>>> s = 10 ** 100000 

Answer 2

Parece que funciona bien:

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

Según http://docs.python.org/library/stdtypes.html, "enteros largos tienen precisión ilimitada", lo que probablemente significa que su tamaño no está limitado.

Answer 3

Sí; Python 2.x tiene dos tipos de enteros, int de tamaño limitado y largo de tamaño ilimitado. Sin embargo, todos los cálculos se convertirán automáticamente en largos si es necesario. Manejar números grandes funciona bien, pero una de las cosas más lentas será si intentas imprimir los 100000 dígitos a la salida, o incluso intentas crear una cadena a partir de ella.

Si necesita precisión de punto fijo decimal arbitraria, existe el módulo decimal.

Answer 4

Como se indica en otras respuestas, Python admite números enteros limitados solo por la cantidad de memoria disponible. Si desea soporte aún más rápido para ellos, tratar gmpy (como el autor del gmpy y actual co-mantenedor estoy, por supuesto, un poco parcial aquí ;-):

$ 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 

Típicamente, la aritmética no es el cuello de botella para trabajar con tales números (aunque el soporte directo de gmpy para algunas funciones combinatorias y teóricas de números puede ayudar si eso es lo que está haciendo con tales números). Girando los números decimales en cadenas es probablemente la operación común que se sentirá más lento ...:

$ 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 

Como se ve, incluso en gmpy stringification de grandes números pueden ser cientos de veces más lento que una simple adición (por desgracia, ¡es una operación intrínsecamente complicada!); pero en el código nativo de Python la relación de tiempos puede ir a la stringificación que es decenas de miles veces más lenta que una simple adición, por lo que realmente debes tener cuidado, especialmente si decides no descargar e instalar gmpy (por ejemplo, no puede: por ejemplo, gmpy no es actualmente compatible con Google App Engine).

Por último, un caso intermedio:

$ 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 

Como se ve, la multiplicación de dos números enormes de código Python nativo puede ser casi 1000 veces más lenta que la simple adición, mientras que con gmpy la desaceleración es inferior a 100 veces (y no es tan malo, aunque solo sea uno, si los números ya están en el formato propio de gmpy, de modo que exista la sobrecarga de convertir el otro).

Answer 5

Como ya se señaló, Python puede manejar números tan grandes como lo permita su memoria. Me gustaría agregar que a medida que los números crecen, el costo de todas las operaciones en ellos aumenta. Esto no es solo para imprimir/convertir a cadena (aunque es la más lenta), sino que agrega dos números grandes (más grandes que lo que su hardware puede manejar de forma nativa) ya no es O (1).

Solo menciono esto para señalar que, si bien Python oculta cuidadosamente los detalles de trabajar con números grandes, aún debe tener en cuenta que estas operaciones de números grandes no son siempre las mismas que en las operaciones normales.