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

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?

  • $\begingroup$ 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. $\endgroup$ – Bill Barth Jan 21 '16 at 2:47
  • 2
    $\begingroup$ I need to do it for Homework $\endgroup$ – 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.

  • $\begingroup$ 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 $\endgroup$ – Wolfy Jan 21 '16 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.