FFT: Support arbitrary sized vectors using Bluestein's algorithm
Opened this issue · 4 comments
could be based on mathnet-numerics implementation:
https://github.com/mathnet/mathnet-numerics/blob/master/src/Numerics/Providers/FourierTransform/ManagedFourierTransformProvider.Bluestein.cs#L252
Hi @gsgou,
There are some other (non-FFT) transforms in FftSharp.Experimental. If you're interested in adding BluesteinForward() and BluesteinInverse() in there, you're welcome to submit a PR!
This is slow, but it's worth noting it works for arbitrary length datasets:
double[] prime = { 1, 2, 3, 4, 5, 6, 7 };
System.Numerics.Complex[] primeComplex = prime.Select(x => new System.Numerics.Complex(x, 0)).ToArray();
System.Numerics.Complex[] result = FftSharp.Experimental.DFT(primeComplex);I don't intend to add Bluesteins to this library myself soon so I'll close this issue for now, but if you or someone else is interested in getting development started I'm happy to open it back up again! Thanks for this suggestion
... okay this may be pretty easy actually. I found this, and this could be as easy as copy/pasting it in. It looks to be under a MIT license:
https://www.nayuki.io/res/free-small-fft-in-multiple-languages/Fft.cs
This needs more work so I'm leaving it in the Experimental namespace so I can publish the package right now, but we can test this a little more thoroughly and add it into the main API soon. I'm merging #80 in so we both have access to the code if/when one of us decides to pick it up!
// this will work when I publish the new package in a few minutes
double[] prime = { 1, 2, 3, 4, 5, 6, 7 };
System.Numerics.Complex[] result = FftSharp.Experimental.Bluestein(prime);