Add support for System.Numerics.Complex[]

Why do you use your own Complex class for complex numbers, now C# has a built-in class and it looks like it can do the same thing as yours?

Hi @AlexandrSpirin, this is a good question! I think the reason I implemented my own complex number class is so it could be minimal and simple, and easily ported to other languages. Compare the complexity of these two classes:

I recognize that people who already have data in System.Numerics.Complex[] would expect a FFT library to be able to work with that standard data type. We could add support for this in a non-breaking way by overloading these two functions with essentially identical code:

FftSharp/src/FftSharp/Transform.cs

Lines 20 to 66 in 8015e0d

    
           /// <summary> 
        
           /// Compute the discrete Fourier Transform (in-place) using the FFT algorithm. 
        
           /// </summary> 
        
           /// <param name="buffer">Data to transform in-place. Length must be a power of 2.</param> 
        
           public static void FFT(Span<Complex> buffer) 
        
           { 
        
               if (buffer.Length == 0) 
        
                   throw new ArgumentException("Buffer must not be empty"); 
        
               if (!IsPowerOfTwo(buffer.Length)) 
        
                   throw new ArgumentException("Buffer length must be a power of 2"); 
        
               FFT_WithoutChecks(buffer); 
        
           } 
        
           /// <summary> 
        
           /// High performance FFT function. 
        
           /// Complex input will be transformed in place. 
        
           /// Input array length must be a power of two. This length is NOT validated. 
        
           /// Running on an array with an invalid length may throw an invalid index exception. 
        
           /// </summary> 
        
           private static void FFT_WithoutChecks(Span<Complex> buffer) 
        
           { 
        
               for (int i = 1; i < buffer.Length; i++) 
        
               { 
        
                   int j = BitReverse(i, buffer.Length); 
        
                   if (j > i) 
        
                       (buffer[j], buffer[i]) = (buffer[i], buffer[j]); 
        
               } 
        
               for (int i = 1; i <= buffer.Length / 2; i *= 2) 
        
               { 
        
                   double mult1 = -Math.PI / i; 
        
                   for (int j = 0; j < buffer.Length; j += (i * 2)) 
        
                   { 
        
                       for (int k = 0; k < i; k++) 
        
                       { 
        
                           int evenI = j + k; 
        
                           int oddI = j + k + i; 
        
                           Complex temp = new Complex(Math.Cos(mult1 * k), Math.Sin(mult1 * k)); 
        
                           temp *= buffer[oddI]; 
        
                           buffer[oddI] = buffer[evenI] - temp; 
        
                           buffer[evenI] += temp; 
        
                       } 
        
                   } 
        
               } 
        
           }

If you want to create a PR I would be happy to review it! Bonus points for demonstrating the new usage in the readme and in a new test. If you decide not to that's okay, I'll leave this issue open and implement this next time I work in this code base.

Thanks again for pointing this out!
Scott

Following-up, I'm moving these methods into their own static class with a simpler API that resembles Math.NET

// Apply FFT in place
System.Numerics.Complex[] samples = { /* */ };
FftSharp.FFT.Forward(samples);

// Get FFT from real data array
double[] samples = { /* */ };
System.Numerics.Complex[] fft = FftSharp.FFT.Forward(samples);

The Transform class will eventually be deprecated

	/// <summary>
	/// Compute the discrete Fourier Transform (in-place) using the FFT algorithm.
	/// </summary>
	/// <param name="buffer">Data to transform in-place. Length must be a power of 2.</param>
	public static void FFT(Span<Complex> buffer)
	{
	if (buffer.Length == 0)
	throw new ArgumentException("Buffer must not be empty");

	if (!IsPowerOfTwo(buffer.Length))
	throw new ArgumentException("Buffer length must be a power of 2");

	FFT_WithoutChecks(buffer);
	}

	/// <summary>
	/// High performance FFT function.
	/// Complex input will be transformed in place.
	/// Input array length must be a power of two. This length is NOT validated.
	/// Running on an array with an invalid length may throw an invalid index exception.
	/// </summary>
	private static void FFT_WithoutChecks(Span<Complex> buffer)
	{
	for (int i = 1; i < buffer.Length; i++)
	{
	int j = BitReverse(i, buffer.Length);
	if (j > i)
	(buffer[j], buffer[i]) = (buffer[i], buffer[j]);
	}

	for (int i = 1; i <= buffer.Length / 2; i *= 2)
	{
	double mult1 = -Math.PI / i;
	for (int j = 0; j < buffer.Length; j += (i * 2))
	{
	for (int k = 0; k < i; k++)
	{
	int evenI = j + k;
	int oddI = j + k + i;
	Complex temp = new Complex(Math.Cos(mult1 * k), Math.Sin(mult1 * k));
	temp *= buffer[oddI];
	buffer[oddI] = buffer[evenI] - temp;
	buffer[evenI] += temp;
	}
	}
	}
	}