FFT implementieren

hallo, ich bin dabei die Fast Fourier Transformation zu implementieren. Dazu habe ich versucht den Pseudocode von der wikipedia in c/c++ umzusetzen:

http://de.wikipedia.org/wiki/Schnelle_Fourier-Transformation

Bei wikipedia ist noch ne zusätzliche Variable (i) "ich denke mal irgendwas mit imaginärteil" in dem folgenden Teil (-2*M_PI*k/n).

Ich weiß nur nicht worum es sich hier genau handelt.
Deswegen hier nun mein Ansatz bei dem ich noch Hilfe gebrauchen könnte.
Fals ansonsten noch Fehler erkennbar sind, bitte mitteilen. danke.

#include "stdafx.h"
#define _USE_MATH_DEFINES
#include <math.h>
#include <stdio.h>
#include <windows.h>

static int N_MAX = 4096;

double *input          = new double[N_MAX];

void getEvenAndUnevenHalf(int n,double *input, double *outputEven, double *outputUneven)
{
	for(int i=0;i<n/2;i++)
	{
		outputEven[i]   = input[i*2];
		outputUneven[i] = input[1+(i*2)];
	}
}
double *FFT(int n,double *input)
{
	if(n==1)
	{
		return input;
	}
	else
	{
		double *evenHalf   = new double[n/2];
		double *unevenHalf = new double[n/2];
	    double *even       = new double[n/2];
		double *uneven     = new double[n/2];
		getEvenAndUnevenHalf(n,input,evenHalf,unevenHalf);
		even   = FFT(n/2,evenHalf);
		uneven = FFT(n/2,unevenHalf);

		double *output = new double[n];

		for(int k=0;k<((n/2)-1);k++)
		{
			output[k]     = even[k]+uneven[k]*exp((-2*M_PI*k/n));
			output[n/2+k] = even[k]-uneven[k]*exp((-2*M_PI*k/n));
		}

		return output;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	DWORD startTime = GetTickCount();
	printf("Start Time %d\n",startTime);
	FFT(N_MAX,input);
	DWORD endTime = GetTickCount();
	printf("End Time %d\n",endTime);
	printf("Duration %d\n",endTime-startTime);
	getchar();
	return 0;
}

JistaloF schrieb:

Bei wikipedia ist noch ne zusätzliche Variable (i) "ich denke mal irgendwas mit imaginärteil" in dem folgenden Teil (-2*M_PI*k/n).

Ich weiß nur nicht worum es sich hier genau handelt.

das i ist wichtig. benutze eine bibliothek für komplexe zahlen deiner wahl. oder schau nach wie komplexe zahlen multipliziert werden, und implementiere es im code. ohne komplexe zahlen funktioniert das ganze mal so überhaupt und gaaanz und gar nicht.

...--... schrieb:

das i ist wichtig. benutze eine bibliothek für komplexe zahlen deiner wahl.

wenn du den gcc benutzt, der sollte z.b. das hier kennen: http://en.wikipedia.org/wiki/Complex.h