using System;

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

public class GlobalFFT {
 movable Calculate( Complex[] z, int processorNumber, Channel( Complex[] ) channelZ ) {
  int np = CommWorld.Size;
  if ( np > 1 ) np -= 1; // When the program runs in distributed mode cluster's frontend is included in CommWorld.Size
  int partLength = z.Length / np;
  int shift = processorNumber * partLength;
  Complex[] partOfZ = new Complex [partLength];
  for ( int k = 0; k < partLength; k++ ) {
   partOfZ [k] = new Complex();
   for ( int j = 0; j < z.Length; j++ ) {
    double arg = 2 * Math.PI * (j + 1) * (k + shift + 1) / (double) z.Length;
    double cos = Math.Cos( arg );
    double sin = Math.Sin( arg );
    partOfZ [k].Re += z [j].Re * cos + z [j].Im * sin;
    partOfZ [k].Im += z [j].Im * cos - z [j].Re * sin;
   }
  }
  channelZ.Send( partOfZ, processorNumber );
 }

 void Get( ref Complex[] Z ) & Channel CZ( Complex[] partOfZ, int processorNumber ) {
  int shift = processorNumber * partOfZ.Length;
  for ( int i = 0; i < partOfZ.Length; i++ ) {
   Z [i + shift].Re = partOfZ [i].Re;
   Z [i + shift].Im = partOfZ [i].Im;
  }
 }

 public static void Main( string[] args ) {
  GlobalFFT fft = new GlobalFFT();
  int m = Int32.Parse( args [0] );
  Random r = new Random();
  Complex[] z = new Complex [m];
  for ( int i = 0; i < m; i++ ) z [i] = new Complex( r.NextDouble(), r.NextDouble() );
  int np = CommWorld.Size;
  if ( np > 1 ) np -= 1;
  for ( int k = 0; k < np; k++ ) fft.Calculate( z, k, fft.CZ );
  for ( int k = 0; k < np; k++ ) fft.Get( ref z );
 }
}