Hm..also habs so..aber irgendwie ist es falsch
Code:
#include <stdio.h>
#include <math.h>
#include <complex.h>	

#define Pi 3.14159265358979323846264	/* Pi */

/* *** Die eigentliche FFT
 * f[]: Eingabe: zu transformierende Daten
 *	Ausgabe: Ergebnis der Transformation
 * N:	Anzahl der Datenpunkte (2er-Potenz !!!!)
 * sign=-1: Hintransformation; sign=1: Ruecktransformation */

void fft(complex f[], int N, int sign) {
  double isqrtN;
  complex temp, W, Wk;
  int r, t, mask, n, no2, m, k, l;
  /* *** Teste, ob N 2er-Potenz ist */
  for(mask=1; mask<N; mask <<= 1)	;
  if(mask != N) {
    fprintf(stderr, "N = %d ist keine 2er-Potenz !\n", N);
    exit(13);
   }
  /* *** Teile Daten durch sqrt(N) */
  isqrtN = 1/sqrt(N);
  for(r=0; r<N; r++)
    f[r] *= isqrtN;
  /* *** Bit-Umkehr */
  for(t=0, r=0; r<N; r++) {
     if(t > r) {	/* Vertausche f[r] und f[t] */
        temp = f[r];
	f[r] = f[t];
	f[t] = temp;
      }
     mask = N;		/* Bit-umgekehrtes Inkrement von t */
     do {
        mask >>= 1;
	t ^= mask;
      } while((! (t & mask)) && mask);
   }

no2 = 1;
  for(m=1; (n=(no2 << 1)) <= N; m++) {
     W = cexp(I*sign*2*Pi/n);	/* W_n (C99 kennt I) */
     Wk = 1;
     for(k=0; k<no2; k++) {
        for(l=k; l<N; l+=n) {
	   complex temp = Wk*f[l+no2];
	   f[l+no2] = f[l] - temp;
	   f[l] += temp;
	 }
        Wk *= W;	/* Wk = W^k */
      }
     no2 = n;
   }
 }