尋找FFT（1D，任意長度）代碼

Question

嗨我正在開發一個程序來分析聲音文件，我需要在1秒陣列上做DFT，通常是44100個樣本。

所以我需要工作在任意長度的一維FFT算法，即什麼不是2

任何想法的動力？

Answer 1

https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm通常用於二元分割，但實際上處理任意分解。只要你的號碼完全分解成小數字（你的號碼是2*2*3*3*5*5*7*7），這將給出一個相當有效的FFT。 （請參閱「通用分解」一節。）

還有其他可以處理任意大小的FFT算法，但它們速度要慢得多（儘管比天真好）。見https://en.wikipedia.org/wiki/Chirp_Z-transform#Bluestein.27s_algorithm爲一個。

http://www.nayuki.io/page/free-small-fft-in-multiple-languages以多種語言（包括JavaScript）實現了一般Cooley-Tukey FFT算法。它沒有對任意素數做有效的實現，但是你沒有任何大的處理。