What’s new in mixfft |
The difference between this and the previous version is the addition of the inverse fft and a version that uses a pre-calculated “context” where the sin/cos tables and factorization is stored. The benchmark numbers show that the context version is faster for small to 2048 point ffts, but beyond that there is no substantial difference. |
Is there an inverse FFT routine ? |
Yes, the inverse FFT routine is included in the package as a separate function. If you don’t like it you can write one easily based on the FFT using the fact that the Fourier transform is linear and therefore : iFFT(x) = 1/N * conj(FFT(conj(x)). |
Is there a multidimensional FFT routine ? |
I haven't got a special multidimensional FFT routine. You can write a 2D-FFT easily based on the FFT by (1) Transforming each of the rows. |
What platforms are supported ? |
I have tested the routine on a PC using the Microsoft Visual C++ compiler. Unfortunately I don't have a list of the other platforms where it has been used/tested. According to a user : It compiles and works fine on a Sun SPARC20 running Solaris 2.4 and Sun Professional C (ANSI). |
Can the routine handle any FFT length ? |
Yes, the only restriction is that the largest prime factor, P, of the FFT length you want to use must be less than or equal to maxPrimeFactor, a constant in mixfft.c, that you can set to any value. My routine calculates, as part of the algorithm, (N/P) DFT's each of length P. These DFT's are not calculated very efficiently (the execution time is proportional to P*P), and the total execution time will therefore be quite large when P is large. |
What algorithm is used ? |
The algorithm is a mixture of split radix at the upper level and special fast algorithms at the lower level. Nussbaumer (Springer Verlag) was a great source of inspiration. |