Accession Number : AD0643998

Title :   THE FAST FOURIER TRANSFORM.

Descriptive Note : Research Memo.,

Corporate Author : STANFORD RESEARCH INST MENLO PARK CALIF

Personal Author(s) : Singleton,Richard C.

Report Date : DEC 1966

Pagination or Media Count : 45

Abstract : Good has proposed a fast algorithm for computing the complex Fourier transform x sub j = sum from k = o to N-1 of alpha sub k exp (i2 ps jk/N) for j = 0,1,... N-1, and Cooley and Tukey have restated the algorithm and reported major time savings in using it to compute large transforms on a digital computer. With N an integer power of two, computing time for this algorithm is proportional to N log2 N, a major improvement over other methods with computing time proportional to N(2). In this paper, the fast Fourier transform algorithm is discussed, and ALGOL procedures given for the basic method plus some of its variations. ALGOL procedures organized for efficient computing on a system with a virtual memory feature are given; these procedures reduce the need for moving portions of data arrays to and from high speed memory. A method for solving very large problems by use of auxiliary memory is also proposed. Methods of using the fast Fourier transform algorithm on real data are restated, and a way of reducing computing in this case is shown. A plan of scaling for computing the fast transform with fixed-point arithmetic is outlined; this method has been used on a small computer without floating-point hardware. (Author)

Descriptors :   (*INTEGRAL TRANSFORMS, *ALGORITHMS), COMPUTER PROGRAMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE