Wenn Sie sehr große Zahlen multiplizieren, verwenden Sie die FFT-basierte Multiplikation (siehe Schönhage-Strassen-Algorithmus). Aus Performance-Gründen cache ich die Twiddle-Faktoren. Das Problem ist, dass ich für große Zahlen (Gigabyte-Größe) FFT-Tabellen der Größe 2 ^ 30 und mehr benötige, die zu viel RAM belegen (16 GB und mehr). Es scheint also, dass ich einen anderen Algorithmus verwenden sollte.
Es gibt eine Software namens y-cruncher, die verwendet wird, um Pi und andere Konstanten zu berechnen, die Zahlen in Terabyte-Größe multiplizieren können. Es verwendet einen Algorithmus namens Hybrid-NTT und ein weiterer Algorithmus aufgerufen VST (sehen Ein Höhepunkt in y-cruncher v0.6.1 im Abschnitt Der VST-Multiplikationsalgorithmus).
Kann jemand etwas Licht in diese Algorithmen oder jeden anderen Algorithmus bringen, der verwendet werden kann? multiplizieren Sie Terabyte-große Zahlen?
Ich habe dies als “zu breit” gestimmt, weil eine gute Antwort auf “Wie funktioniert die Out-of-Core-Integer-Multiplikation?” wird wohl nicht zu kurz kommen. Da ich weiß, dass Mystcial ein aktiver SO-Beitragender ist, ziehe ich meine enge Abstimmung jedoch gerne zurück, wenn jemand zufällig eine gute Antwort gibt.
– tmyklebu
1. März 2015 um 21:20 Uhr
Exakt. Nur dass die Nummer nicht 1234567890 ist, sondern 10^12 Stellen hat. Und ich will nicht quadrieren, sondern zwei beliebige Zahlen multiplizieren. Und ich will, dass es schnell geht. Die Grundschulmethode hat eine Laufzeit von O(n^2).
– iblau
1. März 2015 um 21:26 Uhr
Ja, @chux, ich möchte das exakte Produkt der Größe n + m (oder n + m-1) zweier Zahlen der Größe n, m mit n, m ~ 1 TB berechnen.
– iblau
2. März 2015 um 2:25 Uhr
Jerry ist genau richtig. Es geht um die Implementierung und nicht um den Algorithmus. Wenn das Problem, auf das Sie stoßen, die Twiddle-Faktoren sind, sollten Sie sich daran erinnern, dass das Caching von Twiddle-Faktoren ein Kompromiss zwischen Raum und Zeit ist. Sie müssen sich nicht an einem der beiden Extreme des Kompromisses befinden. Wenn Sie an den Punkt kommen, an dem Sie sie auf die Festplatte auslagern müssen, kann es sich lohnen, sie stattdessen spontan zu generieren. Sie cachen also einige, aber nicht alle Twiddles. Außerdem benötigt der Schönhage-Strassen-Algorithmus keine Twiddle-Faktoren, da sie zu Verschiebungen degenerieren.
– Mystisch
3. März 2015 um 19:29 Uhr
Speziell der Schönhage-Strassen-Algorithmus – der ein Sonderfall des NTT ist. Es ist der einzige bekannte Algorithmus, der triviale Twiddle-Faktoren hat. (Die Twiddle-Faktoren sind alle Zweierpotenzen, müssen also nicht zwischengespeichert werden.)
– Mystisch
3. März 2015 um 19:42 Uhr