vector< complex<double> > DFT(vector< complex<double> >& theData)
{
// Define the Size of the read in vector
const int S = theData.size();

// Initalise new vector with size of S
vector< complex<double> > out(S, 0);
for(unsigned i=0; (i < S); i++)
{
    out[i] = complex<double>(0.0, 0.0);
    for(unsigned j=0; (j < S); j++)
    {
        out[i] += theData[j] * polar<double>(1.0, - 2 * PI * i * j / S);
    }
}

return out;
}

//-------------------------------------

#include <iostream>
#include <complex>
#include <vector> 
#include <conio.h>
#include <cmath>
using namespace std;
 
#define Pi acos(-1.)
 
vector<complex<double>> FFT(vector<double> signal)
{
    unsigned N = signal.size();
    unsigned K = N / 2 + 1;
    double real = 0;
    double imag = 0;
    double phase = 0;
    vector<complex<double>> output;
    for (unsigned k = 0; k < K; k++)
    {
        real = 0;
        imag = 0;
        for (unsigned n = 0; n < N; n++)
        {
            phase = (2 * Pi * n * k) / N;
            real += signal[n] * cos(phase);
            imag += signal[n] * sin(phase);
        }
        complex<double>temp(real, imag);
        temp /= sqrt(N);
        output.push_back(temp);
    }
    return output;
}
 
vector<double> IFFT(vector<complex<double>> fourier)
{
    unsigned K = fourier.size();
    unsigned N = (K - 1) * 2;
    double phase = 0;
    complex<double> temp;
    double result = 0;
    vector<double> output;
    for (unsigned n = 0; n < N; n++)
    {
        result = 0;
        for (unsigned k = 0; k < K; k++)
        {
            temp = conj(fourier[k]);
            phase = (2 * Pi * n * k) / N;
            result += cos(phase) * temp.real() - sin(phase) * temp.imag();
        }
        result /= sqrt(N);
        output.push_back(result);
    }
    return output;
}
 
int main()
{
    vector<double> signal;
    cout << "Input: 8" << endl;
    for (int i = 1; i < 9; i++)
    {
        signal.push_back(i);
        cout << signal.back() << endl;
    }
    vector<complex<double>> test = FFT(signal);
        cout << endl << "Length of fourier array: " << test.size() << endl;
    vector<double> final = IFFT(test);
    cout << endl << "Length of output: " << final.size() << endl << endl;
    for (unsigned i = 0; i < final.size(); i++)
    {
        cout << final[i] << endl;
    }
    _getch();
    return 0;
}