Home → Magazine Archive → November 1968 (Vol. 11, No. 11) → Algorithms: Algorithm 338: algol procedures for the... → Abstract

Algorithms: Algorithm 338: algol procedures for the fast Fourier transform

By Richard C. Singleton

Communications of the ACM, Vol. 11 No. 11, Pages 773-776

The following procedures are based on the Cooley-Tukey algorithm [1] for computing the finite Fourier transform of a complex data vector; the dimension of the data vector is assumed here to be a power of two. Procedure COMPLEXTRANSFORM computes either the complex Fourier transform or its inverse. Procedure REALTRANSFORM computes either the Fourier coefficients of a sequence of real data points or evaluates a Fourier series with given cosine and sine coefficients. The number of arithmetic operations for either procedure is proportional to n log2 n, where n is the number of data points.

The full text of this article is premium content


No entries found