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...
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
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
)?
Vielen Dank schon im vorraus für jede Lösungshife
Matthias