FFT - Fast Fourier Transform Program (Algorithm)

Copy From http://people.csail.mit.edu/hammond/teaching/hide/fft/

public class fft
{
private double[] YREAL;
private double[] YIMAG;
private double[] XREAL;
private double[] AFFT;
private double[] BFFT;
private double[] COSX;
private double[] SINX;
private int[] POW;

fft(String[] datapoints)
{

try
{

// put the given values in to an array
YREAL = makeRealArray(datapoints);
YIMAG = makeImaginaryArray(datapoints);

// make array of x values
XREAL = makeXArray(Integer.parseInt(datapoints[0]));

// the given values function are starting values for
// Fourier Results
AFFT = YREAL;
BFFT = YIMAG;

// make cos(x) array and sin(x) array
COSX = makeCosXArray(XREAL);
SINX = makeSinXArray(XREAL);

// generate power array
POW = makePowerArray(Integer.parseInt(datapoints[0]));

// actual fft calculation done here
calculateABValues(Integer.parseInt(datapoints[0]));

// unscramble the vertices according to POW values
unscramble();

}
catch (Exception e)
{
System.out.println("Exception " + e.toString());
e.printStackTrace();
System.exit(-1);
}

for(int i = 0; i < realarray =" new" i =" 0;" imaginaryarray =" new" i="0;" xarray =" new" i =" 0;" cosxarray =" new" i =" 0;" sinxarray =" new" i =" 0;" powerarray =" new" i =" 0;" totalnumberofruns ="  (int)" i =" 1;" j =" 1;" j =" 0;" i =" 0;" stage =" 1;" numberofsets =" 1;" cyclelength =" NumberOfData/2;" k =" 0;" tempa =" AFFT;" tempb =" BFFT;" setnumber =" 1;" i =" 0;" j =" (i" l =" POW[(int)(k/cycleLength)];"> AFFT.length || l > AFFT.length || j+cycleLength > AFFT.length)
   System.out.println("HELP");
  TEMPA[k] = AFFT[j] + COSX[l]*AFFT[j+cycleLength] - SINX[l]*BFFT[j+cycleLength];
  TEMPB[k] = BFFT[j] + COSX[l]*BFFT[j+cycleLength] - SINX[l]*AFFT[j+cycleLength];
  k++;
 }
}
AFFT = TEMPA;
BFFT = TEMPB;
stage++;
NumberOfSets *= 2;
cycleLength /= 2;
k = 0;            
} while (stage <= (int)(Math.log(NumberOfData)/Math.log(2)));  }    /**   * Method: unscramble   * Input: none   * Output: none   * Function: Rearranges the A and B values   */  private void unscramble()  {   double[] tempA = AFFT;   double[] tempB = BFFT;   for (int i = 0; i < length ="=" data1 =" {" alg =" new" i =" 0;"> Integer.parseInt(args[0]))
  printUsage();
} while (true);

// make sure number entered equals the number of
// datapoints
if ((args.length - 1)/2 != Integer.parseInt(args[0]))
 printUsage();

}
catch (Exception e){
// probably error in input
printUsage();
}

// all is good.
// start the program (Fast Fourier Transform)
fft alg = new fft(args);

}

private static void printUsage()
{
System.out.println("Fast Fourier Transform");
System.out.println("Returns the fft of a list of data points");
System.out.println("--usage");
System.out.println("        fft number datapoints");
System.out.println();
System.out.println("Number must be the number of datapoints");
System.out.println("Number must be power of 2");
System.out.println("Datapoints must be written as: y1real y1imaginary y2real y2imaginary...");
System.out.println("X values are considered to be standardized on [0,2*pi]");
System.out.println();
System.exit(0);
}
}