FFT (Cooley-Tukey)

James Cooley & John Tukey, 1965

The Cooley-Tukey radix-2 decimation-in-time (1965) applies the butterfly operation stage by stage: bit-reverse the input, then for each stage combine pairs of bins separated by increasing strides.