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 )
Sunting:
kode harus mengimplementasikan Fast Fourier Transform standar, yang bentuknya dapat dilihat pada persamaan (3) artikel Wolfram ini ,
- Menggunakan fungsi FFT dari pustaka standar atau paket statistik yang sudah ada tidak diperbolehkan. Tantangannya di sini adalah mengimplementasikan algoritma FFT secara ringkas .
code-golf
math
complex-numbers
jakevdp
sumber
sumber
FFT
(3 karakter): ada di perpustakaan standar"? Beberapa test case juga bagus.Jawaban:
Mathematica, 95 byte
Implementasi lain dari Cooley – Tukey FFT dengan bantuan dari @ chyaong .
Tidak disatukan
sumber
#[[;;;;2]]==#[[1;;N;;2]]
dan[[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 byte
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
Penjelasan
sumber
Python,
166151150 karakterIni menggunakan algoritme radix-2 Cooley-Tukey FFT
Menguji hasilnya
sumber
from x import*
, dansum(([x for x in y] for y in z),[])
lebih lama dari itu[x for y in z for x in y]
.Python 3:
140134113 karakterVersi pendek - pendek dan manis, pas di tweet (dengan terimakasih kepada miles ):
(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:
sumber
e^(-2j * pi * i / n) = (-1)^(2 * i / n) = (1j)^(4 * i / n)
R:
1421339995 byteTerima kasih kepada @Giuseppe karena membantu saya menghemat
3236 byte!Trik tambahan di sini adalah dengan menggunakan argumen default fungsi utama untuk instantiate beberapa variabel.
Penggunaannya masih sama:
Versi 4 tahun pada 133 byte:
Dengan lekukan:
Ini juga menggunakan algoritma Cooley-Tukey. Satu-satunya trik di sini adalah penggunaan fungsi
Recall
yang memungkinkan rekursivitas dan penggunaan vektorisasi R yang sangat mempersingkat perhitungan aktual.Pemakaian:
sumber
Recall
fungsi bernama itu, tapi hei, mudah bermain golf di belakang! :) +1, sangat bagus.Recall
sekarang memang tidak perlu. Saya perhatikan bahwa beberapa bulan yang lalu tetapi terlalu malas untuk mengubahnya :) Saya akan memodifikasinya.y
di sana tetapi tidak menyadari itu bisa digunakan untukexp(...)
bagian itu juga.Python, 134
Ini sangat meminjam dari solusi jakevdp, jadi saya telah mengatur yang ini ke wiki komunitas.
Perubahan:
-12 karakter: bunuh
t
.-1 char: trik eksponen,
x*y**-z == x/y**z
(ini bisa membantu beberapa orang lain)-2 char: ganti
and
dengan*
+1 char:
lambda
ize, membunuhN
-2 char: gunakan
enumerate
bukanzip(range(len(
sumber
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
denganfor s in 1,-1for
atau bahkan, jika pesanan tidak menjadi masalahfor s in-1,1for
,.C, 259
Masalahnya adalah, implementasi seperti itu tidak berguna, dan algoritma langsung JAUH lebih cepat.
sumber
step < n
dapat diubah menjadistep<n
danstep * 2
dapat diubah menjadistep*2
.Matlab,
1281181071021019493 byteEDIT6: terima kasih @algmyr untuk byte lain!
EDIT5: Masih semakin pendek :) terima kasih kepada @sanchises
EDIT4: Yay, -1 karakter lebih (bisa juga dilakukan tanpa
k
):EDIT2 / 3: Terima kasih untuk @sanchises atas peningkatan lebih lanjut!
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.)
sumber
d=
baris menjadi satu:m=n/2;d=f(Y(2:2:n)).*exp(-pi*i*(0:m-1)/m).';
. Selanjutnya, pertimbangkany=f(Y)
untuk mengubahY=f(Y)
dan menghapus baris 3 (dan berjanji Anda tidak akan pernah melakukannya di luar kode-golf)function Y = f(Y)
ada gangguan selain tidak dapat dibaca?m=n/2
bisa dihapus, dan alih-alihm
diganti olehn/2
dann*2
masing - masing. Dan kemudian, saya sangat percaya, program ini sesingkat mungkin di MATLAB.Jelly,
31302826 byte , tidak bersaingJelly 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
sumber
C (gcc) ,
188 186 184183 byteCobalah online!
Golf sedikit berkurang
sumber
Pari / GP, 76 karakter
Pemakaian
sumber
Oktaf ,
109 103 101100 byteCobalah online!
Ooooo, mataku berdarah karena lambda terkutuk
rekursifini . Sebagian besar dari ini diangkat dari jawaban @ flawr.sumber
Aksioma,
259,193,181, 179 byteBahkan 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:
dalam beberapa saya telah melihat h () atau fft () akan mengembalikan solusi yang tepat, tetapi jika penyederhanaan tidak bagus seperti pada:
dari itu cukup untuk mengubah jenis hanya satu elemen daftar, seperti dalam tulisan di bawah ini 8. (Float) untuk menemukan solusi perkiraan:
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.
sumber
APL (NARS), 58 karakter, 116 byte
uji
sumber