Schnelle Fourier-Transformation

8

Ich muss zwei Polynome multiplizieren, die jeweils kleine ganzzahlige Koeffizienten haben. Ich brauche eine schnelle FFT-Routine in C / C ++, die sie falten kann. Ich habe mehrere Bibliotheken gesehen, aber sie scheinen zu groß zu sein, verteilt auf mehrere Dateien. Wichtig ist, dass ich Code brauche, der nicht zu lang ist und sehr einfach in einer einzigen .c/.cpp -Datei verwendet und kompiliert werden kann.

  1. FFT sollte mindestens für echte Eingaben optimiert werden, wenn nicht kleine ganze Zahlen.
  2. Radix 4-Implementierung, falls verfügbar, wäre auch in Ordnung.
  3. Das Kompilieren sollte keine speziellen Kompilierungsflags enthalten, da die Kompilierung des Programms in einer externen Umgebung erfolgen muss, die ich nicht kontrollieren kann.

Einer, der sehr gut zu meinen Bedürfnissen passt, ist hier . Aber ich brauche etwas doppelt so schnell.

    
Nikhil Garg 10.03.2011, 04:30
quelle

2 Antworten

12

Für eine einfache und benutzerfreundliche FFT-Implementierung versuchen Sie KissFFT . Wenn Sie jedoch absolute Höchstleistung benötigen und sich ein wenig Komplexität nicht stört, dann muss es FFTW sein.

    
Paul R 10.03.2011, 08:24
quelle
2

Ich habe die Funktion smbFft von diesem Beispiel auf DspDimension an meine Bedürfnisse in der Vergangenheit angepasst.

    
LnxPrgr3 10.03.2011 04:49
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Welche CPUs unterstützen den MOVBE-Befehl?