寻找FFT(1D，任意长度）代码

Looking for FFT(1D, arbitrary length) code

本文关键字：代码任意长 FFT 1D 寻找更新时间：2023-09-26

嗨，我正在编写一个分析声音文件的程序，我需要对1秒的数组（通常为44100个样本）进行DFT。

所以我需要的是一个1D FFT算法，适用于任意长度，即不是2的幂。

有什么想法吗？

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算法。它不能有效地实现任意素数，但没有任何大素数需要处理。