3 ms·
lol cooley-tukey FFT is anything but simple when you actually have to implement it.
by anon_tor_12345 5y ago
lol cooley-tukey FFT is anything but simple when you actually have to implement it.
- Greek0 5y agoCooley-Tukey Fast Fourier Transform can be complex to implement, if you want to optimize it. A basic version is surprisingly simple, I implemented it for fun in Python a couple of years ago: def fft(x): N = len(x) if N == 1: return x assert N % 2 == 0 E = fft(x[::2]) O = fft(x[1::2]) X = [None] * N for k in range(N // 2): tf = np.exp(-2j * np.pi * k / N) X[k] = E[k] + tf * O[k] X[k + N//2] = E[k] - tf * O[k] return X The Wikipedia article describing it is surprisingly decent: https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algor...