Pasted

#include <complex>
#include <vector>
 
 
using namespace std;
 
typedef complex<double> cdouble;
 
const double PI2  = 2 * 3.141593654;
 
vector<cdouble> fft(const vector<double>& input)
{
    int N = input.size();
 
    vector<cdouble> output(N);
 
    for (int k=0; k<N; k++)
    {
        cdouble out_val(0,0);
 
        for(int n=0; n<N; n++)
        {
            out_val += cdouble(input[n],0.0) * cdouble(cos( (PI2 * k * n) / N ), sin( (PI2 * k * n) / N ));
        }
 
        output[k] = out_val;
    }
    return output;
}
 
vector<cdouble> fft(const vector<double>& input, int N)
{
    vector<cdouble> output(N);
 
    for (int k=0; k<N; k++)
    {
        cdouble out_val(0,0);
 
        for(int n=0; n<input.size(); n++)
        {
            out_val += cdouble(input[n],0.0) * cdouble(cos( (PI2 * k * n) / N ), sin( (PI2 * k * n) / N ));
        }
 
        output[k] = out_val;
    }
    return output;
}