# Fast Fourier Transform

(Redirected from FFT)

**Fast Fourier transform** (**FFT**) is an efficient algorithm for calculating the discrete Fourier transform (DFT). The FFT produces the same results as a DFT but it reduces the execution time by hundreds in some cases. Whereas DFT takes an order of computations, FFT takes an order of , and is definitely the preferred algorithm to be used in all applications in terms of computational complexity. The FFT in most implementations consistent of samples that are exactly a power of 2, this is commonly known as a *FFT Radix 2* algorithm where etc.

## External links

- Fast Fourier transform on Wikipedia