# FAST FOURIER TRANSFORM IN C++

### Overview

The Fast Fourier Transform (FFT) is a fast method for evaluating the discrete Fourier transform (DFT) defined to be the complex exponential sum, $$\hat{x}_k = {1 \over \sqrt{N}} \sum_{j=0}^{N-1} x_j W^{j k} \quad n = 0 \ldots N-1$$ on the sequence $\{ x_k, \quad k = 0 \ldots N-1 \}$ where $W = e^{-2 \pi i / N}$ is an nth root of unity, and i denotes $\sqrt {-1}$

The FFT performs $O(n \: lg \: N)$ operations when N is a power of 2.

Here's C++ software which implements a power of two FFT. We create it as a derived class of the STL vector type.

### Features

• Clean C++ language implementation of a standard power of 2 FFT algorithm.

Source code and executables are distributed under the terms of the GNU General Public License. Current version is 1.0