DFT2-FFT2.zip contains the code.  The file Dd(fx,y) needs to be re-ordered as part of the transform.  This is discussed in ..\Progdet\sorting\ArrayArgSwitch.doc.htm.

Simplest

(1.1)

 

 

 

The top line in (1.1) translates into a quadruple do loop in dft2d.for. The operations are the evaluation of the complex exponential.  This is done nx×ny×nfx×nfy times.

Intermediate integral

Define

(2.1)

So that

(2.2)

Equation (2.1) requires nx×nfx×ny evaluations of the complex exponential.  Equation (2.2) requires ny×nfy×nfx evaluations so that the total number is down by approximately a factor of n. 

                In the two Gaussian test, the numbers are

C:\public\TwoDFT>twodft

n2px is power of 2 > max(nx,nfx)

enter XINT, nx, nfx, n2px

15,150,250,512

enter YINT, ny, nfy, n2py

10,100,100,128

simplest transform

sec       73.0800018ßnfx*nfy*nx*ny operations

simplest intermediate transform

sec        1.3099999ßnfy*nfx*nx + reorder + nfx*nfy*ny operations

 FFT transform

sec        0.1400000ß N2y*N2px*log₂(N2px)+Nfx*N2py*log₂(N2py)) + reorder

                It can happen that for large N2P values that the intermediate method is faster than the FFT.  In general the evaluation of the complex exponential is done by multiplication which is faster than that done in the first two methods.

Figure 1  Two offset Gaussians in x and y

Figure 2 Transform outputs from the simplest transform the intermediate transform and the FFT2 transform. 

                Figure 2 demonstrates that the three transformsgive the same values.