Provide a non-allocating, pure-rust FFT

[mitchmindtree]

I might be vastly underestimating the work and complexity involved in this, but it would be an excellent feature to have and is undoubtably a fundamental tool of DSP.

I could find three current pure-rust fourier transform implementations that might be useful for reference:

• rustfft (MIT/APACHE)
• rft (??)
• dft (MIT)

The Fourier Transform Wikipedia

Circles, Sines and Signals - An awesome explanation on how DFT works.

[andrewcsmith]

Leaving a couple things here, to look into:

• dsp stackexchange question
• nice description of an in-place algorithm

We could conceptually make this work in-place and overwrite a given &mut [Frame] with the spectrum data. It might not be the most efficient implementation, though.

[andrewcsmith]

A few months down the line—rustfft is actually fantastic (now stable at 1.0), and I've used it a lot. I would vote we just aim for interoperability with rustfft: focus on time domain / stream manipulations here, and let others focus on the frequency domain.

Rustfft looks like it already works with int values, and is attracting a lot of PRs for specific prime value optimizations, a la FFTW.