#include <math.h>

void fft(float *x, float *y, int n, int flag)
{
    float frac;
    float a, c, e;
    int i, j, k, l, m;
    float s;
    int n1, n2;
    float xt, yt;
    
    frac = (float)(frexp((float) n, &m)); 
   
    if (frac == 1.0) 
	{
    } 
	else 
	{
	m--;
    }
    
    // --------------MAIN FFT LOOPS-----------------------------
    --y;
    --x;
    
    //---------------Function Body -----------------------------
    n2 = n;
    for (k = 1; k <= m; ++k) {
	n1 = n2;
	n2 /= 2;
	e = (float)6.283185307179586476925286766559005768394 / n1;
	if (flag==1){e=-e;} // for ifft
	a = 0.0;
	for (j = 1; j <= n2; ++j) {
	    c = (float)(cos(a));
	    s = (float)(sin(a));
	    a = j * e;
	    for (i = j; n1 < 0 ? i >= n : i <= n; i += n1) {
		l = i + n2;
		xt = x[i] - x[l];
		x[i] += x[l];
		yt = y[i] - y[l];
		y[i] += y[l];
		x[l] = c * xt + s * yt;
		y[l] = c * yt - s * xt;
	    }
	}
    }
    
    //------------DIGIT REVERSE COUNTER-------------------
    
    j = 1;
    n1 = n - 1;
    for (i = 1; i <= n1; ++i) {
	if (i < j) {
	    xt = x[j]; x[j] = x[i];	x[i] = xt;
	    xt = y[j]; y[j] = y[i];	y[i] = xt;
	}
	k = n / 2;
	while (k<j) {
	    j -= k;
	    k /= 2;
	}
	j += k;
    }

//--------------- for ifft --------------------------------
	if(flag==1)
	{
		x++;
		y++;
		for(j=0;j<=n1;j++)
		{
			x[j]/=n;
			y[j]/=n;
		}
	}

} //--- fft and ifft----