The Fast Fourier transform is a DFT algorithm developed by Tukey and Cooley in 1965 which reduces the number of computations from something on the order of N02 to N0log N0. There are basically two types of Tukey-Cooley FFT algorithms in use: decimation-in-time and decimation-in-frequency. The algorithm is simplified if N0 is chosen to be a power of 2, but it is not a requirement.
Generating Partitions (8) |
Generating Permutations (8) |
Generating Subsets (8) |
Discrete Fourier Transform (7) |