To fit a tabulated function with a Fourier approximation Fast Fourier Transform methods are used.  This type of method factors the Fourier transform into the product of two transforms, if the number M of data points can be factored. Using complex notation, the coefficients are given by

     1   M-1             2pi
C_k = ——   å  F(x_p) EXP(- ———— k x_p )
     M   p=0              L

We will assume the interval to be [0,2p] so its length is L=2p.  Also, the points are assumed to be evenly spaced and M is assumed to be even.

Let's call M=M₀.  If M₀ is factorable into  M₀=H₀ H₁ we write

                                                        2p
k = K₁ H₁ + K₀  ;  p = p₁ H₀ + p₀  ;  M₁ = M₀/H₀  ;  x_p= ———— p
                                                        M₀

Some manipulation would bring us to the desired factorization:

     1   H₀-1        2pi        H₁-1        2pi
C_k = ——   å   EXP(- ————— K₀ p₀) å   EXP(- ————— K₁p₁) F(p₀+p₁H₀)
     M₀  p₀=0         M₀        p₁=0         M₁

Of course, if H₁ can be in turn factored, then the second å can be further factored into two other å's.

With multivariable functions the program takes advantage of the fact that the grid is rectangular to shorten the computations.

An example of a tabulated function in two variables which can be approximated by the FOURIER TRANSFORMS program is:

    y: 0   p/2   p    3p/2  2p 
x:   
0      2   -1    2    -3     2  
p/2    4    1    4    -1     4  
p      2   -1    2    -3     2  
3p/2   0   -3    0    -5     0  
2p     2   -1    2    -3     2  

Note that, even though there are 5 values in each direction, only 4 of the function's values are independent because its value at the interval's end point must be the same as at the initial point because of the required periodicity.

The correlation coefficient is computed with

       å [f_estimated - f_mean]²
SQR ( —————————————————————— )
            å [f-f_mean]²

where the summations are over all independent data points.

The standard error of estimate is calculated using

       å [f - f_estimated ]²
SQR ( ———————————————————— )
               N-2

where the summations are also over all independent data points.

The f_estimated is found using the approximation obtained.