Seltsame Ergebnisse bei DFT

[3_of_8]

Nachtrag:

AddC und MulC sind die Addition bzw. Multiplikation von komplexen Zahlen, MakeC erstellt eine komplexe Zahl aus den angegebenen Werten. Diese Funktionen sind garantiert richtig implementiert.

a ist der "Eingabevektor" (a1,...,an), der verändert wird.
n ist die Anzahl der Elemente in a.
lo ist hier nicht von Bedeutung, ich werds aus der Parameterliste rausstreichen.
w ist die n-te primitive Einheitswurzel.

f[I] ist das Array, das den Wert von w^I speichert.
b ist der Vektor, der die "ursprünglichen" Werte von a speichert, die bei der Matrixmultiplikation benötigt werden, weil die Werte in a ja verändert werden und die Matrixmultiplikation sonst falsch wäre.

EDIT: Nebenbei bemerkt ist dieser Algorithmus trotz einiger Optimierungen, die ich mir ausgedacht habe, sehr, sehr langsam. Nicht verwunderlich, wenn man bedenkt, dass bei n=2000 einige Millionen (Milliarden?) Additionen und Multiplikationen ausgeführt werden müssen.