Fast Fourier Transform

A Fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT).

It's let the complexity of computing of the Diecrete Fourier Transform (DFT) form O(n^{2}) to O(nlogn).

Relate knowledge of Fast Fourier Transform

Usage

1. Compile

   $ make

2. Run

   # DFT
   $ ./dft
   
   # FFT
   $ ./fft

DFT v.s FFT

1. spends times

   

2. example