Untitled

  public static Complex[] fastFourierTransform(int A[]) throws NotPowerOfTwoException
  {
    Complex y[] = new Complex[A.length];
    
    if(A.length == 1)
    {
      y[0] = new Complex(A[0], 0);
      return y;
    }
    
    if(A.length % 2 != 0) throw new NotPowerOfTwoException();
    
    Complex omega = new Complex(1, 0);
    Complex omegaFactor = new Complex(java.lang.Math.cos(2.0 * java.lang.Math.PI / (double)A.length), -java.lang.Math.sin(2.0 * java.lang.Math.PI / (double)A.length));
    int A0[] = new int[A.length / 2];
    int A1[] = new int[A.length / 2];
    
    Complex y0[];
    Complex y1[];
    int i;
    
    for(i = 0; i < A.length / 2; i++)
    {
      A0[i] = A[2 * i];
      A1[i] = A[2 * i + 1];
    }
    
    y0 = fastFourierTransform(A0);
    y1 = fastFourierTransform(A1);
    
    for(i = 0; i < A.length / 2; i++)
    {
      y[i] = y0[i].plus(y1[i].times(omega));
      y[i + A.length / 2] = y0[i].minus(y1[i].times(omega));
      omega = omega.times(omegaFactor);
    }
    return y;
  }