ABSTRACT
A direct calculation of an N-point DFT requires (N − 1)2 multiplications and N(N − 1) additions. For large N, say N > 1000, this would require too much computer time. The term Fast Fourier Transform (FFT) is used to describe a computer algorithm that reduces the amount of computer time enormously. The FFT that we describe in this chapter reduces the calculation time by a factor of 200 when N = 1024. The FFT is one of the greatest contributions to numerical analysis made in this century.
