Komplexe Fourier-Transformation
-
Hallo,
ich habe ein kleines Problem. Zurzeit beschäftige ich mich mit dem Fürer-Algorithmus für große Zahlen.
Es geht um den Half-FFT auf Seite 16
Ein AuszugIm Kommentar von Modular-Integer-Multiplication wird ζ definiert. Und zwar als Komplexe-Zahl. Wenn ich das richtig verstanden habe, müsste die Übersetzung lauten:
ζ = 2N -te Einheitswurzel mit dem Wert e^(i π (2k + 1) / N) bei e^(i π (2k + 1)/P)
das gilt für: k = 0 und k < Pn: Die max. Länge des Produktes im Dualsystem. Die Zahl wird zur nächsten Zahl (Power 2) aufgerundet
P: Die Länge von n im Dualsystem. Ebenfalls aufgerundet
N = 2n/P^2So, imm weiteren Algo. wird nun gerechnet. Ich gehe hier nicht direkt darauf ein, da dies nur vom eigentlichen Problem ablenken würde.
a: Eine Zahlfor(k=0; k<N; k++)
a[k] * ζ^kDas Problem ist ζ. Leider hatten wir keine Fourier-Transformation in Mathematik nicht mehr. Wurde gestrichen
Ich verstehe nicht ganz, was Zeta genau ist und wie ich es Einsetze. Das Potenzieren von komplexen Zahle ist mir klar, aber die Definition von zeta eben nicht.Kann mir hier jemand weiterhelfen?
Frohe Weihnachten
Thomas
-
