Fast Fourier transform
This is a naive approach, however, we already know that an N-point 1-D DFT can be computed with far fewer than formula_13 multiplications by using the Fast Fourier Transform (FFT) algorithm. As described in the next section we can develop Fast Fourier transforms for calculating 2-D or higher dimensional DFTs as well