Too Fast, Too Fourier: FFT Code Golf

48

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 O(N.logN.) )

Edytować:

  • kod powinien implementować standardową szybką transformatę Fouriera, której formę można zobaczyć w równaniu (3) tego artykułu Wolfram ,

    wprowadź opis zdjęcia tutaj

  • 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.
jakevdp
źródło
3
Jest to nieokreślone. Przynajmniej musisz zdefiniować czynniki normalizacyjne, a także powinieneś mieć świadomość, że wszelka dwuznaczność zostanie umyślnie źle zinterpretowana. Np. Czy „Implement” spełnia odpowiedź „ FFT(3 znaki): jest w standardowej bibliotece”? Niektóre przypadki testowe też byłyby dobre.
Peter Taylor
Czy ma to znaczenie dla kolejności elementów wyjściowych, tj. Czy musimy zaimplementować dekodowanie odwróconego bitu, czy też możemy pozostawić wyjście w zakodowanej kolejności?
Paul R
Zobacz zmiany w regulaminie. Dane wyjściowe powinny być listą / tablicą z wartościami uporządkowanymi zgodnie ze wskaźnikami w standardowym wyrażeniu DFT, o których mowa powyżej.
jakevdp,
2
Czy możesz podać przykładowe dane wejściowe i wyjściowe, abyśmy mogli przetestować nasze wdrożenia?
FUZxxl,
2
Tytuł powinien być „Szybki i Fourier-s” (Szybki i wściekły).
clismique

Odpowiedzi:

12

Mathematica, 95 bajtów

Kolejne wdrożenie Cooley – Tukey FFT z pomocą @ chyaong .

{n=Length@#}~With~If[n>1,Join[+##,#-#2]&[#0@#[[;;;;2]],#0@#[[2;;;;2]]I^Array[-4#/n&,n/2,0]],#]&

Bez golfa

FFT[x_] := With[{N = Length[x]},
  If[N > 1,
    With[{a = FFT[ x[[1 ;; N ;; 2]] ], 
          b = FFT[ x[[2 ;; N ;; 2]] ] * Table[E^(-2*I*Pi*k/N), {k, 0, N/2 - 1}]},
      Join[a + b, a - b]],
    x]]
mile
źródło
1
Myślę #[[;;;;2]]==#[[1;;N;;2]]i [[2;;;;2]]==[[2;;N;;2]].
chyanog
1
101 znaków :With[{L=Length@#},If[L>1,Join[+##,#-#2]&[#0@#[[;;;;2]],#0@#[[2;;;;2]]E^(-2I*Pi(Range[L/2]-1)/L)],#]]&
chyanog
Fajnie, możesz skondensować w sobie inną anonimową funkcję bez konfliktu z funkcją rekurencyjną. Dowiedziałem się również, że Część wypełnia brakujące wskaźniki. Możemy dalej to robić za pomocą Unicode.
mile
9

J, 37 bajtów

_2&(0((+,-)]%_1^i.@#%#)&$:/@|:]\)~1<#

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

   f =: _2&(0((+,-)]%_1^i.@#%#)&$:/@|:]\)~1<#
   f 1 1 1 1
4 0 0 0
   f 1 2 3 4
10 _2j2 _2 _2j_2
   f 5.24626 3.90746 3.72335 5.74429 4.7983 8.34171 4.46785 0.760139
36.9894 _6.21186j0.355661 1.85336j_5.74474 7.10778j_1.13334 _0.517839 7.10778j1.13334 1.85336j5.74474 _6.21186j_0.355661

Wyjaśnienie

_2&(0((+,-)]%_1^i.@#%#)&$:/@|:]\)~1<#  Input: array A
                                    #  Length
                                  1<   Greater than one?
_2&(                            )~     Execute this if true, else return A
_2                            ]\         Get non-overlapping sublists of size 2
    0                       |:           Move axis 0 to the end, equivalent to transpose
                          /@             Reduce [even-indexed, odd-indexed]
                       &$:               Call recursively on each 
                   #                     Get the length of the odd list
                i.@                      Range from 0 to that length exclusive
                    %#                   Divide each by the odd length
             _1^                         Compute (-1)^x for each x
           ]                             Get the odd list
            %                            Divide each in that by the previous
       +                                 Add the even values and modified odd values
         -                               Subtract the even values and modified odd values
        ,                                Join the two lists and return
mile
źródło
1
Zobacz także: blog.ndpar.com/2014/10/11/dft-j
FUZxxl
9

Python, 166 151 150 znaków

Wykorzystuje to algorytm radole-2 Cooley-Tukey FFT

from math import*
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
a+s*b/e**(2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

Testowanie wyniku

>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True
jakevdp
źródło
1
2 rzeczy: zwykle najlepiej jest go używać from x import*i sum(([x for x in y] for y in z),[])jest dłuższy niż [x for y in z for x in y].
stoisko
1
Dzięki - to oszczędza 15 znaków! 11 więcej i jest to tweet.
jakevdp
Och, to zdecydowanie możliwe. Często, gdy znajdziesz jedną poprawę, stara staje się przeszkodą.
kabina
5

Python 3: 140 134 113 znaków

Wersja krótka - krótka i słodka, mieści się w tweecie (dzięki dzięki milom ):

from math import*
def f(v):
 n=len(v)
 if n<2:return v
 a,b=f(v[::2])*2,f(v[1::2])*2;return[a[i]+b[i]/1j**(i*4/n)for i in range(n)]

(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:

import cmath
def transform_radix2(vector):
    n = len(vector)
    if n <= 1:  # Base case
        return vector
    elif n % 2 != 0:
        raise ValueError("Length is not a power of 2")
    else:
        k = n // 2
        even = transform_radix2(vector[0 : : 2])
        odd  = transform_radix2(vector[1 : : 2])
        return [even[i % k] + odd[i % k] * cmath.exp(i * -2j * cmath.pi / n) for i in range(n)]
Nayuki
źródło
1
Skrócono do 113 bajtów przy użyciue^(-2j * pi * i / n) = (-1)^(2 * i / n) = (1j)^(4 * i / n)
mil
@miles Bardzo imponująca obserwacja, dziękuję! Po kilkuletniej implementacji DFT miałem obsesję na punkcie sin / cos / exp i zapomniałem, że można użyć prostych mocy i. Zredagowałem swoją odpowiedź, aby uwzględnić nowy wgląd i podziękować.
Nayuki,
5

R: 142 133 99 95 bajtów

Dzięki @Giuseppe za pomoc w goleniu 32 36 bajtów!

f=function(x,n=sum(x|1),y=1:(n/2)*2)`if`(n>1,f(x[-y])+c(b<-f(x[y]),-b)*exp(-2i*(y/2-1)*pi/n),x)

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:

x = c(1,1,1,1)
f(x)
[1] 4+0i 0+0i 0+0i 0+0i

4-letnia wersja o wielkości 133 bajtów:

f=function(x){n=length(x);if(n>1){a=Recall(x[seq(1,n,2)]);b=Recall(x[seq(2,n,2)]);t=exp(-2i*(1:(n/2)-1)*pi/n);c(a+b*t,a-b*t)}else{x}}

Z wcięciami:

f=function(x){
    n=length(x)
    if(n>1){
        a=Recall(x[seq(1,n,2)])
        b=Recall(x[seq(2,n,2)])
        t=exp(-2i*(1:(n/2)-1)*pi/n)
        c(a+b*t,a-b*t)
        }else{x}
    }

Wykorzystuje również algorytm Cooleya-Tukeya. Jedynymi sztuczkami są tutaj użycie funkcji, Recallktóra pozwala na rekurencyjność i zastosowanie wektoryzacji R, która znacznie skraca rzeczywiste obliczenia.

Stosowanie:

x = c(1,1,1,1)
f(x)
[1] 4+0i 0+0i 0+0i 0+0i
plannapus
źródło
1
Cztery lata później zmniejszamy go do 101 bajtów . Nie jestem w 100% pewien, dlaczego Recallużywałeś już tej funkcji, ale hej, z perspektywy czasu można grać w golfa! :) +1, bardzo miło.
Giuseppe,
Tak, Recallteraz jest niepotrzebne. Zauważyłem to kilka miesięcy temu, ale byłem zbyt leniwy, aby to zmienić :) Zmodyfikuję to.
plannapus
Bardzo dobrze! Wycisnąłem kolejne 4 bajty! , stawiając to na równi z Mathematica.
Giuseppe,
Dzięki! Myślałem o rozstawieniu y, ale nie zauważyłem, że można go również wykorzystać w tej exp(...)części.
plannapus
4

Python, 134

To mocno zapożycza z rozwiązania jakevdp, więc ustawiłem to na wiki społeczności.

from math import*
F=lambda x:x*(len(x)<2)or[a+s*b/e**(2j*pi*n/len(x))for s in(1,-1)for n,(a,b)in
enumerate(zip(F(x[::2]),F(x[1::2])))]

Zmiany:

-12 znaków: zabij t.

def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return ... in zip(range(N),*t)]
def F(x):N=len(x);return ... in zip(range(N),F(x[::2]),F(x[1::2]))]

-1 char: wykładnik sztuczki, x*y**-z == x/y**z (może to pomóc niektórym innym)

...[a+s*b*e**(-2j*pi*n/N)...
...[a+s*b/e**(2j*pi*n/N)...

-2 znak zamienić andz*

...return N<2and x or[
...return x*(N<2)or[

+1 char: lambdaize, zabijanieN

def F(x):N=len(x);return x*(N<2)or[a+s*b/e**(2j*pi*n/N) ... zip(range(N) ...
F=lambda x:x*(len(x)<2)or[a+s*b/e**(2j*pi*n/len(x)) ... zip(range(len(x)) ...

-2 char: użyj enumeratezamiastzip(range(len(

...for(n,a,b)in zip(range(len(x)),F(x[::2]),F(x[1::2]))]
...for n,(a,b)in enumerate(zip(F(x[::2]),F(x[1::2])))]
boothby
źródło
Myślę, że nie jest to już szybka transformacja Fouriera, ale ... przez „zabicie t” dodałeś kilka niepotrzebnych obliczeń, które przenoszą ją z O [N log (N)] na O [N ^ 2]
jakevdp
Wygląda na to, że nie mogę głosować za własnym postem. Masz rację, wymieniłem kolejność pętli i zabiłem występ. Zostawię to na razie, na wypadek, gdyby znalazłem sposób, aby to naprawić.
stoisko
101 bajtów zf=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))]
milami
Można wymienić for s in(1,-1)forz for s in 1,-1forlub nawet, jeśli kolejność nie ma znaczenia for s in-1,1for.
Jonathan Frech,
4

C 259

typedef double complex cplx;
void fft(cplx buf[],cplx out[],int n,int step){
if(step < n){
fft(out, buf,n, step * 2);
fft(out+step,buf+step,n,step*2);
for(int i=0;i<n;i+=2*step){
cplx t=cexp(-I*M_PI*i/n)*out[i+step];
buf[i/2]=out[i]+t;
buf[(i+n)/2]=out[i]-t;
}}}

Problem polega na tym, że takie implementacje są bezużyteczne, a prosty algorytm jest DUŻO szybszy.

sanaris
źródło
2
Możesz usunąć więcej białych znaków, aby uzyskać mniejszą liczbę znaków, na przykład step < nmożna zmienić na step<ni step * 2można zmienić na step*2.
ProgramFOX
2
wszystkie zmienne i funkcje oraz
2
Ktoś zasugerował kilka ulepszeń w tym zakresie. Spójrz na nie tutaj: codegolf.stackexchange.com/review/suggested-edits/17119
Justin
1
Możesz usunąć wszystkie nowe wiersze, nowe wiersze są bezużyteczne w C
TuxCrafting,
@ TùxCräftîñg Nie wszystkie nowe linie są bezużyteczne. Są one potrzebne do dyrektyw takich jak #include, #define, #if itp.
Nayuki,
3

Matlab, 128 118 107 102 101 94 93 bajty

EDIT6: dzięki @algmyr za kolejny bajt!

function Y=f(Y);
n=numel(Y);
k=2:2:n;
if k;
   c=f(Y(k-1));
   d=f(Y(k)).*i.^(2*(2-k)/n);
   Y=[c+d;c-d];
end

EDIT5: Wciąż się skraca :) dzięki @sanchises

function Y=f(Y)
n=numel(Y);
k=2:2:n;
if k;
   c=f(Y(k-1));
   d=f(Y(k)).*(-1).^((2-k)/n);
   Y=[c+d;c-d];
end

EDYCJA 4: Tak, -1 znak więcej (mógł również zrobić bez k):

function Y=f(Y)
n=numel(Y);
if n>1;
   k=2:2:n;
   c=f(Y(k-1));
   d=f(Y(k)).*(-1).^((k/2-1)*2/n)';
   Y=[c+d;c-d];
end

EDIT2 / 3: Dzięki za @sanchises za dalsze ulepszenia!

function Y=f(Y)
n=numel(Y);  
if n>1;
   c=f(Y(1:2:n));
   d=f(Y(2:2:n)).*(-1).^(-(0:n/2-1)*2/n).';
   Y=[c+d;c-d]; 
end

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).

function y=f(Y)
n=numel(Y);  
y=Y;
if n>1;
   c=f(Y(1:2:n));
   d=f(Y(2:2:n));
   n=n/2;
   d=d.*exp(-pi*i*(0:n-1)/n).';
   y=[c+d;c-d]; 
end
wada
źródło
Wskazówka: Można łączyć dwie 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)do Y=f(Y)i wyjąć linii 3 (i obiecuję, że nigdy nie zrobię, że poza code-golf)
Sanchises
Oh dziękuję! Czy function Y = f(Y)występują inne wady oprócz nieczytelności?
flawr
Cóż, MATLAB nigdy nie będzie narzekać na wartość zwrotu, nawet jeśli Y nigdy się nie zmieni. Jest jednak nieco szybszy, więc wydaje mi się, że wcale nie jest taki zły do ​​niektórych celów (tj. Funkcja, która prawie nigdy nie zmienia zmiennej wejściowej)
Sanchises,
Teraz, aby golić więcej: m=n/2można go usunąć, a zamiast tego mzastąpić odpowiednio przez n/2i n*2. A potem, mocno wierzę, program jest tak krótki, jak mógłby być w MATLAB.
Sanchises
1
A potem, mocno wierzę, program jest tak krótki, jak mógłby być w MATLAB. - Sanchises 8 marca 15 o 21:05 Słynne ostatnie słowa ...
Sanchises
2

Galaretka, 31 30 28 26 bajtów , niekonkurujące

LḶ÷$N-*×,N$+ḷF
s2Z߀ç/µ¹Ṗ?

Galaretka 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

LḶ÷$N-*×,N$+ḷF  Helper link. Input: lists A and B
L               Get the length of A
   $            Operate on that length
 Ḷ                Make a range [0, 1, ..., length-1]
  ÷               Divide each by length
    N           Negate each
     -          The constant -1
      *         Compute -1^(x) for each x in that range
       ×        Multiply elementwise between that range and B, call it B'  
          $     Operate on that B'
         N        Negate each
        ,         Make a list [B', -B']
            ḷ   Get A
           +    Add vectorized, [B', -B'] + A = [A+B', A-B']
             F  Flatten that and return

s2Z߀ç/µ¹Ṗ?  Main link. Input: list X
         Ṗ   Curtail - Make a copy of X with the last value removed
          ?  If that list is truthy (empty lists are falsey)
       µ       Parse to the left as a monad
s2             Split X into sublists of length 2
  Z            Transpose them to get [even-index, odd-index]
   ߀          Call the main link recursively on each sublist
     ç/        Call the helper link as a dyad on the sublists and return
             Else
        ¹      Identity function on X and return
mile
źródło
2

C (gcc) , 188 186 184 183 bajtów

#define d(a,b,c)f(a,b,c,1,0)
f(a,b,c,n,k)_Complex*a,*b;{_Complex z[c];*b=*a;if(n<c)for(f(a,z,c,n*2),f(a+n,z+n,c,n*2);k<c;k+=n*2)b[k+c>>1]=z[k]*2-(b[k/2]=z[k]+z[k+n]/cpow(1i,2.*k/c));}

Wypróbuj online!

Nieco mniej golfa

#define d(a,b,c)f(a,b,c,1,0)
f(a,b,c,n,k)_Complex*a,*b;{
  _Complex z[c];
  *b=*a;
  if(n<c)
    for(f(a,z,c,n*2),f(a+n,z+n,c,n*2);k<c;k+=n*2)
      b[k+c>>1]=z[k]*2-(b[k/2]=z[k]+z[k+n]/cpow(1i,2.*k/c));
}
sufitowy
źródło
1

Pari / GP, 76 znaków

X(v)=my(t=-2*Pi*I/#v,s);vector(#v,k,s=t*(k-1);sum(n=0,#v-1,v[n+1]*exp(s*n)))

Stosowanie

X([1,1,1,1])
%2 = [4.000000000000000000000000000, 0.E-27 + 0.E-28*I, 0.E-28 + 0.E-27*I, 0.E-27 + 0.E-28*I]
P̲̳x͓L̳
źródło
3
Czy to nie jest naiwny DFT? (tj. theta (N ^ 2))
mile
1

Oktawa , 109 103 101 100 bajtów

f(f=@(f)@(x,n=rows(x)){@(d=f(f)(x(k=2:2:n)).*i.^((k*2-4)/n)')[d+(c=f(f)(x(k-1)));c-d],x}{1+(n<2)}())

Wypróbuj online!

Ooooo, krwawię z tej rekurencyjnej przeklętej lambdy. Duża część tego została usunięta z odpowiedzi @ flawr.

f(                                          % lambda function
  f=@(f)                                    % defined in its own argument list, 
                                            % accepts itself as parameter (for recursion)
    @(x,n=rows(x)){                         % calls another lambda,
                                            % 2nd parameter is just to define a variable
      @(d=f(f)(x(k=2:2:n)).*i.^((k*2-4)/n)')% 1/4 of FFT (argument just defines a variable)
        [d+(c=f(f)(x(k-1)));                % 2/4 of FFT
         c-d                                % 4/4 of FFT
        ],                                  % This is in a @()[] to inhibit evaluation
                                            % unless actually called
      x                                     % FFT of length 1
    }{1+(n<2)}                              % if len(x)==1, return x
                                            % else return [d+c;c-d]
  ()                                        % this is probably important too
)
sufitowy
źródło
Nie rozumiem, co zrobiłeś, ale bardzo mi się podoba.
flawr
0

Axiom, 259 , 193 , 181 , 179 bajtów

L(g,n,f)==>[g for i in 1..n|f]
h(a)==(n:=#a;n=1=>a;c:=h(L(a.i,n,odd? i));d:=h(L(a.i,n,even? i));n:=n/2;t:=1>0;v:=L(d.i*%i^(-2*(i-1)/n),n,t);append(L(c.i+v.i,n,t),L(c.i-v.i,n,t)))

Nawet 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:

-- L(g,n,f)==>[g for i in 1..n|f]
-- this macro L, build one List from other list, where in g, there is the generic element of index i
-- (as a.i, or a.i*b.i or a.i*4), n build 1..n that is the range of i, f is the condition 
-- for insert the element in the list result.

hlp(a)==
    n:=#a;n=1=>a
    -- L(a.i,n,odd? i)  it means build a list getting "even indices i of a.i as starting from index 0" [so even is odd and odd is even]
    -- L(a.i,n,even? i) it means build a list getting "odd  indices i of a.i as starting from index 0"
    c:=hlp(L(a.i,n,odd? i));d:=hlp(L(a.i,n,even? i))
    n:=n/2;t:=1>0
    v:=L(d.i*%i^(-2*(i-1)/n),n,t)
    append(L(c.i+v.i,n,t),L(c.i-v.i,n,t))

-- Return Fast Fourier transform of list a, in the case #a=2^n
fft(a)==(n:=#a;n=0 or gcd(n,2^30)~=n=>[];hlp(a))

(5) -> h([1,1,1,1])
   (5)  [4,0,0,0]
                                    Type: List Expression Complex Integer
(6) -> h([1,2,3,4])
   (6)  [10,- 2 + 2%i,- 2,- 2 - 2%i]
                                    Type: List Expression Complex Integer
(7) -> h([5.24626,3.90746,3.72335,5.74429,4.7983,8.34171,4.46785,0.760139])
   (7)
   [36.989359, - 6.2118552150 341603904 + 0.3556612739 187363298 %i,
    1.85336 - 5.744741 %i, 7.1077752150 341603904 - 1.1333387260 812636702 %i,
    - 0.517839, 7.1077752150 341603904 + 1.1333387260 812636702 %i,
    1.85336 + 5.744741 %i,
    - 6.2118552150 341603904 - 0.3556612739 187363298 %i]
                                      Type: List Expression Complex Float
(8) -> h([%i+1,2,%i-2,9])
   (8)  [10 + 2%i,3 + 7%i,- 12 + 2%i,3 - 7%i]
                                    Type: List Expression Complex Integer

w kilku widziałem, że h () lub fft () zwróci dokładne rozwiązanie, ale jeśli uproszczenie nie jest dobre, jak w:

(13) -> h([1,2,3,4,5,6,7,8])
   (13)
                    +--+                                   +--+
        (- 4 + 4%i)\|%i  - 4 + 4%i             (- 4 - 4%i)\|%i  - 4 + 4%i
   [36, --------------------------, - 4 + 4%i, --------------------------, - 4,
                    +--+                                   +--+
                   \|%i                                   \|%i
            +--+                                   +--+
    (- 4 + 4%i)\|%i  + 4 - 4%i             (- 4 - 4%i)\|%i  + 4 - 4%i
    --------------------------, - 4 - 4%i, --------------------------]
                +--+                                   +--+
               \|%i                                   \|%i
                                    Type: List Expression Complex Integer

wystarczy zmienić typ tylko jednego elementu listy, jak w poniższym piśmie 8. (Float), aby znaleźć przybliżone rozwiązanie:

(14) -> h([1,2,3,4,5,6,7,8.])
   (14)
   [36.0, - 4.0000000000 000000001 + 9.6568542494 923801953 %i, - 4.0 + 4.0 %i,
    - 4.0 + 1.6568542494 92380195 %i, - 4.0, - 4.0 - 1.6568542494 92380195 %i,
    - 4.0 - 4.0 %i, - 4.0 - 9.6568542494 923801953 %i]
                                      Type: List Expression Complex Float

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.

RosLuP
źródło
0

APL (NARS), 58 znaków, 116 bajtów

{1≥k←≢⍵:⍵⋄(∇⍵[y∼⍨⍳k])(+,-)(∇⍵[y←2×⍳t])×0J1*t÷⍨2-2×⍳t←⌊k÷2}

test

  f←{1≥k←≢⍵:⍵⋄(∇⍵[y∼⍨⍳k])(+,-)(∇⍵[y←2×⍳t])×0J1*t÷⍨2-2×⍳t←⌊k÷2}
  f 1 1 1 1
4J0 0J0 0J0 0J0 
  f 1 2 3 4
10J0 ¯2J2 ¯2J0 ¯2J¯2 
  f 1J1 2 ¯2J1  9
10J2 3J7 ¯12J2 3J¯7 
  f 5.24626,3.90746,3.72335,5.74429,4.7983,8.34171,4.46785,0.760139
36.989359J0 ¯6.211855215J0.3556612739 1.85336J¯5.744741 7.107775215J¯1.133338726 ¯0.517839J0 
  7.107775215J1.133338726 1.85336J5.744741 ¯6.211855215J¯0.3556612739 
RosLuP
źródło