Come posso convertire un numero assolutamente voluminoso in una stringa in un ragionevole lasso di tempo?

Question

Questo è un problema piuttosto strano, ma sto cercando di ottenere una copia del numero primo più grande corrente in un file. Ottenere il numero in forma intera è abbastanza facile. Ho appena eseguito questo.

prime = 2**74207281 - 1 

Ci vuole circa mezzo secondo e funziona bene. Anche le operazioni sono abbastanza veloci. Dividerlo per 10 (senza decimali) per spostare le cifre è veloce. Tuttavia, lo str(prime) impiega molto tempo. Ho reimplementato str in questo modo e ho scoperto che stava elaborando circa un centinaio di cifre al secondo.

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

C'è un modo per farlo in modo più efficiente? Lo sto facendo in Python. Dovrei provare anche questo con Python, o c'è uno strumento migliore per questo?

Answer 1

La ripetuta concatenazione di stringhe è notoriamente inefficiente poiché le stringhe Python sono immutabili. Vorrei andare per

strprime = str(prime) 

Nei miei benchmark, questa è costantemente la soluzione più veloce. Ecco il mio piccolo programma di riferimento:

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"))) 

Per me, questo stampe (utilizzando Python 2.7.10):

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

Answer 2

Esiste gmp, la libreria di aritmetica di precisione multipla GNU. E 'progettato specialmente per gestire numeri enormi velocemente.

Answer 3

sono voluti circa 32 secondi per l'uscita del file utilizzando WinGhci (lingua Haskell):

import System.IO 

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

Il file era 21 megabyte; le ultime quattro cifre, 6351.

Answer 4

L'algoritmo di conversione da intero a stringa di Python utilizza un algoritmo semplicistico con un'esecuzione di O (n ** 2). Quando la lunghezza del numero raddoppia, il tempo di conversione quadruplica.

alcuni semplici test sul mio computer mostrano l'aumento del tempo di esecuzione:

$ 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 

Poiché l'esponente attuale è circa 10 volte più grande di mio ultimo valore di prova, si dovrebbe prendere circa 100 volte più a lungo. O poco più di 3 ore.

È possibile eseguire più rapidamente? Sì. Esistono diversi metodi più veloci.

Metodo 1

è più veloce per dividere il numero molto elevato da un numero approssimativamente uguale grandezza ma piccole potenze di 10 in due. Il processo viene ripetuto fino a quando i numeri sono relativamente piccoli. Quindi su ogni numero viene utilizzato str() e gli zeri iniziali vengono utilizzati per applicare il risultato alla stessa lunghezza dell'ultima potenza di 10. Quindi le corde vengono unite per formare il risultato finale. Questo metodo è utilizzato dalla libreria mpmath e la documentazione implica che dovrebbe essere circa 3 volte più veloce.

Metodo 2

interi di Python sono memorizzati in formato binario. Il binario è ottimo per i calcoli ma la conversione da binaria a decimale è il collo di bottiglia. È possibile definire il proprio tipo intero che memorizza il valore in blocchi di 100 cifre decimali (o un valore simile). Le operazioni (esponenziazione, moltiplicazione, divisione) saranno più lente ma la conversione in una stringa sarà molto veloce.

Molti anni fa, ho implementato tale classe e utilizzato algoritmi efficienti per la moltiplicazione e la divisione. Il codice non è più disponibile su Internet ma ho trovato una copia di backup che ho testato. Il tempo di esecuzione è stato ridotto a ~ 14 secondi.

Aggiornamento

Ho aggiornato il codice di riferimento DecInt sopra ed è ora disponibile a https://github.com/casevh/DecInt.

Se viene utilizzato il tipo intero nativo di Python, il tempo di esecuzione totale è inferiore a 14 secondi sul computer. Se invece viene usato il tipo intero gmpy2, il tempo di esecuzione è di ~ 3,5 secondi.

$ 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 

Metodo 3

mantengo la biblioteca gmpy2 che forniscono un facile accesso alla biblioteca GMP per l'aritmetica intero veloce. GMP implementa il Metodo 1 nel codice C e assembly altamente ottimizzato e calcola il numero primo e la rappresentazione della stringa in ~ 5 secondi.

Metodo 4

Il modulo decimal in Python memorizza valori come cifre decimali. Le versioni recenti di Python 3 includono un'implementazione C della libreria decimale che è molto più veloce che l'implementazione di pure-Python include con Python 2. L'implementazione C viene eseguita in poco più di 3 secondi sul mio computer.

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