An algorithm for computing the mixed radix fast Fourier transform

Abstract
This paper presents an algorithm for computing the fast Fourier transform, based on a method proposed by Cooley and Tukey. As in their algorithm, the dimensionnof the transform is factored (if possible), andn/pelementary transforms of dimensionpare computed for each factorpofn. An improved method of computing a transform step corresponding to an odd factor ofnis given; with this method, the number of complex multiplications for an elementary transform of dimensionpis reduced from(p-1)^{2}to(p-1)^{2}/4for oddp. The fast Fourier transform, when computed in place, requires a final permutation step to arrange the results in normal order. This algorithm includes an efficient method for permuting the results in place. The algorithm is described mathematically and illustrated by a FORTRAN subroutine.

This publication has 8 references indexed in Scilit: