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?
Understanding and implementing the Fast Fourier Transform
c++;homework;fourier transform
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.