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
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
. 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 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 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
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
Herzlichen Dank noch einmal an dich Hagen
, 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
). 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