using System;

public class Complex {

 public double Re = 0.0;
 public double Im = 0.0;

 public Complex () {}

 public Complex ( double re, double im )  {
  Re = re;
  Im = im;
 }

}

//*****************************************************************//

public class Iterative_FFT_Parallel2   {

 public static void Main ( String[] args )   {

  int N = System.Convert.ToInt32 ( args [ 0 ] ); //  N is power of 2

  Random r = new Random();

  Complex[]  a = new Complex [ N ];
  Complex[]  A = new Complex [ N ];

  for ( int i = 0; i < N; i++ )
   a [ i ] = new Complex ( r.NextDouble(), r.NextDouble() );

  DateTime dt1 = DateTime.Now;
  
  Iterative_FFT_Parallel2 ifp2 = new Iterative_FFT_Parallel2();
  
  int logN = 0;
  int m    = N;

  while ( m > 1 )
  {
   m = m / 2;
   logN++;
  }

  for ( int k = 0; k < N; k++ )
   A [ ifp2.bit_reverse ( k, logN ) ] = a [ k ];
   
  int N2 = N / 2;
  
  ifp2.Iterative_FFT ( a, A, N2, logN, 0,  ifp2.sendStop );
  ifp2.Iterative_FFT ( a, A, N2, logN, N2, ifp2.sendStop );
  
  for ( m = 0; m < 2; m++ )
   ifp2.getStop();
   
  //   Final iteration
  
  double wn_Re, wn_Im, w_Re, w_Im;
  double arg, t_Re, t_Im;

  double u_Re, u_Im, tmp;  
  
  int    jN2;
  
  arg = 2.0 * Math.PI / N;

  wn_Re = Math.Cos ( arg );
  wn_Im = Math.Sin ( arg );

  w_Re  = 1.0;
  w_Im  = 0.0;
  
  for ( int j = 0; j < N2; j++ )
  {
   jN2  = j + N2;

   t_Re = w_Re * A [ jN2 ].Re - w_Im * A [ jN2 ].Im;
   t_Im = w_Re * A [ jN2 ].Im + w_Im * A [ jN2 ].Re;

   u_Re = A [ j ].Re;
   u_Im = A [ j ].Im;

   A [ j ].Re = u_Re + t_Re;
   A [ j ].Im = u_Im + t_Im;

   A [ jN2 ].Re = u_Re - t_Re;
   A [ jN2 ].Im = u_Im - t_Im;

   tmp  = w_Re * wn_Re - w_Im * wn_Im;
   w_Im = w_Re * wn_Im + w_Im * wn_Re;
   w_Re = tmp;
  }
  
  DateTime dt2 = DateTime.Now;

  Console.WriteLine ( "N = " + N + "   Elapsed time is " + (dt2-dt1).TotalSeconds );

 }
 
 /////////////////////////////////////////////////////////////////////////////////////

 public void getStop()   &   Channel sendStop()  {
  return;
 }
 
 /////////////////////////////////////////////////////////////////////////////////////
 
 public int bit_reverse ( int k, int size )   {

  int   right_unit = 1;
  int   left_unit  = 1 << ( size - 1 );

  int   result     = 0;
  int   bit;

  for ( int i = 0; i < size; i++ )
  {
   bit = k & right_unit;
   //Console.WriteLine ( "bit = " + bit );
   if ( bit != 0 )
    result = result | left_unit;

   right_unit = right_unit << 1;
   left_unit  = left_unit  >> 1;
  }

  return ( result );

 }
 
 ////////////////////////////////////////////////////////////////////////////////////////
 
 public async Iterative_FFT ( Complex[] a, Complex[] A, int N2, int logN, int shift,
                                    Channel() sendStop                                    )
 {

  int    j, k, m, m2, km2, s;

  double wn_Re, wn_Im, w_Re, w_Im;
  double arg, t_Re, t_Im;

  double u_Re, u_Im, tmp;

  for ( s = 1; s < logN; s++ )
  {
   m = 1 << s;

   arg = 2.0 * Math.PI / m;

   wn_Re = Math.Cos ( arg );
   wn_Im = Math.Sin ( arg );

   w_Re  = 1.0;
   w_Im  = 0.0;

   m2    = m >> 1;

   for ( j = 0; j < m2; j++ )

    for ( k = j + shift; k < N2; k += m )
    {
     km2  = k + m2;

     t_Re = w_Re * A [ km2 ].Re - w_Im * A [ km2 ].Im;
     t_Im = w_Re * A [ km2 ].Im + w_Im * A [ km2 ].Re;

     u_Re = A [ k ].Re;
     u_Im = A [ k ].Im;

     A [ k ].Re = u_Re + t_Re;
     A [ k ].Im = u_Im + t_Im;

     A [ km2 ].Re = u_Re - t_Re;
     A [ km2 ].Im = u_Im - t_Im;

     tmp  = w_Re * wn_Re - w_Im * wn_Im;
     w_Im = w_Re * wn_Im + w_Im * wn_Re;
     w_Re = tmp;
    }

  }
  
  sendStop ! ();

 }
 
}