FFT für schnelle Multiplikation

[negaH]

Zitat:

Mein Ziel ist es eine Multiplikation zweier Zahlen mit je 128 MBit (2^27 Bit) zu implementieren. Solch eine Zahl bräuchte also 16 MByte Speicherplatz. Um 2 Zahlen zu multiplizieren entsprechend 32 MByte und weitere 32 MByte für das Ergebnis. Das ginge ja soweit. Bei der 1:1 Implementation des Algorithmus' wird aber gefordert, das für *jedes Bit* der beiden Ausganszahlen eine komplexe Zahl mit Speicherplatzbedarf von 8 Byte (je 4 Byte für den real- und den Imaginärteil) vorliegt. bei 2 Ausgangszahlen a 128 MBit komme ich auf einen zusätzlichen Speicherbedarf von 2GByte... Pale

Stop du implementierst da den falschen Algortihmus. In der Zahlentheorie bzw. den dazu nötigen Bibliotheken wird der

modulare Fermat Schönhage Strassen

benutzt. Dieser arbeitet nicht mit komplexen Zahlen sondern modular zu Fermat'schen Zahlen -> die sind praktisch gesehen vergleichbar mit Primzahlen (aus Sicht ihrer Eigenschaften für diese FFT)

Je nach Implementierung benötigt man Ln2(A) + Ln2(B) an Speicher minimal (A * B), d.h. wenn man inplaced multipliziert und den Speicher der Multiplikanten überschreibt. Das ist unpraktisch und meistens wird man die doppelte Menge an Speicher benötigen (alleine schon weil man für das Resulat die beiden separaten Speicherbereiche für A und B ja in einem linearen Speicherbereich für das Resultat bringen muß, und meistens liegen A und B nicht lückenlos hintereinander im Speicher). Aber auch dies dürfte noch sehr optimistisch sein da man unter Umständen die Multiplikanten expandieren muß, dh. Nullen dranhängen. Meine eigene Implementierung der "modularen Fermat Schönhage Strassen FFT" benötigt im schlechtesten Falle 3 mal mehr Speicher als die Multiplikanten an Speicher belegen. Dies liegt daran das alle meine LowLevel Routinen meistens nicht Inplaced arbeiten bei solch komplexen Berechnungen. Dh. diese Routinen kopieren quasi Speicherbereiche in einen neuen Speicherbereich und erledigen nebenbei die mathematische Operation. Dies hat sich aus Sicht der Gesamtperformance als am besten heraus gestellt. Was eben zu Folge hat das man zb. in der FFT mehr an Speicher benötigt als theoretisch minimal notwendig.

Du solltest unbedingt zu Vergleichszwecken während deiner Entwicklung eine funktionsfähige Fremdbibliothek benutzen. Ich hatte zb. lange Zeit mit meinem DecMath gearbeitet und erst sehr spät festgestellt das bei der Berechnung der Konstante Pi mit mehr als 16 Millionen Stellen in meinen FFT Funktionen ein "hinterfo..iger" Bit-Überlauf-Fehler auftrat. Finden konnte ich ihn nur weil ich eine "Fremdbibliothek" (meine alten TBigNums ) zum Vergleich heranzog.

Gruß Hagen