Discrete Fourier Transform

#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;
}