class Complex             //编写一个复数类，其中包含一些常用的复数方法
        {
        float real, imge ;
        Complex ()
               {}
        Complex ( float R, float I)      //两个构造方法
                 {
            real = R ;
            imge = I ;
        }
        Complex Add ( Complex A,Complex B )    //复数加
        {
          this.real = A.real+B.real ;
            this.imge = A.imge+B.imge ;
          return ( this ) ;
        }
      Complex Subtract ( Complex A,Complex B)     //减
        {
          this.real = A.real-B.real ;
          this.imge = A.imge-B.imge ;
          return ( this ) ;
        }
      Complex Multiply ( Complex A,Complex B )       //乘
        {
          this.real = (A.real*B.real)-(A.imge*B.imge) ;
          this.imge = (A.real*B.imge)+(A.imge*B.real) ;
          return ( this ) ;
       }
      Complex Divide ( Complex A,Complex B )         //除
        {
          this.real = ((A.real*B.real)+(A.imge*B.imge))/(B.real*B.real+B.imge*B.imge ) ;
          this.imge = (-(A.real*B.imge)-(A.imge*B.real))/(B.real*B.real+B.imge*B.imge ) ;
          return ( this ) ;
        }
  }

/////////////////////////////////////////////////////////////////////////////

class FFT                  
  {
  final int N=4;
  int u[]={1,0,0,1};         //初始化序列  
  Complex x[]=new Complex[N];
  int inverse(int n)          //倒序函数
    {          
    int m=0;
    int i=(int)(Math.log(N)/Math.log(2));   //i表示蝶形的列数
    while(n>0)
      {
      m+=n%2*Math.pow(2,i-1);
      i--;
      n=n>>1;
      }
    return m;
    }
  FFT()
    {
    for(int i=0;i<N;i++)
      {
      x[i]=new Complex(u[i],0);
      }
    for(int i=1;i<=(int)(Math.log(N)/Math.log(2));i++)             
      {
      int m=(int)(N/(Math.pow(2,i-1)));
      for(int j=0;j<N;j+=m)
        {
        for(int k=j,n=0;k<j+m/2;k++,n++)
          {
          Complex x1=new Complex();
          Complex x2=new Complex();
          Complex temp1=new Complex();
          x1.Add(x[k],x[k+m/2]);
          temp1.Subtract(x[k],x[k+m/2]);
          x2.Multiply(temp1,new Complex((float)(Math.cos(n*2*Math.PI/m)),(float)(Math.sin(-n*2*Math.PI/m))));
          x[k]=x1;
          x[k+m/2]=x2;
          }
        }
      }
    for(int i=0;i<N;i++)        //重新排列x[K]
      {
      if(i<inverse(i))
        {
        Complex temp=new Complex();
        temp=x[i];
        x[i]=x[inverse(i)];
        x[inverse(i)]=temp;
        }              
      }      
    for(int i=0;i<N;i++)
      {
      if(x[i].imge<0)
        System.out.println("      "+x[i].real+x[i].imge+"i");
      else
                                System.out.println("      "+x[i].real+"+"+x[i].imge+"i");
      }  
    }
  
  }

//////////////////////////////////////////////////////////////////////////////////

class Dsp
  {
  public static void main(String args[])
    {
    new FFT();
    }  
  }