ABSTRACT
This chapter shows an algorithm of the fast Fourier transform (FFT) in detail. The FFT is available in the programming libraries of most computers and there are many books in which a complete computer program of the FFT can be found. The construction of a FFT program is most easily shown by the flow diagram representation. The FFT is faster than the direct computation if the number of desired outputs is larger than the one in the brackets. However, it has been noticed that the FFT drastically increases not only the speed of computation but also the accuracy. If the number N of the data exceeds the internal capacity of the computer, the computation of the FFT can be done in two stages. First, make two sequences of the data, separating the odd- and even-indexed terms. Then, feed them to the FFT separately and store the outputs in external devices such as tapes and disks.
