On Computing The Fast Fourier Transform

Cooley and Tukey have proposed a fast algorithm
for computing complex Fourier transform and 
have shown major time savings in using it to compute
large transforms on a digital computer.  With n 
a 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 briefly reviewed and fast difference equation methods
for accurately computing the needed trigonometric 
function values are given.  The problem of computing
a large Fourier transform on a system with virtual 
memory is considered, and a solution is proposed.  This
method has been used to compute complex Fourier 
transforms of size n = 2^16 on a computer with 2^15
words of core storage; this exceeds by a factor of 
eight the maximum radix two transform size with fixed
allocation of this amount of core storage.  The 
method has also been used to compute large mixed radix
transforms.  A scaling plan for computing the 
fast Fourier transform with fixed-point arithmetic is also given.

CACM October, 1967

Singleton, R. C.

CA671008 JB February 27, 1978  2:03 PM

1525	5	1525
1525	5	1525
1525	5	1525
1668	5	1525
1669	5	1525
1679	5	1525
1728	5	1525
2859	5	1525
1525	6	1525
1525	6	1525
1525	6	1525
1525	6	1525
1525	6	1525
1647	6	1525
1669	6	1525
1676	6	1525
1785	6	1525