Problem bei FFT

[3_of_8]

Was ist eine FFTw? O_o

Also, ich sags nochmal so: Eine FFT ist ein Spezialfall einer DFT, die auf dem Divide and Conquer-Verfahren beruht (das kennen wir aus der Schönhagen-Strasse-Matrixmultiplikation oder dem Quicksort-Algorithmus). Divide-and-Conquer-Algorithmen funktionieren nur mit Zweierpotenzen. Ich hab das ganze in dem Fall so geschrieben, dass die FFT solange wie möglich angewandt wird (also so oft wie möglich durch zwei geteilt wird) und dann DFTs ausgeführt werden. Bei Zahlen, die mit 2 teilerfremd sind, muss also immer eine DFT angewandt werden. Das ist der worst-case. Bei Zweierpotenzen kann komplett eine FFT angewandt werden, wodurch man eine Laufzeit von, ich glaube log n oder n log n oder sowas in der Art hat. Also wenn irgendwie möglich, sollte man diese Funktion immer mit Zweierpotenzen aufrufen.