The Good-Thomas algorithm computes a discrete Fourier transform of size when 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 -point kernel and a -point kernel, so the computation becomes independent transforms along two array directions.
For , 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 does not satisfy the coprimality hypothesis.[ref]
Articles by others on the same topic
There are currently no matching articles.