Zaimplementuj szybką transformację Fouriera w jak najmniejszej liczbie postaci.
Zasady:
- Najkrótsze rozwiązanie wygrywa
- Można założyć, że wejściem jest tablica 1D, której długość jest potęgą dwóch.
- Możesz użyć wybranego algorytmu, ale rozwiązaniem musi być szybka transformata Fouriera, a nie tylko naiwna dyskretna transformata Fouriera (to znaczy, że musi ona mieć asymptotyczny koszt obliczeniowy )
Edytować:
kod powinien implementować standardową szybką transformatę Fouriera, której formę można zobaczyć w równaniu (3) tego artykułu Wolfram ,
- Używanie funkcji FFT z wcześniej istniejącej standardowej biblioteki lub pakietu statystyk jest niedozwolone. Wyzwanie polega na zwięzłym wdrożeniu samego algorytmu FFT.
code-golf
math
complex-numbers
jakevdp
źródło
źródło
FFT
(3 znaki): jest w standardowej bibliotece”? Niektóre przypadki testowe też byłyby dobre.Odpowiedzi:
Mathematica, 95 bajtów
Kolejne wdrożenie Cooley – Tukey FFT z pomocą @ chyaong .
Bez golfa
źródło
#[[;;;;2]]==#[[1;;N;;2]]
i[[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 bajtów
Poprawa po kilku latach. Nadal używa algorytmu Cooley-Tukey FFT.
Zapisano 4 bajty przy użyciu e πi = -1, dzięki @ Leaky Nun .
Wypróbuj online!
Stosowanie
Wyjaśnienie
źródło
Python,
166151150 znakówWykorzystuje to algorytm radole-2 Cooley-Tukey FFT
Testowanie wyniku
źródło
from x import*
isum(([x for x in y] for y in z),[])
jest dłuższy niż[x for y in z for x in y]
.Python 3:
140134113 znakówWersja krótka - krótka i słodka, mieści się w tweecie (dzięki dzięki milom ):
(W Pythonie 2,
/
jest obcinanie podział, gdy obie strony są liczbami całkowitymi. Więc możemy zastąpić(i*4/n)
przez(i*4.0/n)
, który wpada długość do 115 znaków).Długa wersja - większa przejrzystość wnętrza klasycznego Cooley-Tukey FFT:
źródło
e^(-2j * pi * i / n) = (-1)^(2 * i / n) = (1j)^(4 * i / n)
R:
1421339995 bajtówDzięki @Giuseppe za pomoc w goleniu
3236 bajtów!Dodatkową sztuczką jest użycie domyślnych argumentów funkcji głównej, aby utworzyć wystąpienie niektórych zmiennych.
Użycie jest nadal takie samo:
4-letnia wersja o wielkości 133 bajtów:
Z wcięciami:
Wykorzystuje również algorytm Cooleya-Tukeya. Jedynymi sztuczkami są tutaj użycie funkcji,
Recall
która pozwala na rekurencyjność i zastosowanie wektoryzacji R, która znacznie skraca rzeczywiste obliczenia.Stosowanie:
źródło
Recall
używałeś już tej funkcji, ale hej, z perspektywy czasu można grać w golfa! :) +1, bardzo miło.Recall
teraz jest niepotrzebne. Zauważyłem to kilka miesięcy temu, ale byłem zbyt leniwy, aby to zmienić :) Zmodyfikuję to.y
, ale nie zauważyłem, że można go również wykorzystać w tejexp(...)
części.Python, 134
To mocno zapożycza z rozwiązania jakevdp, więc ustawiłem to na wiki społeczności.
Zmiany:
-12 znaków: zabij
t
.-1 char: wykładnik sztuczki,
x*y**-z == x/y**z
(może to pomóc niektórym innym)-2 znak zamienić
and
z*
+1 char:
lambda
ize, zabijanieN
-2 char: użyj
enumerate
zamiastzip(range(len(
źródło
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
zfor s in 1,-1for
lub nawet, jeśli kolejność nie ma znaczeniafor s in-1,1for
.C 259
Problem polega na tym, że takie implementacje są bezużyteczne, a prosty algorytm jest DUŻO szybszy.
źródło
step < n
można zmienić nastep<n
istep * 2
można zmienić nastep*2
.Matlab,
1281181071021019493 bajtyEDIT6: dzięki @algmyr za kolejny bajt!
EDIT5: Wciąż się skraca :) dzięki @sanchises
EDYCJA 4: Tak, -1 znak więcej (mógł również zrobić bez
k
):EDIT2 / 3: Dzięki za @sanchises za dalsze ulepszenia!
EDYCJA: Może wprowadzić pewne ulepszenia i zauważyłem, że stała skalowania nie jest wymagana.
To jest wersja rozszerzona, liczba znaków jest ważna, jeśli usuniesz nowe linie / spacje. (Działa tylko w przypadku wektorów kolumnowych).
źródło
d=
linie w jednym:m=n/2;d=f(Y(2:2:n)).*exp(-pi*i*(0:m-1)/m).';
. Ponadto, należy rozważyć zmianęy=f(Y)
doY=f(Y)
i wyjąć linii 3 (i obiecuję, że nigdy nie zrobię, że poza code-golf)function Y = f(Y)
występują inne wady oprócz nieczytelności?m=n/2
można go usunąć, a zamiast tegom
zastąpić odpowiednio przezn/2
in*2
. A potem, mocno wierzę, program jest tak krótki, jak mógłby być w MATLAB.Galaretka,
31302826 bajtów , niekonkurująceGalaretka powstała po tym wyzwaniu, więc nie konkuruje.
Wykorzystuje algorytm rekurencyjny Cooley-Tukey radix-2. W przypadku wersji bez gry w golfa zobacz moją odpowiedź w Mathematica.
Wypróbuj online lub Zweryfikuj wiele przypadków testowych .
Wyjaśnienie
źródło
C (gcc) ,
188 186 184183 bajtówWypróbuj online!
Nieco mniej golfa
źródło
Pari / GP, 76 znaków
Stosowanie
źródło
Oktawa ,
109 103 101100 bajtówWypróbuj online!
Ooooo, krwawię z tej
rekurencyjnejprzeklętej lambdy. Duża część tego została usunięta z odpowiedzi @ flawr.źródło
Axiom,
259,193,181, 179 bajtówNawet jeśli h (a) zdałby cały test i byłby w porządku jako wpis do tej „konkurencji”, należy wywołać h () lub hlp () poprzez fft () poniżej, aby sprawdzić argumenty . Nie wiem, czy to oprogramowanie może być w porządku, ponieważ widziałem tylko to, co napisali inni, i szukałem sposobu, w jaki mógłby on działać w Axiomie, aby uzyskać jakiś możliwy właściwy wynik. Poniżej niemodyfikowany kod z kilkoma komentarzami:
w kilku widziałem, że h () lub fft () zwróci dokładne rozwiązanie, ale jeśli uproszczenie nie jest dobre, jak w:
wystarczy zmienić typ tylko jednego elementu listy, jak w poniższym piśmie 8. (Float), aby znaleźć przybliżone rozwiązanie:
Napisałem to, widziałem wszystkie inne odpowiedzi, ponieważ w linku strona była zbyt trudna, więc nie wiem, czy ten kod może być poprawny. Nie jestem ekspertem od fft, więc wszystko to może (jest prawdopodobne) być błędne.
źródło
APL (NARS), 58 znaków, 116 bajtów
test
źródło