Are there any bugs in fft implementation?

Question

Algorithms

The calculation of the signal spectrum using fft is implemented, the fft.cs file:

namespace FFTW
{
    using NAudio.Wave;
    using System;
    using System.Numerics;

    internal static class fft
    {
        internal static byte[] OpenWAVFile(string file)
        {
            using (WaveFileReader reader = new WaveFileReader(file))
            {
                byte[] buffer = new byte[reader.Length];
                reader.Read(buffer, 0, buffer.Length);
                return buffer;
            }
        }

        internal static Complex[] Convert(int[] value)
        {
            Complex[] buffer = new Complex[value.Length];   
            for (int i = 0; i < value.Length; i++)
            {
                // Re = value[i], Im = 0
                buffer[i] = new Complex(value[i], 0);
                buffer[i] *= 1;                            
            }
            return buffer;
        }

        internal static class FFT_V1
        {
            private static Complex w(int k, int n)
            {
                if (k % n == 0) return 1;
                double arg = -2 * Math.PI * k / n;
                return new Complex(Math.Cos(arg), Math.Sin(arg));
            }

            public static Complex[] Calculate(Complex[] value)
            {
                // Check if it is splitted enough
                if (value != null && value.Length <= 1) { return value; }

                int n = value.Length >> 1;  

                // Split even and odd
                Complex[] odd = new Complex[n];     
                Complex[] even = new Complex[n];    

                for (int i = 0; i < n; i++)
                {
                    even[i] = value[i * 2];       
                    odd[i] = value[i * 2 + 1];     
                }

                // Split on tasks
                even = Calculate(even); 
                odd = Calculate(odd);   

                // Calculate DFT
                for (int k = 0; k < n; k++)
                {
                    value[k] = even[k] + w(k, value.Length) * odd[k];
                    value[n + k] = even[k] - w(k, value.Length) * odd[k];
                }
                return value;
            }
        }
    }
}

Program.cs file:

using System.Numerics;

namespace FFTW
{
    internal class Program
    {
        private static void Main()
        {
            byte[] source = fft.OpenWAVFile(@".\source.wav");

            int[] buffer = new int[source.Length >> 1];

            for (int i = 0, k = 0; k < buffer.Length; i += 2, k++)
                buffer[k] = System.Convert.ToUInt16(source[i]) |
                    System.Convert.ToUInt16(source[i + 1] << 8);

            Complex[] spectrum1 = fft.FFT_V1.Calculate(fft.Convert(buffer));
        }
    }
}

Question to experts on algorithms, are there any errors or shortcomings in the implementation of fft?

Answer 1

Why buffer[i] *= 1;?
There is a bug with the fact that your code only works with a length equal to powers of two, but this is not checked anywhere. Usually, in order not to mess with frequent cases, expand the buffer to a power of two.
If you do with odd n, then these standard formulas do not work.
It is also possible that all sorts of off by one errors and mixed signs are scattered throughout the code (why is the argument of the sine / cosine taken with a minus sign in w()?)
Another drawback is that you call w() 2 times, when how could you remember the result of the first call.
And yet, recursion is usually expanded into cycles. The English wiki has pseudocode .

Answer 2

Well supir, did you give a sinusoid to the input? What's the output?
Disadvantages - memory is re-allocated on the dynamics with each call, adult libraries do not do this (they shift it to the user) - this affects the overall speed of work.