Add support for System.Numerics.Complex[]

[AlexandrSpirin]

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?

[swharden]

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:

• https://github.com/swharden/FftSharp/blob/main/src/FftSharp/Complex.cs

• https://github.com/microsoft/referencesource/blob/master/System.Numerics/System/Numerics/Complex.cs

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

[swharden]

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