Dezimaldarstellung einer großen Zahl

bords0 · Dienstag 2. August 2011, 08:03

Kürzlich wurde ich gefragt, was den 3 hoch 100 Millionen sei. Kein Problem, dachte, und ließ Python

a = 3 ** 100000000

ausrechnen. Funktionierte sogar in akzeptabler Zeit (wenn auch nicht augenblicklich).

Jetzt wollte ich nur noch die Zahl in eine Datei schreiben. Dazu habe ich mal

Code: Alles auswählen

s = str(a)

eingebeben. Und wartete. Und wartete. Und wartete. Und habs am nächsten Tag abgebrochen. Das Konvertieren ins Dezimalsystem ist anscheinend aufwändiger als das Ausrechnen. Im Nachhinein nicht unplausibel....

Kennt jemand eine Möglichkeit, das in vernünftiger Zeit hinzubekommen?

gkuhl · Dienstag 2. August 2011, 08:50

Hast du mal abgeschätzt wieviele Ziffern 3**100000000 hat?

BlackJack · Dienstag 2. August 2011, 09:10

@bords0: Die „GNU Multiple Precision Arithmetic Library” (libgmp) bekommt das in vertretbarer Zeit hin. Es gibt eine Python-Anbindung (`gmpy`).

@gkuhl: Es sind genau 47.712.126 Ziffern.

gkuhl · Dienstag 2. August 2011, 12:22

@BlackJack: Meine Schätzung war 47.712.255. Linear extrapoliert aus den ersten 1000 Elementen der Folge. Hätte nicht gedacht, dass das so gut funktioniert.

Darii · Dienstag 2. August 2011, 13:29

Ja ist mir auch schonmal aufgefallen, dass das nicht linear ist ab einem Schwellwert dauert es lange, hatte aber nie Lust mir die Implementierung genauer anzugucken.

bords0 · Dienstag 2. August 2011, 15:31

Sehe ich das richtig, dass ich GMP selbst kompilieren muss? (Bin auf Windows.)

BlackJack · Dienstag 2. August 2011, 16:10

@bords0: Könnte sein. Falls die Bibliothek nicht in den Windows-Installern für das Python-Modul enthalten ist.

bords0 · Mittwoch 3. August 2011, 08:13

@gkuhl: meine Schätzung wäre gewesen

Code: Alles auswählen

 >>> math.log10(3)*100000000
47712125.471966244

was wgenau dem tatsächlichen Wert entspricht (natürlich muss man aufrunden).

@BlackJack: gmpy bringt tatsächlich alles mit. Ich hatte mich von der Meldung "DLL load failed" irritieren lassen (gmpy2 auf python 2.7). Mit gmpy (ohne 2) auf 3.2 ging es aber problemlos. (Und ich war schon auf der Suche nach MPIR-binaries - MPIR wird meist auf Windows als gmp-Ersatz verwendet...)

Danke! Geht rasend schnell.

BlackJack · Mittwoch 3. August 2011, 16:00

@bords0: Das DLL load failed… könnte auch an einer fehlenden Microsoft-DLL liegen. Auf der Webseite von `gmpy` bei Google stand dazu etwas.