## 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.