import java.io.*;

class SCO11M
{  //Hızlı Fourier transformu
/*
   This computes an in-place complex-to-complex FFT 
   x and y are the real and imaginary arrays of 2^m points.
   dir =  1 gives forward transform
   dir = -1 gives reverse transform 
*/

public static double[][] FFT(int dir,double x[],double y[])
{
   int m=x.length;
   int n,i,i1,j,k,i2,l,l1,l2;
   double c1,c2,tx,ty,t1,t2,u1,u2,z;
   double a[][]=new double[2][m];
   /* Calculate the number of points */
   n = 1;
   for (i=0;i<m;i++) 
      n *= 2;

   /* Do the bit reversal */
   i2 = n >> 1;
   j = 0;
   for (i=0;i<n-1;i++) {
      if (i < j) {
         tx = x[i];
         ty = y[i];
         x[i] = x[j];
         y[i] = y[j];
         x[j] = tx;
         y[j] = ty;
      }
      k = i2;
      while (k <= j) {
         j -= k;
         k >>= 1;
      }
      j += k;
   }

   /* Compute the FFT */
   c1 = -1.0; 
   c2 = 0.0;
   l2 = 1;
   for (l=0;l<m;l++) {
      l1 = l2;
      l2 <<= 1;
      u1 = 1.0; 
      u2 = 0.0;
      for (j=0;j<l1;j++) {
         for (i=j;i<n;i+=l2) {
            i1 = i + l1;
            t1 = u1 * x[i1] - u2 * y[i1];
            t2 = u1 * y[i1] + u2 * x[i1];
            x[i1] = x[i] - t1; 
            y[i1] = y[i] - t2;
            x[i] += t1;
            y[i] += t2;
         }
         z =  u1 * c1 - u2 * c2;
         u2 = u1 * c2 + u2 * c1;
         u1 = z;
      }
      c2 = Math.sqrt((1.0 - c1) / 2.0);
      if (dir == 1) 
         c2 = -c2;
      c1 = Math.sqrt((1.0 + c1) / 2.0);
   }

   /* Scaling for forward transform */
   if (dir == 1) {
      for (i=0;i<n;i++) {
         x[i] /= n;
         y[i] /= n;
      }
   }
   for (i=0;i<m;i++) {a[0][i]=x[i];a[1][i]=y[i];}
   return a;
}

public static double[] xi(int m)
{
   int nn=2*m;
   double pi=Math.PI;
   double x[]=new double[nn];
   for(int j=0;j<nn;j++)  {x[j]=-pi+j*pi/m;}
   return x;              
}

public static int[] decompose(int K,int p)
{  int z=K;
   int k[]=new int[p+1];
   for(int i=0;i<=p;i++)
   {    	   
   if((z-(z/2)*2)!=0) {k[i]=1;}
   z/=2; 
   } 
return k;
}

public static int compose0(int [] k,int p)
{  int K=0;
   int sayi=1;
   for(int i=0;i<=p;i++)
   {K+=k[i]*sayi;sayi*=2;} 
   return K;
}

public static int compose1(int [] k,int p)
{  int K=0;
   int sayi=1;
   for(int i=0;i<=p;i++)
   {K+=k[p-i]*sayi;sayi*=2;} 
   return K;
}


public static int compose2(int [] k,int p,int q)
{  int K=0;
   int sayi=1;
   for(int i=q;i<=p;i++)
   {K+=k[i]*sayi;sayi*=2;} 
   return K;
}

public static int compose3(int [] k,int p,int q)
{  int sayi=1;
   int K=0;
   for(int i=1;i<=q;i++) sayi*=2;
   for(int i=q;i<=p;i++)
   {K+=k[i]*sayi;sayi*=2;} 
   return K;
}
  
public static double[][] FFT(double x[],double y[])
{   //a b arası eşit aralıklı noktalar
    double PI=Math.PI;
    int nn=y.length;
    int m=nn/2;
    int M=m;
    double pp=Math.log(m)/Math.log(2.0);
    System.out.println("m= "+m+"pp="+pp);
    int p=(int)pp;
    int q=p;
    complex e=complex.exp(PI/m);
    System.out.println("e="+complex.toString(e));
    complex c[]=new complex[nn];
    double a[]=new double[m+1];
    double b[]=new double[m+1];
    b[0]=0.0;
    b[m]=0.0;
    int k[]=new int[p];
    int K1,K2;
    complex ksi[]=new complex[nn+1];
    complex eta; 
    for(int j=0;j<nn;j++) c[j]=new complex(y[j]);
    for(int j=1;j<=M;j++) 
    {ksi[j]=complex.exp(PI*j/m);
     ksi[j+M]=complex.exp(-PI*j/m);
     System.out.println("ksi["+j+"]="+complex.toString(ksi[j])+"ksi["+(j+M)+"]="+complex.toString(ksi[j+M]));
    }
    int K=0;
    ksi[0]=new complex(1.0);
    
    for(int L=1;L<=(p+1);L++)
    {
	while(K<(2*m-1))
	  {for(int j=1;j<=M;j++)
	    {k=decompose(K,p);K1=compose2(k,p,q);K2=compose3(k,p,q);
	     eta=complex.add(c[K],complex.multiply(ksi[K2],(double)M));
	     c[K+M]=complex.substract(c[K],eta);
	     c[K]=complex.add(c[K],eta);
	     K++;
	    }
	  K=K+M;
	  }
	K=0;
	M=M/2;
	q=q-1;
	while(K<(2*m-1))
	  {
	  k=decompose(K,p);
	  int j=compose1(k,p);
	  complex dummy=c[j];
	  
	  if(j>K) {c[j].assign(c[K]);c[K].assign(dummy);}
	  K++;
	  }
	a[0]=complex.multiply(c[0],(double)m).real();
	complex z=complex.exp(-PI*m);
	a[m]=(complex.multiply(z,complex.divide(c[m],m))).real();
	for(int j=1;j<(m-1);j++)
	{z=complex.exp(-PI*j);
	complex z1=complex.multiply(z,complex.divide(c[j],m)); 
	a[j]=z1.real();
	b[j]=z1.imaginary();
	}
	}
    double w[][]=new double[2][m+1];
    for(int j=0;j<=m;j++)
    {w[0][j]=a[j];
     w[1][j]=b[j];
    }
     return w;
}
/*
public static double funcFFT(double C[],double a,double b,double x)
{
    double t=2.0*(x-a)/(b-a)-1;
    //System.out.println("t="+t);
    int n=C.length;
    double ff=0;
    if(n!=0.0)
    {  for(int i=0;i<n;i++)
       {ff+=C[i]*Ti(t,i);}
    } 
    return ff;
}
*/

  public static void main(String args[]) throws IOException
  {
  int K=15;
  int p=5;
  System.out.println(Matrix.reversetoString(decompose(K,p)));
  double PI=Math.PI;
  double x[]=new double[4];
  double y[]=new double[4];
  for(int i=0;i<4;i++) {x[i]=-PI+PI*i/2.0;y[i]=2.0*x[i]*x[i]-9.0;System.out.println(x[i]+" "+y[i]);}
  System.out.println(Matrix.toString( FFT(x,y))); 
  
  }
}