fork(7) download
copy 
  1. using System;
  2. using System.Numerics;
  3.  
  4. class Test
  5. {
  6.   static
  7.   void ft(int n, ref Complex[] f)
  8.   {
  9.     if (n > 1)
  10.     {
  11.       Complex[] g = new Complex[(int)n / 2];
  12.       Complex[] u = new Complex[(int)n / 2];
  13.  
  14.       for (int i = 0; i < n / 2; i++)
  15.       {
  16.         g[i] = f[i * 2];
  17.         u[i] = f[i * 2 + 1];
  18.       }
  19.  
  20.       ft(n / 2, ref g);
  21.       ft(n / 2, ref u);
  22.  
  23.       for (int i = 0; i < n / 2; i++)
  24.       {
  25.         float a = i;
  26.         a = (float) (-2.0 * Math.PI * a / n);
  27.         float cos = (float)Math.Cos(a);
  28.         float sin = (float)Math.Sin(a);
  29.         Complex c1 = new Complex(cos, sin);
  30.         c1 = Complex.Multiply(u[i], c1);
  31.         f[i] = Complex.Add(g[i], c1);
  32.  
  33.         f[i + (int)n / 2] = Complex.Subtract(g[i], c1);
  34.       }
  35.     }
  36.   }
  37.  
  38.   static
  39.   void inverseFt(ref Complex[] f)
  40.   {
  41.     for (int i = 0; i < f.Length; i++)
  42.     {
  43.       f[i] = Complex.Conjugate(f[i]);
  44.     }
  45.     ft(f.Length, ref f);
  46.     float scaling = (float)(1.0 / f.Length);
  47.     for (int i = 0; i < f.Length; i++)
  48.     {
  49.       f[i] = scaling * Complex.Conjugate(f[i]);
  50.     }
  51.   }
  52.  
  53.   static
  54.   void toWolframAlphaDefinition(ref Complex[] f)
  55.   {
  56.     float scaling = (float)(1.0/Math.Sqrt(f.Length));
  57.     for (int i = 0; i < f.Length; i++)
  58.     {
  59.       f[i] = scaling * Complex.Conjugate(f[i]);
  60.     }
  61.   }
  62.  
  63.   static
  64.   void demoFt()
  65.   {
  66.     int N = 4;
  67.     Complex[] f = new Complex[N];
  68.     for (int i = 0; i < f.Length; ++i)
  69.     {
  70.       f[i] = 0.6 + 0.1 * i;
  71.     }
  72.     ft(f.Length, ref f);
  73.     System.Console.WriteLine("Forward transform:");
  74.     for (int i = 0; i < f.Length; ++i)
  75.     {
  76.       System.Console.WriteLine("  " + f[i]);
  77.     }
  78.     inverseFt(ref f);
  79.     System.Console.WriteLine("Inverse transform:");
  80.     for (int i = 0; i < f.Length; ++i)
  81.     {
  82.       System.Console.WriteLine("  " + f[i]);
  83.     }
  84.   }
  85.   static void Main()
  86.   {
  87.     demoFt();
  88.   }
  89. }
Success #stdin #stdout 0.06s 23944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Forward transform:
  (3, 0)
  (-0.199999991257722, 0.2)
  (-0.2, 0)
  (-0.200000008742278, -0.2)
Inverse transform:
  (0.6, 0)
  (0.7, -2.77555905048799E-18)
  (0.8, 0)
  (0.9, 2.77555905048799E-18)
https://ideone.com/SheAor
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!