Wie kann ich eine absolut massive Zahl in einer angemessenen Zeit in eine Zeichenfolge konvertieren?

Question

Das ist ein ziemlich merkwürdiges Problem, das ich kenne, aber ich versuche, eine Kopie der aktuellen größten Primzahl in einer Datei zu bekommen. Die Zahl in ganzzahliger Form zu erhalten ist ziemlich einfach. Ich laufe das einfach.

prime = 2**74207281 - 1 

Es dauert etwa eine halbe Sekunde und es funktioniert gut. Operationen sind auch ziemlich schnell. Es wird durch 10 (ohne Dezimalstellen) geteilt, um die Ziffern zu verschieben. Allerdings dauert str(prime) eine sehr lange Zeit. Ich habe str so re-implementiert und festgestellt, dass es etwa hundert Ziffern pro Sekunde verarbeitet.

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

Gibt es eine Möglichkeit, dies effizienter zu tun? Ich mache das in Python. Soll ich das überhaupt mit Python versuchen, oder gibt es dafür ein besseres Tool?

Answer 1

Wiederholte String-Verkettung ist notorisch ineffizient, da Python-Strings unveränderlich sind. Ich würde gehen für

strprime = str(prime) 

In meinen Benchmarks ist dies immer die schnellste Lösung. Hier ist mein kleines Benchmark-Programm:

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

Für mich ist diese Drucke (mit Python 2.7.10):

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

Answer 2

Es gibt gmp, die GNU Multiple Precision Arithmetic Library. Es ist speziell für den schnellen Umgang mit großen Zahlen ausgelegt.

Answer 3

dauerte etwa 32 Sekunden für die Ausgabe der Datei mit WinGhci (Haskell Sprache):

import System.IO 

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

Die Datei war 21 Megabyte; die letzten vier Ziffern, 6351.

Answer 4

Python-Algorithmus zur Umwandlung von Ganzzahl in Zeichenfolge verwendet einen vereinfachten Algorithmus mit einer Ausführung von O (n ** 2). Wenn sich die Anzahl verdoppelt, vervierfacht sich die Wandlungszeit.

Einige einfachen Tests auf meinem Computer in Laufzeit den Anstieg zeigen:

$ 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 

Da der eigentliche Exponent etwa 10-mal größer als bei meinem letzten Testwert ist, sollte es etwa 100-mal länger dauern. Oder etwas mehr als 3 Stunden.

Kann es schneller gemacht werden? Ja. Es gibt mehrere Methoden, die schneller sind.

Methode 1

Es ist schneller, die sehr große Anzahl von einer Power-of-10 in zwei etwa gleich großen, aber kleineren Zahlen zu teilen. Der Prozess wird wiederholt, bis die Zahlen relativ klein sind. Dann wird str() für jede Nummer verwendet und führende Nullen werden verwendet, um das Ergebnis auf die gleiche Länge wie die letzte Potenz von 10 zu puffern. Dann werden die Saiten verbunden, um das Endergebnis zu bilden. Diese Methode wird von der Bibliothek mpmath verwendet und die Dokumentation legt nahe, dass sie etwa 3x schneller sein sollte.

Methode 2

ganzen Zahlen Pythons sind im binären Format gespeichert. Binär ist ideal für Berechnungen, aber Binär-zu-Dezimal-Konvertierung ist der Flaschenhals. Es ist möglich, einen eigenen Integer-Typ zu definieren, der den Wert in Blöcken von 100 Dezimalziffern (oder ähnlichen Werten) speichert. Operationen (Potenzierung, Multiplikation, Division) werden langsamer, aber die Umwandlung in eine Zeichenfolge ist sehr schnell.

Vor vielen Jahren implementierte ich eine solche Klasse und verwendete effiziente Algorithmen zur Multiplikation und Division. Der Code ist nicht mehr im Internet verfügbar, aber ich habe eine Sicherungskopie gefunden, die ich getestet habe. Die Laufzeit wurde auf ~ 14 Sekunden reduziert.

aktualisieren

ich die DecInt Code verwiesen oben aktualisiert und es ist bei https://github.com/casevh/DecInt ab sofort verfügbar.

Wenn der native Integer-Typ von Python verwendet wird, beträgt die Gesamtlaufzeit auf meinem Computer weniger als 14 Sekunden. Wenn stattdessen der Integer-Typ gmpy2 verwendet wird, beträgt die Laufzeit ~ 3,5 Sekunden.

$ 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 

Methode 3

I behalten die gmpy2 Bibliothek, die für die schnelle Integer-Arithmetik einfachen Zugriff auf die GMP-Bibliothek bereitzustellen. GMP implementiert Methode 1 in hoch optimiertem C- und Assemblercode und berechnet die Primzahl und die Zeichenfolgendarstellung in ~ 5 Sekunden.

Methode 4

Das decimal Modul in Python speichert Werte als Dezimalziffern. Jüngste Versionen von Python 3 enthalten eine C-Implementierung der dezimalen Bibliothek, die viel schneller ist als die reine Python-Implementierung mit Python 2. Die C-Implementierung läuft in etwas mehr als 3 Sekunden auf meinem Computer.