Implementieren Sie die schnelle Fourier-Transformation in möglichst wenigen Zeichen.
Regeln:
- Kürzeste Lösung gewinnt
- Es kann angenommen werden, dass der Eingang ein 1D-Array ist, dessen Länge eine Zweierpotenz ist.
- Sie können den Algorithmus Ihrer Wahl verwenden, aber die Lösung muss tatsächlich eine schnelle Fouriertransformation sein, nicht nur eine naive diskrete Fouriertransformation (dh es müssen asymptotische Berechnungskosten von ).
Bearbeiten:
Der Code sollte die standardmäßige schnelle Fourier-Vorwärtstransformation implementieren, deren Form in Gleichung (3) dieses Wolfram-Artikels zu sehen ist.
- Die Verwendung einer FFT-Funktion aus einer vorhandenen Standardbibliothek oder einem Statistikpaket ist nicht zulässig. Hier besteht die Herausforderung darin, den FFT-Algorithmus selbst kurz und bündig zu implementieren .
code-golf
math
complex-numbers
jakevdp
quelle
quelle
FFT
(3 Zeichen): Es ist in der Standardbibliothek"? Einige Testfälle wären auch gut.Antworten:
Mathematica, 95 Bytes
Eine weitere Implementierung der Cooley-Tukey-FFT mit Hilfe von @ chyaong .
Ungolfed
quelle
#[[;;;;2]]==#[[1;;N;;2]]
und[[2;;;;2]]==[[2;;N;;2]]
.With[{L=Length@#},If[L>1,Join[+##,#-#2]&[#0@#[[;;;;2]],#0@#[[2;;;;2]]E^(-2I*Pi(Range[L/2]-1)/L)],#]]&
J, 37 Bytes
Eine Verbesserung nach ein paar Jahren. Verwendet weiterhin den Cooley-Tukey-FFT-Algorithmus.
4 Bytes mit e πi = -1 dank @ Leaky Nun gespeichert .
Probieren Sie es online!
Verwendungszweck
Erläuterung
quelle
Python,
166151150 ZeichenHierbei wird der Cooley-Tukey-FFT-Algorithmus von Radix-2 verwendet
Das Ergebnis testen
quelle
from x import*
undsum(([x for x in y] for y in z),[])
ist länger als[x for y in z for x in y]
.Python 3:
140134113 ZeichenKurze Version - kurz und süß, passt in einen Tweet (dank Meilen ):
(In Python 2
/
wird die Division abgeschnitten, wenn beide Seiten Ganzzahlen sind. Wir ersetzen also(i*4/n)
durch(i*4.0/n)
, wodurch die Länge auf 115 Zeichen erhöht wird.)Lange Version - mehr Klarheit in die Interna des klassischen Cooley-Tukey FFT:
quelle
e^(-2j * pi * i / n) = (-1)^(2 * i / n) = (1j)^(4 * i / n)
R:
1421339995 BytesVielen Dank an @ Giuseppe für die Hilfe beim Rasieren von
32 bis36 Bytes!Ein zusätzlicher Trick besteht darin, die Standardargumente der Hauptfunktion zu verwenden, um einige Variablen zu instanziieren.
Die Verwendung ist immer noch die gleiche:
4 Jahre alte Version mit 133 Bytes:
Mit Einrückungen:
Es wird auch der Cooley-Tukey-Algorithmus verwendet. Die einzigen Tricks hier sind die Verwendung von Funktionen
Recall
, die Rekursivität ermöglichen, und die Verwendung von R-Vektorisierung, die die tatsächliche Berechnung erheblich verkürzen.Verwendungszweck:
quelle
Recall
diese Funktion verwendet haben, aber hey, es ist im Nachhinein einfach, Golf zu spielen! :) +1, sehr nett.Recall
ist jetzt in der Tat unnötig. Ich habe das vor ein paar Monaten bemerkt, war aber zu faul, um es zu ändern :) Ich werde es ändern.y
, aber ich habe nicht bemerkt, dass es auch für dasexp(...)
Teil verwendet werden könnte.Python, 134
Dies basiert stark auf der Lösung von jakevdp, daher habe ich dieses Wiki auf ein Community-Wiki gesetzt.
Änderungen:
-12 Zeichen: töten
t
.-1 Zeichen: Exponententrick
x*y**-z == x/y**z
(dies könnte einigen anderen helfen)-2 Zeichen: Ersetzen
and
durch*
+1
lambda
Zeichen : Ize, tötenN
-2 Zeichen: Verwenden Sie
enumerate
anstelle vonzip(range(len(
quelle
f=lambda x:x*(len(x)<2)or[u+v/1j**(4*i/len(x))for i,(u,v)in enumerate(zip(f(x[::2])*2,f(x[1::2])*2))]
for s in(1,-1)for
mitfor s in 1,-1for
oder sogar, wenn Reihenfolge keine Rolle spielt,for s in-1,1for
.C 259
Das Problem ist, dass solche Implementierungen nutzlos sind und der einfache Algorithmus VIEL schneller ist.
quelle
step < n
kann instep<n
undstep * 2
in geändert werdenstep*2
.Matlab,
1281181071021019493 BytesEDIT6: danke @algmyr für ein weiteres Byte!
EDIT5: Immer noch kürzer :) dank @sanchises
EDIT4: Yay, -1 Zeichen mehr (hätte auch ohne das gehen können
k
):EDIT2 / 3: Danke für @sanchises für weitere Verbesserungen!
BEARBEITEN: Konnte einige Verbesserungen vornehmen und stellte fest, dass die Skalierungskonstante nicht erforderlich ist.
Dies ist die erweiterte Version. Die Anzahl der Zeichen ist gültig, wenn Sie die Zeilenumbrüche / Leerzeichen entfernen. (Funktioniert nur für Spaltenvektoren.)
quelle
d=
Linien in einem:m=n/2;d=f(Y(2:2:n)).*exp(-pi*i*(0:m-1)/m).';
. Darüber hinaus halten Wechsely=f(Y)
zuY=f(Y)
und entfernen Linie 3 (und versprechen Sie nie , dass außerhalb von Code-Golf tun)function Y = f(Y)
es andere Nachteile als Unlesbarkeit?m=n/2
könnte entfernt und stattdessenm
durchn/2
undn*2
ersetzt werden. Und dann glaube ich fest daran, dass das Programm so kurz ist, wie es in MATLAB sein könnte.Jelly,
31302826 Bytes , nicht konkurrierendJelly wurde nach dieser Herausforderung entwickelt und ist daher nicht konkurrierend.
Dies verwendet den rekursiven Cooley-Tukey-Radix-2-Algorithmus. Für eine Version ohne Golf siehe meine Antwort in Mathematica.
Probieren Sie es online aus oder überprüfen Sie mehrere Testfälle .
Erläuterung
quelle
C (gcc) ,
188 186 184183 BytesProbieren Sie es online!
Etwas weniger golfen
quelle
Pari / GP, 76 Zeichen
Verwendungszweck
quelle
Oktave ,
109 103 101100 BytesProbieren Sie es online!
Ooooo bluten meine Augen von diesem
rekursivenverfluchten Lambda. Große Teile davon wurden aus der Antwort von @flawr gestrichen.quelle
Axiom,
259,193,181, 179 BytesSelbst wenn h (a) den gesamten Test bestehen könnte und als Eintrag für diesen "Wettbewerb" in Ordnung wäre, muss man unten h () oder hlp () bis fft () aufrufen, um die Argumente zu überprüfen . Ich weiß nicht, ob diese Software in Ordnung ist, weil ich nur gesehen habe, was andere geschrieben haben, und nach der Art und Weise gesucht habe, wie sie in Axiom ausgeführt werden kann, um ein mögliches richtiges Ergebnis zu erhalten. Unter ungolfed Code mit ein paar Kommentaren:
In den wenigen Fällen, in denen ich h () oder fft () gesehen hatte, würde die exakte Lösung zurückgegeben, aber wenn die Vereinfachung nicht gut ist, wie in:
als es genug ist, ändern Sie den Typ von nur einem Element der Liste, wie im folgenden Schreiben von 8. (Float), um die ungefähre Lösung zu finden:
Ich habe es geschrieben, alle anderen Antworten gesehen, weil es in dem Link auf der Seite zu schwierig war, so dass ich nicht weiß, ob dieser Code richtig sein kann. Ich bin kein FFT-Experte, also kann all dies (es ist wahrscheinlich) falsch sein.
quelle
APL (NARS), 58 Zeichen, 116 Byte
Prüfung
quelle