In signal processing, the fast Fourier transform (FFT) is an algorithm that efficiently computes the [[discrete Fourier transform (DFT)]]of a [[discrete-time signal]], or its inverse. The standard definition of the DFT: $X(k) = \sum_{n=0}^{N-1} x(n) e^{-j \frac{2\pi}{N} kn},\; 0 \leq k \leq N-1$ requires $N^2$ complex multiplications. By splitting the computation of the DFT into successive halves it is possible to achieve the same result with $\frac{N}{2} \log_2 N$ complex multiplications when $N$ is a power of $2$. This makes the FFT algorithm an essential tool in many fields, including audio and image processing, telecommunications, and scientific computing. ![[DIT-FFT-butterfly.svg]] [Wikimedia](https://commons.wikimedia.org/wiki/File:DIT-FFT-butterfly.svg)