Help for FFT11

PURPOSE

FFT11 is a VICAR applications program which computes the forward 
or inverse complex Fourier Transform on a line-by-line basis.
It is analogous to the program FFT1AP except that it does not use
the array processor and is more flexible in its input format
requirements:  it will allow any data format and most FFT sizes.
EXECUTION:

The following is the execution statement format for FFT11:

	FFT11 IN OUT SIZE INVERSE OFORM

where:	INP	is the input file,
	OUT	is the output file,
	SIZE	is the standard Vicar2 size parameter,
	INVERSE specifies whether or not the transform is inverse,
	OFORM   specifies the output data format for inverse
		 transforms.
OPERATION:

FFT11 uses subroutine DFFT (formerly module RCSFFT) to compute the fast 
fourier transform (FFT) of an input image, line by line.  For computational 
details, see Help (in DCL) for that routine.  It uses an algorithm by 
Richard C. Singleton of Stanford Research Institute.

The FFT output by the program (or input in inverse mode) is in the same
format as that of program FFT1AP.  The output of the transformation performed
by DFFT is not scaled in forward mode, and is scaled by 1/N in the
inverse mode.

If SS-1+NS exceeds the number of samples of the input image, then the input
data will be extrapolated using a cosine function.  The extrapolation
algorithm is identical to that used in FFT1AP, but results may differ slightly
as the extrapolation is performed on REAL*4 data in FFT11, but is rounded
to the input data type in FFT1AP.  This extrapolation uses a buffer of
1024 elements, which is the maximum number of samples by which the input
line can be increased.
RESTRICTIONS:

1. For an inverse transform, the input format must be complex.

2. The dimension of the FFT (i.e., the number of samples of the output in
  forward mode) may be any number, subject to the following constraints:

  a. It may not contain a prime factor greater than 23.

  b. The number of prime factors may not exceed 208.

  c. The square-free portion may not exceed 210.  (A factor P of a number
    N is square-free if it cannot be paired with another identical factor
    of N; i.e., each prime occurring an odd number of times in N is a
    square-free factor of N.  The square-free portion of N is the product
    of its square-free factors.)

E.g., 221 (=13*17) fails because the square-free part exceeds 210, and
202 (=2*101) fails because a prime factor exceeds 23, but 210 (=2*3*5*7)
and 216 (= 2**3 * 3**3) are acceptable.
TIMING:

The time required for the DFFT algorithm depends strongly on whether the
dimension of the FFT, N, is composite.  This dependance goes approximately
as N * SUMF, where SUMF is the sum of the prime factors of N.  Factors of
5 or less are favoured by special coding in the subroutine.

The following times were measured for RCSFFT on the IBM:
	0.842 sec. for N = 2048 (2**10)
	0.933 sec. for N = 2000 (2**4 * 5**3)
	1.343 sec. for N = 2187 (3**7)
	2.042 sec. for N = 2197 (13**3)

As a simple rule of thumb, choosing a power of 2 will be the most efficient.
WRITTEN BY:  L.W.Kamp,  4 Apr.1985

COGNIZANT PROGRAMMER:  L.W.Kamp

HISTORY:

  30aug90 -- changed 'COMPLEX' to 'COMP' in F.T. label.
  03may93 -- made portable
  24Oct96 -- Fixed printing of the INPUT FORMAT field (DFR)