Background FFT is a divide and conquer algorithm that speeds up matrix multiplication of an input array of size n and an nxn \(M_n(\omega)\) matrix which has (j,k)th entry \(\omega^{jk}\) where 1, \(\omega\), \(\omega^{2}\), ..., \(\omega^{n-1}\) are the complex nth roots of unity.

Continued The code below works (the results are correct) though there's a memory leak. 

```C
float complex *fft(float complex *in, int n, float complex w) {
  int i,j;
  if(fabs(crealf(w)-1.00f)<.0001f && fabs(cimagf(w)-0.00f)<0.0001f) {
//printf("Edge return %d \n", n);
return in;
  }
  //if(crealf(w)>1.0 || crealf(w)<-1.0) return in;
  //if (stack > 3) return in;
  stack++;
  float complex *ine = malloc(n/2*sizeof(float complex));
  float complex *ino = malloc(n/2*sizeof(float complex));
  for(i=0,j=0;i<n;i++) {
if(i%2==0){ 
  ine[j]=in[i];
}
else {
  ino[j++]=in[i];   
}
  }
  float complex *s = fft(ine,n/2,cpow(w,2));
  float complex *s1 = fft(ino,n/2,cpow(w,2));

  float complex *bad = malloc(n*sizeof(float complex));
  for (j=0; j<n/2; j++){
    bad[j] = s[j] + cpow(w,j) * s1[j];
bad[j+n/2] = s[j] - cpow(w,j) * s1[j];
  }
  free(ine); free(ino); //free(s); free(s1);
  //printf("End return %d \n", n);
  return bad;
}
```