## Re: Sourcecode 2D-FFT

Nils Haeck writes:

##### Quote

The shit hits the fan though if you try to do series with lengths of e.g.

1023, or any large prime, since it can not be split up into factors, and thus

it resorts to a very lengthy operation of the standard discrete fourier

transform.

Actually, there are O(N log N) FFT algorithms even for prime N,

although the constant factors are several times worse than for nearby

composite sizes. Google for Rader's FFT algorithm and Bluestein's FFT

algorithm.

(Our FFTW library,

www.fftw.org, supports multidimensional FFTs of

arbitrary sizes, including primes, exploiting SSE, of both real and

complex data. It is in C, but of course it is possible to call a C

.DLL file from Delphi: see the instructions at

fftw.org/install/windows.html)

##### Quote

Btw, the complex FFT can help for sound, because in complex 1D FFT you

transform a real and imaginary part of a complex number. You can fill the

left channel in the real part, the right channel in the imag part, and then

for the price of 1 you can do stereo FFT :)

Note that you then have to disentangle the output (this is described in

e.g. Numerical Recipes) with an extra pass over the data. Especially

for the case of a 2d FFT, it is likely to be more efficient to use an

FFT specialized for real data.

Regards,

Steven G. Johnson