[C#] FFT 프로그램 코드

C#은 복소수 연산을 지원한다. (using System.Numerics)

 

C#에서 FFT를 구하는 소스코드는 다음과 같다.

 

int BitRev(int n, int bits) 
{
    int rN = n;
    int cnt = bits - 1;

    n >>= 1;
    while (n > 0) 
    {
        rN = (rN << 1) | (n & 1);
        cnt--;
        n >>= 1;
    }

    return ((rN << cnt) & ((1 << bits) - 1));
}

void FFT(Complex[] buf) 
{
    int i,j,k,N;

    for (j = 1; j < buf.Length; j++)
    {
        int swapP = BitRev(j, bits);
        if (swapP <= j)
        {
            continue;
        }
        var temp = buf[j];
        buf[j] = buf[swapP];
        buf[swapP] = temp;
    }

 

    for (N = 2; N <= buf.Length; N <<= 1) 
    {
        for (i = 0; i < buf.Length; i += N) 
        {
            for (k = 0; k < N / 2; k++) 
            {
              int evenI = i + k;
              int oddI = i + k + (N / 2);
              var even = buf[evenI];
              var odd = buf[oddI];

              double term = -2 * Math.PI * k / (double)N;
              Complex exp = new Complex(Math.Cos(term), Math.Sin(term)) * odd;
     

              buf[evenI] = even + exp;
              buf[oddI] = even - exp;
           }
        }
    }
}

void Main(string[] args) 
{
      Complex[] input = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0};        
      FFT(input);
      foreach (Complex c in input) 
      {
          Console.WriteLine(c);   
      }
}