prime - python primary number

¿Cómo puedo convertir un número absolutamente masivo en una cadena en un tiempo razonable?

Question

Este es un problema bastante extraño que conozco, pero estoy tratando de obtener una copia del mayor número primo actual en un archivo. Obtener el número en forma de entero es bastante fácil. Acabo de ejecutar esto.

prime = 2**74207281 - 1

Tarda alrededor de medio segundo y funciona bien. Las operaciones son bastante rápidas también. Dividirlo por 10 (sin decimales) para cambiar los dígitos es rápido. Sin embargo, str(prime) está tardando mucho tiempo. Volví a implementar str esta manera y descubrí que estaba procesando unos cien dígitos por segundo.

while prime > 0:
    strprime += str(prime%10)
    prime //= 10

¿Hay alguna manera de hacer esto de manera más eficiente? Estoy haciendo esto en Python. ¿Debo intentar esto con Python o hay una herramienta mejor para esto?

Answer 1

El algoritmo de conversión de enteros a cadenas de Python utiliza un algoritmo simplista con una ejecución de O (n ** 2). A medida que la longitud del número se duplica, el tiempo de conversión se cuadruplica.

Algunas pruebas simples en mi computadora muestran el aumento en el tiempo de ejecución:

$ time py35 -c "n=str(2**1000000)"
user    0m1.808s
$ time py35 -c "n=str(2**2000000)"
user    0m7.128s
$ time py35 -c "n=str(2**4000000)"
user    0m28.444s
$ time py35 -c "n=str(2**8000000)"
user    1m54.164s

Dado que el exponente real es aproximadamente 10 veces más grande que mi último valor de prueba, debería demorar unas 100 veces más. O algo más de 3 horas.

¿Se puede hacer más rápido? Sí. Hay varios métodos que son más rápidos.

Método 1

Es más rápido dividir el número muy grande por una potencia de 10 en dos números más o menos del mismo tamaño pero más pequeños. El proceso se repite hasta que los números son relativamente pequeños. Luego se usa str() en cada número y los ceros iniciales se usan para rellenar el resultado a la misma longitud que la última potencia de 10. Luego las cuerdas se unen para formar el resultado final. Este método es utilizado por la biblioteca mpmath y la documentación implica que debería ser aproximadamente 3 veces más rápido.

Método 2

Los enteros de Python se almacenan en formato binario. Binary es ideal para cálculos, pero la conversión de binario a decimal es el cuello de botella. Es posible definir su propio tipo de entero que almacena el valor en bloques de 100 dígitos decimales (o algún valor similar). Las operaciones (exponenciación, multiplicación, división) serán más lentas, pero la conversión a una cadena será muy rápida.

Hace muchos años, implementé tal clase y usé algoritmos eficientes para la multiplicación y la división. El código ya no está disponible en Internet, pero encontré una copia de respaldo que probé. El tiempo de ejecución se redujo a ~ 14 segundos.

Actualizar

Actualicé el código DecInt al que se hace referencia anteriormente y ahora está disponible en https://github.com/casevh/DecInt .

Si se utiliza el tipo de entero nativo de Python, el tiempo total de ejecución es menos de 14 segundos en mi computadora. Si se gmpy2 el tipo entero de gmpy2 en su lugar, el tiempo de ejecución es de ~ 3.5 segundos.

$ py35 DecInt.py
Calculating 2^74207281
Exponentiation time: 3.236
Conversion to decimal format: 0.304
Total elapsed time: 3.540
Length of result: 22338618 digits

Método 3

gmpy2 biblioteca gmpy2 que proporciona un acceso fácil a la biblioteca GMP para una rápida aritmética de enteros. GMP implementa el Método 1 en C y código de ensamblaje altamente optimizados y calcula el número primo y la representación de cadena en ~ 5 segundos.

Método 4

El módulo decimal en Python almacena valores como dígitos decimales. Las versiones recientes de Python 3 incluyen una implementación en C de la biblioteca decimal que es mucho más rápida que la implementación en Python puro con Python 2. La implementación en C se ejecutó en poco más de 3 segundos en mi computadora.

from decimal import *
getcontext().prec = 23000000
getcontext().Emin = -999999999
getcontext().Emax = 999999999
x=Decimal(2)**74207281 - 1
s=str(x)

Answer 2

Hay gmp, la biblioteca aritmética de precisión múltiple de GNU. Está especialmente diseñado para manejar grandes números rápidamente.

Answer 3

La concatenación repetida de cadenas es notoriamente ineficiente ya que las cadenas de Python son inmutables. Yo iria por

strprime = str(prime)

En mis puntos de referencia, esta es siempre la solución más rápida. Aquí está mi pequeño programa de referencia:

import decimal

def f1(x):
    '''''' Definition by OP ''''''
    strprime = ""
    while x > 0:
        strprime += str(x%10)
        x //= 10
    return strprime

def digits(x):
    while x > 0:
        yield x % 10
        x //= 10

def f2(x):
    '''''' Using string.join() to avoid repeated string concatenation ''''''
    return "".join((chr(48 + d) for d in digits(x)))

def f3(x):
    '''''' Plain str() ''''''
    return str(x)

def f4(x):
    '''''' Using Decimal class''''''
    return decimal.Decimal(x).to_eng_string()

x = 2**100

if __name__ == ''__main__'':
    import timeit
    for i in range(1,5):
        funcName = "f" + str(i)
        print(funcName+ ": " + str(timeit.timeit(funcName + "(x)", setup="from __main__ import " + funcName + ", x")))

Para mí, esto imprime (usando Python 2.7.10):

f1: 15.3430171013
f2: 20.8928260803
f3: 0.310356140137
f4: 2.80087995529

Answer 4

Tomó alrededor de 32 segundos generar el archivo usando WinGhci (lenguaje Haskell):

import System.IO

main = writeFile "prime.txt" (show (2^74207281 - 1))

El archivo tenía 21 megabytes; Los últimos cuatro dígitos, 6351.