= 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}
Back to article page