Brief
The FFT (fast Fourier transform) splits a signal into its frequency components in O(n log n) time instead of O(n^2). Implement a recursive radix-2 FFT, which halves the problem at each step and so needs a power-of-2 length. Then write an iterative, in-place, vectorised version with bit-reversal (the reordering of the inputs that the iterative version needs). Add a Bluestein path for lengths that are not powers of 2 (it rewrites an FFT of any length as a convolution that can use power-of-2 FFTs). Use your FFT for spectral-subtraction denoising of a voice recording (estimate the noise spectrum and subtract it from each frame), and for FFT convolution via the convolution theorem (convolution in time equals multiplication of spectra).
VICTORY CONDITIONS
- Error <= 1e-9 * log2(n) relative to the signal norm. Within 10x of numpy.fft's time at 2^20. FFT convolution >= 100x faster than np.convolve at 2^18 taps (filter length). (Max abs error vs numpy.fft and wall time at n = 2^20 complex points; FFT-convolution speedup).
- A public repository with a README that shows your result and how to reproduce it.
Terms in plain words
- Radix-2 FFT
- An FFT that splits the input into even and odd samples at each level, so it works on lengths that are powers of 2.
- Bit-reversal permutation
- Reordering the inputs by reversing the binary digits of each index, which lets the FFT run in place without recursion.
- Bluestein's algorithm
- A way to compute an FFT of any length by turning it into a convolution, which is then done with power-of-2 FFTs.
- Convolution theorem
- The fact that convolving two signals is the same as multiplying their Fourier transforms, which makes long convolutions fast.
- Spectral subtraction
- A denoising method that estimates the noise's frequency content and subtracts it from each short frame of the signal.
Why it rates ★★☆☆☆
Everyone writes an FFT once. Doing Bluestein plus a real application shows care.