AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

FFT für schnelle Multiplikation

Ein Thema von MatWur · begonnen am 22. Feb 2007 · letzter Beitrag vom 28. Feb 2007
 
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#4

Re: FFT für schnelle Multiplikation

  Alt 27. Feb 2007, 22:56
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
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 14:51 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz