Ob da ein Quadrat fehlt oder nicht, kann ich dir leider nicht sagen, sowas wäre etwas für das Mathematik-Subforum hier.
Aber mind. sollte
for(count=0;count<m;count++)
{
u_1[count]=x[count]+x[count+m];
u_2[count]=(x[count]-x[count+m])*diag[count];;
}
doch wohl eher
for(count=0;count<m;count++)
{
u_1[count]=(x[count]+x[count+m])*diag[count];
u_2[count]=(x[count]-x[count+m])*diag[count];
}
heißen.
Außerdem solltest du für Pi eine symbolische Konstante verwenden, z.B.
#ifndef M_PI
#define M_PI 3.141592653
#endif
Weiterhin ist deine Speicherbehandlung, wie du selber schon bemerkt hast, stark verbesserungsbedürftig, du brauchst kein extra Array zurückgeben, nehme besser einfach das übergebene Array zur Abspeicherung der Ergebniswerte, also in etwa (ungetestet):
void fft(double*x,int k)
{
if(k>1)
{
int count, m=pow(2,k)/2;
double* diag=malloc(m*sizeof*diag);
double* v =malloc(m*sizeof*v);
double* w =malloc(m*sizeof*w);
double q = M_PI/m;
for(count=0;count<m;count++)
{
diag[count]=sin(q*count);
}
for(count=0;count<m;count++)
{
v[count]=(x[count]+x[count+m])*diag[count];
w[count]=(x[count]-x[count+m])*diag[count];
}
fft(v,k-1); /* nach Ausführung der Funktion steht das Ergebnis gleich in v */
fft(w,k-1); /* nach Ausführung der Funktion steht das Ergebnis gleich in w */
for(count=0;count<m;count++)
{
x[2*count]=v[count];
x[2*count+1]=w[count];
}
free(w);free(v);free(diag);
}
}
