DFT Implementations, including FFT

DFT.cs

private static Complex[] DFTDirectComputation(Complex[] input)
{
    int N = input.Length;
    Complex[] output = new Complex[input.Length];
    for (int k = 0; k < input.Length; k++)
    {
        var sum = new Complex();
        for (int n = 0; n < input.Length; n++)
        {
            sum += input[n] * WFunction(N, k * n);
        }
        output[k] = sum;
    }

    return output;
}

private static Complex[] DFTSlightlyFaster(Complex[] input)
{
    int N = input.Length;
    Complex[] output = new Complex[input.Length];

    for (int k = 0; k < input.Length; k++)
    {
        var evenSum = new Complex();
        var oddSum = new Complex();
        for (int m = 0; m < N / 2; m++)
        {
            evenSum += input[2 * m] * WFunction(N / 2, k * m);
            oddSum += input[2 * m + 1] * WFunction(N / 2, k * m);
        }

        oddSum = oddSum * WFunction(N, k);
        output[k] = evenSum + oddSum;
    }

    return output;
}

private static Complex[] DFTUsingFFT(Complex[] input)
{
    int N = input.Length;
    Complex[] output = new Complex[input.Length];

    if (input.Length == 1)
    {
        output[0] = input[0];
    }
    else
    {
        Complex[] evenPoints = input.Where((c, i) => i % 2 == 0).ToArray();
        Complex[] oddPoints = input.Where((c, i) => i % 2 == 1).ToArray();

        Complex[] evenDft = DFTUsingFFT(evenPoints);
        Complex[] oddDft = DFTUsingFFT(oddPoints);

        for (int k = 0; k < N / 2; k++)
        {
            output[k] = evenDft[k] + WFunction(N, k) * oddDft[k];
            output[k + N / 2] = evenDft[k] - WFunction(N, k) * oddDft[k];
        }
    }

    return output;
}

private static Complex WFunction(
    int N,
    int expOfW
)
{
    return new Complex(Math.Cos((2 * Math.PI / N) * expOfW), -Math.Sin((2 * Math.PI / N) * expOfW));
}