Good-Thomas algorithm (source code)

= Good-Thomas algorithm
{c}

= Prime-factor algorithm
{synonym}

The <Good-Thomas algorithm> computes a <discrete Fourier transform> of size $N=ab$ when $a,b$ are <coprime integers>. The <Chinese remainder theorem> reindexes samples and <frequencies> by pairs of residues. With compatible input and output permutations, the transform kernel factors into an $a$-point kernel and a $b$-point kernel, so the <computation> becomes independent transforms along two array directions.

For $N=15$, one uses lengths three and five. Unlike the usual <Cooley-Tukey FFT algorithm> factorization, the coprime reindexing eliminates the intervening twiddle-factor multiplications. The required permutations still have computational cost, and a factorization such as $16=4\cdot4$ does not satisfy the coprimality hypothesis.<Notes on the FFT by C. Sidney Burrus>[prime factor algorithm discussion]{ref}