FFT für schnelle Multiplikation

[MatWur]

Hallo,

ich beschäftige mich derzeit mit der Implementation schneller Algorithmen auf meinem Computer, dazu wäre eine schnelle Multiplikation erforderlich. Nun gibt es den Schönhagen-Strasse Algorithmus der eine Schnelle Fourier Transformation (FFT) beschreibt, um 2 Zahlen in Binärdarstellung mit einem besserem Laufzeitverhalten zu multiplizieren als dies die Schulmethode oder das Verfahren nach Karazuba können.
Diesen FFT-Algorithmus (eine gute Beschreibung kann man hier finden: http://www.inf.fh-flensburg.de/lang/...en/fft/fft.htm) bereitet mir bei der Implementierung erhebliche Schwierigkeiten. D.h. eigentlich weniger der Algorithmus als viel mehr der Speicherplatz, den ich zur Multiplikation mit dieser Methode benötige. 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:
Hmmm, so wird das nix mit der schnellen Multiplikation und mir...
Ich weiss nun, das es bereits sehr gute Implementierungen dieser FFT gibt, z. Bsp. in GIMPS (einem Projekt zur Suche grosser Primzahlen, evtl. mal nach googeln). Und diese Implementierungen sind nicht nur schnell sondern auch Speicherschonend. Dr. Woltman (der Programmierer der meisten Routinen des GIMPS-Projektes) hat nun den Quellcode seiner Implementation veröffentlicht (kann auf der GIMPS Homepage runtergeladen werden), leider kann ich mit diesem C++ Code gar nichts anfangen :wall:

Deswegen nun meine Frage: kann mir jemand der sich mit diesem FFT-Algorithmus auskennt den entscheidenden Hinweis geben, wie ich auf einen erträglichen Speicherbedarf komme? Bzw. (was fast noch besser wäre) gibt es einen öffentlich zugänglichen Quellcode in Pascal/Assembler, der diesen Algorithmus speicherschonend und schnell implementiert (an Beispielen lernt sich's bekanntermaßen am einfachsten :D)?

Vielen Dank schon im vorraus für jede Lösungshife

Matthias

[Relicted]

Hallo MatWur und willkommen bei dp...

Ich habe mich mal kurz umgeschaut auf der Seite aber jetzt nicht direkt den C-Algo gefunden.
Vielleicht kannst ja mal einen Direktlink raussuchen. Gibt hier sicher einige Leute die auch ne menge Spaß am "übersetzen" von C->Delphi haben.
Die Jungs werden dir sicher unter die Arme greifen :-)

Hast du mal drüber nachgedacht den Algo in eine dll auszulagern? also in c zu kompilieren und in dein delphi projekt zu laden?
wäre vielleicht auch noch ein ansatz.

Gruß
Reli

[MatWur]

ja, Danke Schön erst einmal und noch ein Hallo in die Runde ;)

den GIMPS Source-Code gibt es hier: http://www.mersenne.org/source.htm
zu der anderen Webpage gibt es keinen Source-code, nur das Progrämmchen in Pseudo-code am Ende der Seite. Ich selber habe keinen C++ Compiler, bisher kam ich mit meiner alten Delphi-Version eigentlich immer aus. Ich habe versucht aus einigen der Codes schlau zu werden, aber welcher Delphi-Programmierer versteht schon sowas wie k-==++! (oder so ähnlich...ich mag kein C++ ;) ) :mrgreen:
Mir geht es darum selber eine brauchbare FFT-Multiplikation in Pascal/Assembler zu schreiben, ich möchte mir da ein kleines Paket (evtl. in einer DLL, aber wohl eher in einer Delphi-Unit) zusammenschreiben mit schnellen Routinen für sehr grosse Ganzzahlen um ein paar Zahlentheoretische Probleme anzugehen. Aber solch eine FFT-Multiplikation ist dazu zwingende Voraussetzung, den die traditionellen Verfahren werden bei Zahlen dieser Grössenordnung einfach zu langsam. Und mein bisheriges Wissen erfordert bei der Implementation viel zu viel Speicher während der Multiplikation. Ich weiss von GIMPS das die bei der Multiplikation (respektive dort wird quadriert, was mir prinzipiell auch reichen würde) lediglich das doppelte des Speicherplatzbedarfes der Ausgangszahl brauchen, wie das gemacht wird, genau das müsste ich wissen :gruebel:

mfg

Matthias

[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

[MatWur]

Zitat:

Zitat von negaH

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

MUUUHHHH. Hat mich meine Mathematik verlassen? In der Tat erhalte ich bei der von mir realisierten FFT (ich dachte das wäre der SchönStrAlg...) Ergebnisse modulo einer Mersennezahl (binäre Form 111...111), nicht modulo einer Fermatzahl (binäre Form 100..001). Aber meines Wissens nach ist es gerade die Vandermonde Matrix die ich benötige, um die Fourier-transformation wirklich schnell (also zur FFT) zu machen, da ich nur diese rekursiv schnell berechnen kann. Ich brauche also eine andere Matrix... hmmmm, ich muss dann mal ein paar Tage Theorie unter neuen Voraussetzungen lesen :zwinker:

Zitat:

Zitat von negaH

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.

Also, 'inplaced' ist mir dadurch klar geworden. Aber für die Multiplikation 2er Zahlen mit je 2^27 Bit soll ich minimal nur 54 Bit Speicherplatz brauchen??? Das klingt niedlich :mrgreen: . Oder meinst du 54 Bit zusätzlich zu dem Speicher, den die beiden Ausgangszahlen und evtl. das Ergebnis braucht (wenn ich nicht inplaced arbeite)?

Zitat:

Zitat von negaH

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.

Das verstehe ich alles. Und dreifacher Speicherbereich der beiden Multiplikanten klingt auch übersichtlich, bei meiner FFT kommt schon aufgrund des grossen Speicherbedarfs eine miese Performance raus...

Zitat:

Zitat von negaH

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

Das mit dem Bitüberlauf bei der Pi-berechnung habe ich irgendwo gelesen. Über die Gültigkeit von Murphey's Naturgesetzen streiten wir beide wohl nicht :zwinker: Genau für Verifizierungszwecke suche ich ja solche Bibliotheken, aber solange ich selber keinen vernünftigen Alg implementiert habe habe ich auch nichts zum prüfen... mir geht es momentan hauptsächlich darum den (richtigen) Algorithmus zu implementieren und lauffähig zu kriegen. Dazu muss ich jetzt erst einmal meine Theorie auffrischen, insbesondere dein Hinweis auf den anderen Algorithmus sollte mich weiterbringen. Den Aufbau der verwendeten Matrix muss ich rausfinden...bzw. wie deren rekursiv linearisierter Algorithmus aussieht...
Mit TBigNums habe ich schon vor Jahren mal ein bischen rumgespielt. Das war also quasi die Vorgängerversion von DecMath. Hochinteressant einmal soche Info's aus erster Hand zu beziehen :-D
Herzlichen Dank noch einmal an dich Hagen :kiss: , diese Informationen nützen mir definitiv was. Ich muss jetzt erst mal ein wenig Theorie wälzen und rumgurgeln (...ehhh rumkugeln.... ne, rumgoogeln, jetzt habsch's :mrgreen: ). Für jeden weiteren Hinweis, insbesondere zum modularen Fermat Schönhage Strassen Algorithmus, wäre ich selbstverständlich auch weiterhin sehr dankbar.

bis denne

Matthias

[negaH]

Zitat:

Aber für die Multiplikation 2er Zahlen mit je 2^27 Bit soll ich minimal nur 54 Bit Speicherplatz brauchen??? Das klingt niedlich

Hm, entweder mache ich jetzt einen fatalen Denkfehler oder du ;)

Die Zahl 2^(2^27)-1 benötigt exakt 2^27 Bits im Speicher und Ln2(2^2^27) ist nach meinem Wissen 2^27. Die Multiplikation von 2 Zahlen mit 2^27 Bits jeweils ergibt also ein Resulat mit 2^(27*2) Bits.

Ln2(A) + Ln2(B) = Ln2(Resulat) ->
Result := A * B;

Ln2(A) = Anzahl Bits die die Zahl A benötigt.

Ich weiß nicht, aber ich wäre total am Boden zerstört wenn das falsch sein sollte ;)

Gruß Hagen

[MatWur]

jau (rotwerd :duck: ), ich bau' mir jetzt ein Vogelhäuschen aus dem Brett vor meinem Kopf... siehe meine Signatur :mrgreen: nenene, manomanoman... :wall:

bis denne, ich muss wohl erst mal schlafen gehen

Matthias