package fft;

public class Fft {
	public final fft.Complex[] input;
	public fft.Complex[] output;
	public final int size;
	
	public Fft(int n) {
		if (fft.Fft.checkSize(n)) {
		  this.size = n;
		  this.input = new fft.Complex[this.size];}
		else {
		  throw new java.lang.IllegalArgumentException("The argument must be power of 2");}
	}
	
	public static boolean checkSize(int a) {
		for (long b = 1L; true; b *= 2L) {
		  if ((long)a == b) {
		    return true;}
		  if ((long)a < b) {
		    return false;}}
	}
	
	public void fft() {
		int half = this.size / 2;
		fft.Complex[] coefs = new fft.Complex[half];
		for (int a = 0; a < half; a++) {
		  coefs[a] = new fft.Complex((double)a / (double)this.size);}
		this.output = this.fftRec(this.input, coefs);
	}
	
	public fft.Complex[] fftRec(fft.Complex[] in, fft.Complex[] coefs) {
		int len = in.length;
		if (len > 1) {
		  int half = len / 2;
		  fft.Complex[] in0 = new fft.Complex[half];
		  fft.Complex[] in1 = new fft.Complex[half];
		  for (int i = 0; i < half; i++) {
		    in0[i] = in[2 * i];
		    in1[i] = in[2 * i + 1];}
		  fft.Complex[] out0 = this.fftRec(in0, coefs);
		  fft.Complex[] out1 = this.fftRec(in1, coefs);
		  fft.Complex[] out = new fft.Complex[len];
		  for (int r = 0; r < half; r++) {
		    fft.Complex coeff = coefs[this.size * r / len];
		    fft.Complex par = out1[r].mul(coeff);
		    out[r] = out0[r].add(par);
		    out[r + half] = out0[r].sub(par);}
		  return out;}
		else {
		  return in;}
	}
	
	public double[] getIm() {
		double[] a = new double[this.size];
		for (int i = 0; i < this.size; i++) {
		  a[i] = this.output[i].getIm();}
		return a;
	}
	
	public double[] getRe() {
		double[] a = new double[this.size];
		for (int i = 0; i < this.size; i++) {
		  a[i] = this.output[i].getRe();}
		return a;
	}
	
	public static void main(java.lang.String[] args) {
		if (args.length < 1) {
		  java.lang.System.out.println("Usage:  java Fft <number of iterations> [<number of tests>]");
		  java.lang.System.out.println("Sample: java Fft 1000 5");
		  return;}
		int iters = java.lang.Integer.valueOf(args[0]).intValue();
		int tests = 1;
		if (args.length > 1) {
		  tests = java.lang.Integer.valueOf(args[1]).intValue();}
		final double[] arg = new double[] {1D, 0D, 0D, 1D, 2D, 1D, 1D, 2D, 1D, 0D, 0D, -1D, 2D, 1D, 1D, 2D, -1D, 0D, 0D, 1D, -2D, 1D, 1D, 2D, -1D, 0D, 0D, -1D, 2D, 1D, 1D, 2D};
		double[] res1 = null;
		for (int i = 0; i < 100; i++) {
		  res1 = fft.Fft.test(arg);}
		for (int t = 0; t < tests; t++) {
		  long start = java.lang.System.currentTimeMillis();
		  for (int i = 0; i < iters; i++) {
		    res1 = fft.Fft.test(arg);}
		  long end = java.lang.System.currentTimeMillis();
		  java.lang.System.out.println("Time of one iteration = " + (float)(end - start) / (float)iters * 1000F + " microsec");}
	}
	
	public void setX(double[] re, double[] im) {
		if (re.length != this.size
		||  im.length != this.size) {
		  throw new java.lang.IllegalArgumentException("Size of both arguments must be equal to " + this.size);}
		for (int a = 0; a < this.size; a++) {
		  this.input[a] = new fft.Complex(re[a], im[a]);}
	}
//--------------------------------------   0 sec - method fft.Fft.test(double[])
//--------------------------------------   0 sec - field java.lang.Throwable.serialVersionUID postprocessing...
//--------------------------------------   0 sec - field java.lang.Exception.serialVersionUID postprocessing...
//--------------------------------------   0 sec - field java.lang.RuntimeException.serialVersionUID postprocessing...
//--------------------------------------   1 sec - method fft.Fft.test(double[]) postprocessing...
  public static double[] test (final double[] arg_1)
  {
    if (arg_1.length != 32) {
      throw new java.lang.IllegalArgumentException();}
    final double arg_0_14 = arg_1[0];
    final double arg_1_15 = arg_1[1];
    final double arg_2_18 = arg_1[2];
    final double arg_3_19 = arg_1[3];
    final double arg_4_22 = arg_1[4];
    final double arg_5_23 = arg_1[5];
    final double arg_6_26 = arg_1[6];
    final double arg_7_27 = arg_1[7];
    final double arg_8_30 = arg_1[8];
    final double arg_9_31 = arg_1[9];
    final double arg_10_34 = arg_1[10];
    final double arg_11_35 = arg_1[11];
    final double arg_12_38 = arg_1[12];
    final double arg_13_39 = arg_1[13];
    final double arg_14_42 = arg_1[14];
    final double arg_15_43 = arg_1[15];
    final double arg_16_46 = arg_1[16];
    final double arg_17_47 = arg_1[17];
    final double arg_18_50 = arg_1[18];
    final double arg_19_51 = arg_1[19];
    final double arg_20_54 = arg_1[20];
    final double arg_21_55 = arg_1[21];
    final double arg_22_58 = arg_1[22];
    final double arg_23_59 = arg_1[23];
    final double arg_24_62 = arg_1[24];
    final double arg_25_63 = arg_1[25];
    final double arg_26_66 = arg_1[26];
    final double arg_27_67 = arg_1[27];
    final double arg_28_70 = arg_1[28];
    final double arg_29_71 = arg_1[29];
    final double arg_30_74 = arg_1[30];
    final double arg_31_75 = arg_1[31];
    final double re_344 = arg_0_14 + arg_16_46;
    final double im_345 = arg_1_15 + arg_17_47;
    final double re_350 = arg_0_14 - arg_16_46;
    final double im_351 = arg_1_15 - arg_17_47;
    final double re_374 = arg_8_30 + arg_24_62;
    final double im_375 = arg_9_31 + arg_25_63;
    final double re_380 = arg_8_30 - arg_24_62;
    final double im_381 = arg_9_31 - arg_25_63;
    final double re_396 = re_344 + re_374;
    final double im_397 = im_345 + im_375;
    final double re_402 = re_344 - re_374;
    final double im_403 = im_345 - im_375;
    final double re_411 = re_380 * 6.123233995736766e-17D - im_381;
    final double im_413 = re_380 + im_381 * 6.123233995736766e-17D;
    final double re_418 = re_350 + re_411;
    final double im_419 = im_351 + im_413;
    final double re_424 = re_350 - re_411;
    final double im_425 = im_351 - im_413;
    final double re_458 = arg_4_22 + arg_20_54;
    final double im_459 = arg_5_23 + arg_21_55;
    final double re_464 = arg_4_22 - arg_20_54;
    final double im_465 = arg_5_23 - arg_21_55;
    final double re_488 = arg_12_38 + arg_28_70;
    final double im_489 = arg_13_39 + arg_29_71;
    final double re_494 = arg_12_38 - arg_28_70;
    final double im_495 = arg_13_39 - arg_29_71;
    final double re_510 = re_458 + re_488;
    final double im_511 = im_459 + im_489;
    final double re_516 = re_458 - re_488;
    final double im_517 = im_459 - im_489;
    final double re_525 = re_494 * 6.123233995736766e-17D - im_495;
    final double im_527 = re_494 + im_495 * 6.123233995736766e-17D;
    final double re_532 = re_464 + re_525;
    final double im_533 = im_465 + im_527;
    final double re_538 = re_464 - re_525;
    final double im_539 = im_465 - im_527;
    final double re_555 = re_396 + re_510;
    final double im_556 = im_397 + im_511;
    final double re_561 = re_396 - re_510;
    final double im_562 = im_397 - im_511;
    final double re_571 = re_532 * 0.7071067811865476D - im_533 * 0.7071067811865475D;
    final double im_574 = re_532 * 0.7071067811865475D + im_533 * 0.7071067811865476D;
    final double re_579 = re_418 + re_571;
    final double im_580 = im_419 + im_574;
    final double re_585 = re_418 - re_571;
    final double im_586 = im_419 - im_574;
    final double re_594 = re_516 * 6.123233995736766e-17D - im_517;
    final double im_596 = re_516 + im_517 * 6.123233995736766e-17D;
    final double re_601 = re_402 + re_594;
    final double im_602 = im_403 + im_596;
    final double re_607 = re_402 - re_594;
    final double im_608 = im_403 - im_596;
    final double re_617 = re_538 * -0.7071067811865475D - im_539 * 0.7071067811865476D;
    final double im_620 = re_538 * 0.7071067811865476D + im_539 * -0.7071067811865475D;
    final double re_625 = re_424 + re_617;
    final double im_626 = im_425 + im_620;
    final double re_631 = re_424 - re_617;
    final double im_632 = im_425 - im_620;
    final double re_682 = arg_2_18 + arg_18_50;
    final double im_683 = arg_3_19 + arg_19_51;
    final double re_688 = arg_2_18 - arg_18_50;
    final double im_689 = arg_3_19 - arg_19_51;
    final double re_712 = arg_10_34 + arg_26_66;
    final double im_713 = arg_11_35 + arg_27_67;
    final double re_718 = arg_10_34 - arg_26_66;
    final double im_719 = arg_11_35 - arg_27_67;
    final double re_734 = re_682 + re_712;
    final double im_735 = im_683 + im_713;
    final double re_740 = re_682 - re_712;
    final double im_741 = im_683 - im_713;
    final double re_749 = re_718 * 6.123233995736766e-17D - im_719;
    final double im_751 = re_718 + im_719 * 6.123233995736766e-17D;
    final double re_756 = re_688 + re_749;
    final double im_757 = im_689 + im_751;
    final double re_762 = re_688 - re_749;
    final double im_763 = im_689 - im_751;
    final double re_796 = arg_6_26 + arg_22_58;
    final double im_797 = arg_7_27 + arg_23_59;
    final double re_802 = arg_6_26 - arg_22_58;
    final double im_803 = arg_7_27 - arg_23_59;
    final double re_826 = arg_14_42 + arg_30_74;
    final double im_827 = arg_15_43 + arg_31_75;
    final double re_832 = arg_14_42 - arg_30_74;
    final double im_833 = arg_15_43 - arg_31_75;
    final double re_848 = re_796 + re_826;
    final double im_849 = im_797 + im_827;
    final double re_854 = re_796 - re_826;
    final double im_855 = im_797 - im_827;
    final double re_863 = re_832 * 6.123233995736766e-17D - im_833;
    final double im_865 = re_832 + im_833 * 6.123233995736766e-17D;
    final double re_870 = re_802 + re_863;
    final double im_871 = im_803 + im_865;
    final double re_876 = re_802 - re_863;
    final double im_877 = im_803 - im_865;
    final double re_893 = re_734 + re_848;
    final double im_894 = im_735 + im_849;
    final double re_899 = re_734 - re_848;
    final double im_900 = im_735 - im_849;
    final double re_909 = re_870 * 0.7071067811865476D - im_871 * 0.7071067811865475D;
    final double im_912 = re_870 * 0.7071067811865475D + im_871 * 0.7071067811865476D;
    final double re_917 = re_756 + re_909;
    final double im_918 = im_757 + im_912;
    final double re_923 = re_756 - re_909;
    final double im_924 = im_757 - im_912;
    final double re_932 = re_854 * 6.123233995736766e-17D - im_855;
    final double im_934 = re_854 + im_855 * 6.123233995736766e-17D;
    final double re_939 = re_740 + re_932;
    final double im_940 = im_741 + im_934;
    final double re_945 = re_740 - re_932;
    final double im_946 = im_741 - im_934;
    final double re_955 = re_876 * -0.7071067811865475D - im_877 * 0.7071067811865476D;
    final double im_958 = re_876 * 0.7071067811865476D + im_877 * -0.7071067811865475D;
    final double re_963 = re_762 + re_955;
    final double im_964 = im_763 + im_958;
    final double re_969 = re_762 - re_955;
    final double im_970 = im_763 - im_958;
    final double re_1004 = re_917 * 0.9238795325112867D - im_918 * 0.3826834323650898D;
    final double im_1007 = re_917 * 0.3826834323650898D + im_918 * 0.9238795325112867D;
    final double re_1028 = re_939 * 0.7071067811865476D - im_940 * 0.7071067811865475D;
    final double im_1031 = re_939 * 0.7071067811865475D + im_940 * 0.7071067811865476D;
    final double re_1052 = re_963 * 0.38268343236508984D - im_964 * 0.9238795325112867D;
    final double im_1055 = re_963 * 0.9238795325112867D + im_964 * 0.38268343236508984D;
    final double re_1075 = re_899 * 6.123233995736766e-17D - im_900;
    final double im_1077 = re_899 + im_900 * 6.123233995736766e-17D;
    final double re_1098 = re_923 * -0.3826834323650897D - im_924 * 0.9238795325112867D;
    final double im_1101 = re_923 * 0.9238795325112867D + im_924 * -0.3826834323650897D;
    final double re_1122 = re_945 * -0.7071067811865475D - im_946 * 0.7071067811865476D;
    final double im_1125 = re_945 * 0.7071067811865476D + im_946 * -0.7071067811865475D;
    final double re_1146 = re_969 * -0.9238795325112867D - im_970 * 0.3826834323650899D;
    final double im_1149 = re_969 * 0.3826834323650899D + im_970 * -0.9238795325112867D;
    final double[] res_1313 = new double[32];
    res_1313[0] = re_555 + re_893;
    res_1313[1] = im_556 + im_894;
    res_1313[2] = re_579 + re_1004;
    res_1313[3] = im_580 + im_1007;
    res_1313[4] = re_601 + re_1028;
    res_1313[5] = im_602 + im_1031;
    res_1313[6] = re_625 + re_1052;
    res_1313[7] = im_626 + im_1055;
    res_1313[8] = re_561 + re_1075;
    res_1313[9] = im_562 + im_1077;
    res_1313[10] = re_585 + re_1098;
    res_1313[11] = im_586 + im_1101;
    res_1313[12] = re_607 + re_1122;
    res_1313[13] = im_608 + im_1125;
    res_1313[14] = re_631 + re_1146;
    res_1313[15] = im_632 + im_1149;
    res_1313[16] = re_555 - re_893;
    res_1313[17] = im_556 - im_894;
    res_1313[18] = re_579 - re_1004;
    res_1313[19] = im_580 - im_1007;
    res_1313[20] = re_601 - re_1028;
    res_1313[21] = im_602 - im_1031;
    res_1313[22] = re_625 - re_1052;
    res_1313[23] = im_626 - im_1055;
    res_1313[24] = re_561 - re_1075;
    res_1313[25] = im_562 - im_1077;
    res_1313[26] = re_585 - re_1098;
    res_1313[27] = im_586 - im_1101;
    res_1313[28] = re_607 - re_1122;
    res_1313[29] = im_608 - im_1125;
    res_1313[30] = re_631 - re_1146;
    res_1313[31] = im_632 - im_1149;
    return res_1313;
  }
}

class Complex {
	public final double im;
	public final double re;
	
	Complex(double r) {
		this (java.lang.Math.cos(6.283185307179586D * r), java.lang.Math.sin(6.283185307179586D * r));
	}
	
	Complex(double re, double im) {
		this.re = re;
		this.im = im;
	}
	
	fft.Complex add(fft.Complex that) {
		return new fft.Complex(this.re + that.re, this.im + that.im);
	}
	
	double getIm() {
		return this.im;
	}
	
	double getRe() {
		return this.re;
	}
	
	fft.Complex mul(fft.Complex that) {
		return new fft.Complex(this.re * that.re - this.im * that.im, this.re * that.im + this.im * that.re);
	}
	
	fft.Complex sub(fft.Complex that) {
		return new fft.Complex(this.re - that.re, this.im - that.im);
	}
	
	public java.lang.String toString() {
		return "" + this.re + "+i*" + this.im;
	}
}
//--------------------------------------   1 sec - JScp version 0.1.94 ---