Menu
I need to multiply two polynomials each having small integral coefficients. I need a fast FFT routine in C/C++ which can convolve them. I have seen several libraries but they seem to be too large spread over multiple files. What is important is I need code which is not too long and can be very easily used and compiled in a single .c/.cpp file.
One that very well matches my needs is here. But I need something twice as fast.
308
As the name implies, the Fast Fourier Transform (FFT) is an algorithm that determines Discrete Fourier Transform of an input significantly faster than computing it directly. In computer science lingo, the FFT reduces the number of computations needed for a problem of size N from O(N^2) to O(NlogN) .
The FFT algorithm is used to convert a digital signal (x) with length (N) from the time domain into a signal in the frequency domain (X), since the amplitude of vibration is recorded on the basis of its evolution versus the frequency at that the signal appears [40].
The output of the FFT is a complex vector containing information about the frequency content of the signal. The magnitude tells you the strength of the frequency components relative to other components. The phase tells you how all the frequency components align in time.
The fast Fourier transform (FFT) is a computationally efficient method of generating a Fourier transform. The main advantage of an FFT is speed, which it gets by decreasing the number of calculations needed to analyze a waveform.
For a straightforward and easy to use FFT implementation try KissFFT. If you need absolute maximum performance though, and don't mind a little complexity, then it has to be FFTW.
174
I've adapted the smbFft function from this example on DspDimension to my needs in the past.
23
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
