Wie multipliziert man Terabyte-große Zahlen?

Wenn Sie sehr große Zahlen multiplizieren, verwenden Sie eine FFT-basierte Multiplikation (siehe Schönhage–Strassen algorithm). Aus Leistungsgründen speichere ich die Twiddle-Faktoren. Das Problem ist für große Zahlen (Gigabyte-Größe) Ich brauche FFT-Tabellen der Größe 2^30 und mehr, die zu viel RAM (16 GB und höher) belegen. Es scheint also, ich sollte einen anderen Algorithmus verwenden.Wie multipliziert man Terabyte-große Zahlen?

Es gibt eine Software namens y-cruncher, die zur Berechnung von Pi und anderen Konstanten verwendet wird, die Terabyte große Zahlen multiplizieren können. Es verwendet einen Algorithmus namens Hybrid NTT und einen anderen Algorithmus namens VST (siehe A Peak into y-cruncher v0.6.1 im Abschnitt Der VST Multiplikation Algorithmus).

Kann jemand etwas Licht auf diese Algorithmen oder einen anderen Algorithmus werfen, der verwendet werden kann, um zu multiplizieren Terabyte-große Zahlen?

Quelle

2015-03-01 iblue

Ich wählte dies als "zu breit", weil eine gute Antwort auf "Wie funktioniert Out-of-Core-Integer-Multiplikation?" wird wahrscheinlich nicht kurz sein. Mysticial zu kennen ist ein aktiver SO-Mitwirkender, aber ich bin ziemlich glücklich, meine enge Stimme zurückzuziehen, wenn jemand eine gute Antwort gibt. – tmyklebu

Möchten Sie wissen, wie man 1234567890^2 durchführt? Ich weiß nicht, was deine Frage ist. –

Denken Sie daran, in der Grundschule, wenn Sie multipliziert Spalten, getragen und dann hinzugefügt ... Das gleiche, aber Sie müssen es nicht für jede Potenz von 10 tun ... nur alle 2^n (wobei n die Anzahl der Bits ist in Ihrem größten Integer-Typ) – technosaurus

FFT kann auf demselben Array mit konstanter Anzahl von zusätzlichem Speicher ausgeführt werden (möglicherweise muss die Nummer intelligent ausgetauscht werden). Daher kann es auch auf der Festplatte gemacht werden. Im schlimmsten Fall ist es ein log (N) * N mal Festplattenzugriff. Es scheint viel langsamer zu sein als im RAM, aber die Gesamtkomplexität bleibt gleich.

Quelle

2015-03-04 04:43:37

Die Komplexität kann gleich bleiben, aber [die tatsächlichen Lesezeiten sind viel, viel langsamer] (https://gist.github.com/jboner/2841832). Vergessen Sie nicht, dass diese konstanten Faktoren in der Praxis wichtig sind. – wchargin

es ist Log (N) Zeiten des sequentiellen Festplattenzugriffs nur des gesamten Arrays, sollte viel schneller sein als wahlfreier Zugriff. wenn Sie FFT intelligent implementieren (die Nummer am Anfang neu anordnen). –

Für große Zahlen (> 4 GB) kann ich über FFT 10 Bits oder weniger in einen komplexen Datenpunkt packen (2 double = 128 bit), also muss ich 12,8 mal die Größe der tatsächlichen Zahl schreiben, wenn ich FFT mache . Dies wäre nicht sehr effizient. – iblue

Wie multipliziert man Terabyte-große Zahlen?

Antwort

Verwandte Themen