using System;
using System.Numerics;

class Test
{
  static
  void ft(int n, ref Complex[] f)
  {
    if (n > 1)
    {
      Complex[] g = new Complex[(int)n / 2];
      Complex[] u = new Complex[(int)n / 2];

      for (int i = 0; i < n / 2; i++)
      {
        g[i] = f[i * 2];
        u[i] = f[i * 2 + 1];
      }

      ft(n / 2, ref g);
      ft(n / 2, ref u);

      for (int i = 0; i < n / 2; i++)
      {
        float a = i;
        a = (float) (-2.0 * Math.PI * a / n);
        float cos = (float)Math.Cos(a);
        float sin = (float)Math.Sin(a);
        Complex c1 = new Complex(cos, sin);
        c1 = Complex.Multiply(u[i], c1);
        f[i] = Complex.Add(g[i], c1);

        f[i + (int)n / 2] = Complex.Subtract(g[i], c1);
      }
    }
  }

  static
  void inverseFt(ref Complex[] f)
  {
    for (int i = 0; i < f.Length; i++)
    {
      f[i] = Complex.Conjugate(f[i]);
    }
    ft(f.Length, ref f);
    float scaling = (float)(1.0 / f.Length);
    for (int i = 0; i < f.Length; i++)
    {
      f[i] = scaling * Complex.Conjugate(f[i]);
    }
  }

  static
  void toWolframAlphaDefinition(ref Complex[] f)
  {
    float scaling = (float)(1.0/Math.Sqrt(f.Length));
    for (int i = 0; i < f.Length; i++)
    {
      f[i] = scaling * Complex.Conjugate(f[i]);
    }
  }

  static
  void demoFt()
  {
    int N = 4;
    Complex[] f = new Complex[N];
    for (int i = 0; i < f.Length; ++i)
    {
      f[i] = 0.6 + 0.1 * i;
    }
    ft(f.Length, ref f);
    System.Console.WriteLine("Forward transform:");
    for (int i = 0; i < f.Length; ++i)
    {
      System.Console.WriteLine("  " + f[i]);
    }
    inverseFt(ref f);
    System.Console.WriteLine("Inverse transform:");
    for (int i = 0; i < f.Length; ++i)
    {
      System.Console.WriteLine("  " + f[i]);
    }
  }
  static void Main()
  {
    demoFt();
  }
}