1. #include <vector>
2. #include <complex>
3. #include <iostream>
4. using namespace std;
5. #include <cmath>
6.  
7. #define M_PI 3.14159265358979323846
8.  
9. int main()
10. {
11.        
12. }
13.  
14. vector<complex<double>> FFT(vector<complex<double>>& samples)
15. {
16.         int N = samples.size();
17.         if (N == 1) return samples;
18.         int M = N / 2;
19.         vector<complex<double>> Xeven(M, 0);
20.         vector<complex<double>> Xodd(M, 0);
21.         for (int i = 0; i != M; i++)
22.         {
23.                 Xeven[i] = samples[2 * i];
24.                 Xodd[i] = samples[2 * i + 1];
25.         }
26.         vector<complex<double>> Feven(M, 0);
27.         Feven = FFT(Xeven);
28.         vector<complex<double>> Fodd(M, 0);
29.         Fodd = FFT(Xodd);
30.         vector<complex<double>> freqbins(N, 0);
31.         for (int k = 0; k != N / 2; k++)
32.         {
33.                 complex<double> cmplxexponential = polar(1.0, -2 * M_PI * k / N)*Fodd[k];
34.                 freqbins[k] = Feven[k] + cmplxexponential;
35.                 freqbins[k + N / 2] = Feven[k] - cmplxexponential;
36.         }
37.         return freqbins;
38. }