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)).

All you need to do is :
(1) Change the sign on the imaginary part of the input.
(2) Calculate the FFT of the sequence.
(3) Change the sign on the imaginary part of the output.
(4) Scale by 1/N.

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.
(2) Transforming each of the resulting columns.

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.