# Understanding and implementing the Fast Fourier Transform

I need to write the fast fourier transform in C++ and I am referring to this formula from wikipedia:

But for some reason I am not getting the correct output when I simply enter (1,1) (1,1) (1,1) (1,1) for by vector $v$. Here is my code:

#include <iostream>
#include <complex>
#include <cmath>
#include <time.h>

using namespace std;
typedef complex<double> dcomp;

int main() {
const int N = 4;
dcomp sum1 = dcomp(0.0, 0.0);
dcomp sum2 = dcomp(0.0, 0.0);
dcomp *X = new dcomp[N];
dcomp *v = new dcomp[N];
for(int i = 0; i < N; i++) {
v[i] = dcomp(1.0, 1.0);
}

for(int k = 0; k < N; k++) {
for(int m = 0; m < N/2.0; m++) {
double inside = (-2*M_PI/N)*(2*m)*k;
sum1 = sum1 + v[2*m] * dcomp(cos(inside), sin(inside));
}
for(int m = 0; m < N/2.0; m++) {
double inside1 = (-2*M_PI/N)*(2*m+1)*k;
sum2 = sum2 + v[2*m + 1] * dcomp(cos(inside1), sin(inside1));
}

X[k] = sum1 + sum2;
cout << X[k] << endl;
}

return 0;
}


It is quite simple to read if you just look at the formula I am literally doing the same thing but my output is (4,4) (4,4) (4,4) (4,4)

and it should be: (2,2) (0,0) (0,0) (0,0)

Can anyone help me and point out where I went wrong?

• You need to write an FFT because it's been assigned to you or because you need to use such a function in your research? There are many highly optimized libraries (FFTW being the most famous) that can do this for you. – Bill Barth Jan 21 '16 at 2:47
• I need to do it for Homework – Wolfy Jan 21 '16 at 2:49

Rather than having us debug your homework for you, I recommend that you read this blog post by Jake Vanderplas that contains a wonderful explanation of the FFT algorithm along with a highly readable Python implementation.

• Great article, I have actually read it before I understand the FFT algorithm, I don't want anyone to spend time debugging my code. But I just want to know what I am doing wrong so I can fix it. I have rewritten my code over and over again and I am still getting the wrong output. Oddly enough working it out by hand I get what I want which is why I am confused that C++ does not output the correct result – Wolfy Jan 21 '16 at 16:48