The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

FFT - Fast Fourier Transform


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.


  • Download Files (local site)
  • Fast Fourier transform

    Problem Links

      
    Generating Partitions (8)
      
    Generating Permutations (8)
      
    Generating Subsets (8)
      
    Discrete Fourier Transform (7)



    This page last modified on 2008-07-10 .
    www.algorist.com