Terlalu Cepat, Terlalu Fourier: Golf Kode FFT

48

Terapkan Fast Fourier Transform dalam karakter sesedikit mungkin.

Aturan:

  • Solusi terpendek menang
  • Dapat diasumsikan bahwa input adalah array 1D yang panjangnya adalah kekuatan dua.
  • Anda dapat menggunakan algoritme pilihan Anda, tetapi solusinya harus benar-benar berupa Fast Fourier Transform, bukan hanya Transformier Fourier Naif yang naif (yaitu, ia harus memiliki biaya perhitungan asimptotik O(NlogN) )

Sunting:

  • kode harus mengimplementasikan Fast Fourier Transform standar, yang bentuknya dapat dilihat pada persamaan (3) artikel Wolfram ini ,

    masukkan deskripsi gambar di sini

  • Menggunakan fungsi FFT dari pustaka standar atau paket statistik yang sudah ada tidak diperbolehkan. Tantangannya di sini adalah mengimplementasikan algoritma FFT secara ringkas .
jakevdp
sumber
3
Ini tidak ditentukan secara spesifik. Paling tidak Anda perlu mendefinisikan faktor-faktor normalisasi, dan Anda juga harus menyadari bahwa ambiguitas apa pun akan disalahartikan dengan sengaja. Misalnya "Implement" puas dengan jawabannya " FFT(3 karakter): ada di perpustakaan standar"? Beberapa test case juga bagus.
Peter Taylor
Apakah itu penting tentang urutan elemen output, yaitu apakah kita perlu menerapkan pembalikan bit terbalik atau dapatkah kita meninggalkan output dalam urutan acak?
Paul R
Lihat hasil edit aturan. Keluaran harus berupa daftar / larik dengan nilai yang diurutkan sesuai dengan indeks dalam ekspresi DFT standar, yang dirujuk di atas.
jakevdp
2
Bisakah Anda memposting beberapa contoh input dan output sehingga kami dapat menguji implementasi kami?
FUZxxl
2
Judul seharusnya "Fast and Fourier-s" (Fast and Furious).
clismique

Jawaban:

12

Mathematica, 95 byte

Implementasi lain dari Cooley – Tukey FFT dengan bantuan dari @ chyaong .

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

Tidak disatukan

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]]
mil
sumber
1
Saya pikir #[[;;;;2]]==#[[1;;N;;2]]dan [[2;;;;2]]==[[2;;N;;2]].
chyanog
1
101 karakter :With[{L=Length@#},If[L>1,Join[+##,#-#2]&[#0@#[[;;;;2]],#0@#[[2;;;;2]]E^(-2I*Pi(Range[L/2]-1)/L)],#]]&
chyanog
Bagus, Anda dapat menyingkat fungsi anonim lain di dalamnya tanpa bertentangan dengan yang rekursif. Juga belajar bahwa Bagian mengisi indeks yang hilang. Kita bisa mengambilnya lebih jauh menggunakan Unicode.
mil
9

J, 37 byte

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

Perbaikan setelah beberapa tahun. Masih menggunakan algoritma Cooley-Tukey FFT.

Disimpan 4 byte menggunakan e πi = -1, terima kasih kepada @ Leaky Nun .

Cobalah online!

Pemakaian

   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

Penjelasan

_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
mil
sumber
1
Lihat juga, ini: blog.ndpar.com/2014/10/11/dft-j
FUZxxl
9

Python, 166 151 150 karakter

Ini menggunakan algoritme radix-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)]

Menguji hasilnya

>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True
jakevdp
sumber
1
2 hal: biasanya lebih baik digunakan from x import*, dan sum(([x for x in y] for y in z),[])lebih lama dari itu [x for y in z for x in y].
stan
1
Terima kasih - menghemat 15 karakter! 11 lebih dan itu tweet.
jakevdp
Oh, itu pasti mungkin. Seringkali ketika Anda menemukan satu peningkatan, yang lama menjadi batu sandungan.
stan
5

Python 3: 140 134 113 karakter

Versi pendek - pendek dan manis, pas di tweet (dengan terimakasih kepada miles ):

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

(Dalam Python 2, /memotong divisi ketika kedua belah pihak adalah bilangan bulat. Jadi kita ganti (i*4/n)dengan (i*4.0/n), yang menabrak panjangnya menjadi 115 karakter.)

Versi panjang - kejelasan lebih lanjut ke bagian dalam FFT Cooley-Tukey klasik:

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
sumber
1
Dipendekkan menjadi 113 byte menggunakane^(-2j * pi * i / n) = (-1)^(2 * i / n) = (1j)^(4 * i / n)
mil
@miles Pengamatan yang sangat mengesankan, terima kasih! Setelah berulang kali menerapkan DFT selama lebih dari satu dekade, saya terobsesi dengan sin / cos / exp dan lupa bahwa kekuatan sederhana dari saya dapat digunakan. Saya mengedit jawaban saya untuk memasukkan wawasan baru dan memuji Anda.
Nayuki
5

R: 142 133 99 95 byte

Terima kasih kepada @Giuseppe karena membantu saya menghemat 32 36 byte!

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)

Trik tambahan di sini adalah dengan menggunakan argumen default fungsi utama untuk instantiate beberapa variabel.
Penggunaannya masih sama:

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

Versi 4 tahun pada 133 byte:

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}}

Dengan lekukan:

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}
    }

Ini juga menggunakan algoritma Cooley-Tukey. Satu-satunya trik di sini adalah penggunaan fungsi Recallyang memungkinkan rekursivitas dan penggunaan vektorisasi R yang sangat mempersingkat perhitungan aktual.

Pemakaian:

x = c(1,1,1,1)
f(x)
[1] 4+0i 0+0i 0+0i 0+0i
plannapus
sumber
1
Empat tahun kemudian, dan kami turun ke 101 byte . Tidak 100% yakin mengapa Anda menggunakan Recallfungsi bernama itu, tapi hei, mudah bermain golf di belakang! :) +1, sangat bagus.
Giuseppe
Ya Recallsekarang memang tidak perlu. Saya perhatikan bahwa beberapa bulan yang lalu tetapi terlalu malas untuk mengubahnya :) Saya akan memodifikasinya.
plannapus
Sangat bagus! Saya memeras 4 byte lagi! , menempatkan ini setara dengan Mathematica.
Giuseppe
Terima kasih! Saya berpikir tentang memasang ydi sana tetapi tidak menyadari itu bisa digunakan untuk exp(...)bagian itu juga.
plannapus
4

Python, 134

Ini sangat meminjam dari solusi jakevdp, jadi saya telah mengatur yang ini ke wiki komunitas.

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

Perubahan:

-12 karakter: bunuh 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: trik eksponen, x*y**-z == x/y**z (ini bisa membantu beberapa orang lain)

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

-2 char: ganti anddengan*

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

+1 char: lambdaize, membunuhN

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: gunakan enumeratebukanzip(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])))]
stan
sumber
Saya pikir ini bukan lagi transformasi fourier cepat, namun ... dengan "membunuh t" Anda menambahkan dalam beberapa perhitungan yang tidak perlu yang memindahkannya dari O [N log (N)] ke O [N ^ 2]
jakevdp
Tampaknya saya tidak dapat melakukan downvote pada posting saya sendiri. Anda benar, saya bertukar urutan loop dan mematikan kinerja. Saya akan meninggalkan ini untuk saat ini, kalau-kalau saya menemukan cara untuk memperbaikinya.
booth
101 byte denganf=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))]
mil
Anda dapat mengganti for s in(1,-1)fordengan for s in 1,-1foratau bahkan, jika pesanan tidak menjadi masalah 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;
}}}

Masalahnya adalah, implementasi seperti itu tidak berguna, dan algoritma langsung JAUH lebih cepat.

sanaris
sumber
2
Anda dapat menghapus beberapa spasi putih untuk mendapatkan jumlah karakter yang lebih rendah, misalnya step < ndapat diubah menjadi step<ndan step * 2dapat diubah menjadi step*2.
ProgramFOX
2
semua variabel dan fungsi serta typedef harus memiliki nama satu huruf untuk menyimpan banyak karakter
2
Anda memiliki seseorang yang menyarankan banyak perbaikan untuk ini. Lihatlah mereka di sini: codegolf.stackexchange.com/review/suggested-edits/17119
Justin
1
Anda dapat menghapus semua baris baru, baris baru tidak berguna di C
TuxCrafting
@ TùxCräftîñg Tidak semua baris baru tidak berguna. Mereka diperlukan untuk arahan seperti #include, #define, #if, dll.
Nayuki
3

Matlab, 128 118 107 102 101 94 93 byte

EDIT6: terima kasih @algmyr untuk byte lain!

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: Masih semakin pendek :) terima kasih kepada @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

EDIT4: Yay, -1 karakter lebih (bisa juga dilakukan tanpa 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: Terima kasih untuk @sanchises atas peningkatan lebih lanjut!

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

EDIT: Bisa membuat beberapa perbaikan, dan memperhatikan bahwa konstanta penskalaan tidak diperlukan.

Ini adalah versi yang diperluas, jumlah karakter valid jika Anda menghapus baris baru / spasi. (Hanya berfungsi untuk vektor kolom.)

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
cacat
sumber
Tip: Anda dapat menggabungkan dua d=baris menjadi satu: m=n/2;d=f(Y(2:2:n)).*exp(-pi*i*(0:m-1)/m).';. Selanjutnya, pertimbangkan y=f(Y)untuk mengubah Y=f(Y)dan menghapus baris 3 (dan berjanji Anda tidak akan pernah melakukannya di luar kode-golf)
Sanchises
Oh terima kasih! Apakah function Y = f(Y)ada gangguan selain tidak dapat dibaca?
flawr
Nah, MATLAB tidak akan pernah mengeluh tentang nilai kembali, bahkan jika Y tidak pernah berubah. Ini sedikit lebih cepat, jadi saya kira itu tidak terlalu buruk untuk semua tujuan (yaitu fungsi yang hampir tidak pernah mengubah variabel input)
Sanchises
Sekarang, untuk mencukur lebih banyak: m=n/2bisa dihapus, dan alih-alih mdiganti oleh n/2dan n*2masing - masing. Dan kemudian, saya sangat percaya, program ini sesingkat mungkin di MATLAB.
Sanchises
1
Dan kemudian, saya sangat percaya, program ini sesingkat mungkin di MATLAB. - Sanchises 8 Maret '15 pada 21:05 Kata-kata terakhir yang terkenal ...
Sanchises
2

Jelly, 31 30 28 26 byte , tidak bersaing

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

Jelly dibuat setelah tantangan ini sehingga tidak bersaing.

Ini menggunakan algoritma rekursif Cooley-Tukey radix-2. Untuk versi yang tidak golf, lihat jawaban saya di Mathematica.

Cobalah online atau Verifikasi beberapa uji .

Penjelasan

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
mil
sumber
2

C (gcc) , 188 186 184 183 byte

#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));}

Cobalah online!

Golf sedikit berkurang

#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));
}
plafon
sumber
1

Pari / GP, 76 karakter

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

Pemakaian

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̳
sumber
3
Bukankah ini DFT naif? (ie theta (N ^ 2))
mil
1

Oktaf , 109 103 101 100 byte

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)}())

Cobalah online!

Ooooo, mataku berdarah karena lambda terkutuk rekursif ini . Sebagian besar dari ini diangkat dari jawaban @ 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
)
plafon
sumber
Saya tidak mengerti apa yang Anda lakukan tetapi saya sangat menyukainya.
flawr
0

Aksioma, 259 , 193 , 181 , 179 byte

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

Bahkan jika h (a) dapat lulus semua tes dan akan baik-baik saja sebagai entri untuk 'kompetisi' ini, seseorang harus memanggil h () atau hlp () melalui fft () di bawah, untuk memeriksa argumen . Saya tidak tahu apakah perangkat lunak ini bisa baik-baik saja karena saya hanya melihat apa yang ditulis oleh orang lain, dan mencari cara menjalankannya di Axiom untuk mengembalikan beberapa kemungkinan hasil yang benar. Di bawah kode ungolfed dengan beberapa komentar:

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

dalam beberapa saya telah melihat h () atau fft () akan mengembalikan solusi yang tepat, tetapi jika penyederhanaan tidak bagus seperti pada:

(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

dari itu cukup untuk mengubah jenis hanya satu elemen daftar, seperti dalam tulisan di bawah ini 8. (Float) untuk menemukan solusi perkiraan:

(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

Saya menulisnya, melihat semua jawaban lain karena di tautan, halaman itu terlalu sulit jadi saya tidak tahu apakah kode ini benar. Saya bukan ahli fft sehingga semua ini bisa (kemungkinan) salah.

RosLuP
sumber
0

APL (NARS), 58 karakter, 116 byte

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

uji

  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
sumber