fft

constexpr std::vector<Complex> fft(const std::vector<Complex> &X) noexcept: Calculates the fast Fourier transform [1] of a complex sequence.

Parameters

const std::vector<Complex> &X

A complex sequence.

Returns

template<>
type std::vector<Complex>

A complex sequence.

The fast Fourier transform performs the discrete Fourier transform, defined as follows:

\[\DeclareMathOperator\H{H} X_k = \sum_{m = 0}^{n - 1}x_m e^{-2\pi km/n} \quad k = 0, \ldots, n-1,\]

A discrete Fourier transform is classed as a fast Fourier transform if it is able to perform the above transform in \(O(n\log(n))\) time. The Cooley-Tukey algorithm [2] is used by cpplex to achieve this.

Example

std::vector<Complex> X = {1 + 2_j, 2 + 3_j, 3, 4, 5};
std::vector<Complex> Y = fft(X);

for(int i = 0; i < Y.size(); i++){
    std::cout << Y[i] << "\n";
}

Output:

15 + 5j
0.35317 + 6.36801j
-0.736644 + 0.385248j
-4.26336 - 1.23935j
-5.35317 - 0.513904j

References