/**
    Note: requires a function "isPowerOfTwo" before it will compile.
          Add that function and adjust code accordingly, or remove
          the check for 'power of two'.
*/
public class FFT
{	private final static double EPSI = 10E-5;
	public static int ERROR = 0;
    	public final static String[] ERROR_MSG =
                 {"No error",
                  "array dimensions do not match",
                  "array dimensions must be a multiple of 2",
                  "imaginary part of constant not zero"};

	public static void computeFFT(double ar[], double ai[])
	{	if (ar.length != ai.length)
		{	ERROR = 1;
			System.err.println("array dimensions must match");
 		}
		else if (!BitConvert.isPowerOfTwo(ar.length))
		{	ERROR = 2;
			System.err.println("array dimensions must be multiple of 2");
		}
		else
		{	computeFFT(1, ar.length, ar, ai);
			if (ai[0] > EPSI)
			{	ERROR = 3;
				System.err.println("imaginary part of constant not zero");
			}
		}
	}
	public static void computeFFT(int sign, int n, double ar[], double ai[]) 
	{	double scale = 2.0 / (double)n;
		int i, j;
		for (i = j = 0; i < n; ++i) 
		{	if (j >= i) 
			{	double tempr = ar[j]*scale;
				double tempi = ai[j]*scale;
				ar[j] = ar[i]*scale;
				ai[j] = ai[i]*scale;
				ar[i] = tempr;
				ai[i] = tempi;
			}
			int m = n/2;
			while ((m >= 1) && (j >= m)) 
			{	j -= m;
				m /= 2;
			}
			j += m;
		}
		int mmax,istep;
		for (mmax = 1, istep = 2*mmax; mmax < n; mmax = istep, istep = 2*mmax) 
		{	double delta = sign*Math.PI/(double)mmax;
			for (int m = 0; m < mmax; ++m) 
			{	double w = m*delta;
				double wr = Math.cos(w);
				double wi = Math.sin(w);
				for (i = m; i < n; i += istep) 
				{	j = i + mmax;
					double tr = wr*ar[j] - wi*ai[j];
					double ti = wr*ai[j] + wi*ar[j];
					ar[j] = ar[i] - tr;
					ai[j] = ai[i] - ti;
					ar[i] += tr;
					ai[i] += ti;
				}
			}
			mmax = istep;
		}
	}
	public static String getErrorMsg()
	{	return ERROR_MSG[ERROR];
	}
}