public class FFT
{
    /*
     * This method (function) computes the Fourier coefficients of a functions 
     * specified via discrete points. The input array <tt>ar</tt> contains the 
     * real values, <tt>ai</tt> the imaginary values of the input function,
     * or zero if the function is a real-valued function (most likely).
     * 
     * The length of the arrays must be the same, and must be a power
     * of two. It is specified as the input value n.
     * 
     * The input variable sign specifies regular (sign = 1) or inverse
     * (sign = -1) Fourier transform.
     * 
     * On output the arrays ar and ai contain the Fourier coefficients
     * of the Fourier series.
     */
    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;
        }
    }
}