Algorithm 339: an algol procedure for the fast Fourier transform with arbitrary factors

Abstract

comment Computes the Fourier transform of 2 "~ complex data values. The arrays A[0: n--l] and B[0: n--l], where n = 2% initially contain the real and imaginary components of the data, and on exit contain the corresponding Fourier coefficient values. If inverse is false, the Fourier transform 1 n-] n--1 an go xi = ~ "-b ~ [a~ cos (~'jk/n) -b bk sin (~-jk/n)] q-~ cos (~rj), k=l and leaves the first n values as A[0], A[1], , A[n--1] and the remaining n values as B[0], B[1], ..-, Bin-l]. The procedures FFT2, REVFFT2, REORDER, and REALTRAN are used by this procedure, and must also be declared;