/* * Discrete Fourier transform (C++) * by Project Nayuki, 2020. Public domain. * https://www.nayuki.io/page/how-to-implement-the-discrete-fourier-transform */ /* * Computes the discrete Fourier transform (DFT) of the given complex vector. * All the array arguments must have the same length. */ #include #include #include using std::size_t; using std::complex; using std::vector; using std::exp; vector > computeDft(const vector > &input) { vector > output; size_t n = input.size(); for (size_t k = 0; k < n; k++) { // For each output element complex sum(0, 0); for (size_t t = 0; t < n; t++) { // For each input element double angle = 2 * M_PI * t * k / n; sum += input[t] * exp(complex(0, -angle)); } output.push_back(sum); } return output; } /* * (Alternate implementation using only real numbers.) * Computes the discrete Fourier transform (DFT) of the given complex vector. * All the array arguments must have the same length. */ #include #include #include using std::size_t; using std::vector; using std::cos; using std::sin; void computeDft(const vector &inreal, const vector &inimag, vector &outreal, vector &outimag) { size_t n = inreal.size(); for (size_t k = 0; k < n; k++) { // For each output element double sumreal = 0; double sumimag = 0; for (size_t t = 0; t < n; t++) { // For each input element double angle = 2 * M_PI * t * k / n; sumreal += inreal[t] * cos(angle) + inimag[t] * sin(angle); sumimag += -inreal[t] * sin(angle) + inimag[t] * cos(angle); } outreal[k] = sumreal; outimag[k] = sumimag; } }