Good-Thomas Algorithm

Purpose: Decompose a DFT of length $n=n_1{n}_2$ with $\gcd (n_1,n_2)=1$ into $n_2$ transforms of length $n_1$ and $n_1$ transforms of length $n_2$ — with no twiddle factors at all. Also called the prime-factor algorithm (PFA).

The Idea

Cooley-Tukey also splits $n=n_1{n}_2$, but the two sub-transforms are joined by twiddle factors ${\omega }^{j_1{k}_2}$ — extra complex multiplications. Good-Thomas eliminates them entirely by choosing a smarter index map, available only when the factors are coprime.

Use the Chinese Remainder Theorem to re-index:

$j\equiv (j_1,j_2)(\mathrm{mod}(n_1,n_2)),k\equiv (k_1,k_2).$

With the CRT map applied to the input index and the Ruritanian (CRT-weighted) map to the output index, the kernel factorises cleanly:

${\omega }_n^{jk}={\omega }_{n_1}^{j_1{k}_1}{\omega }_{n_2}^{j_2{k}_2},$

with no cross terms. So the 1-D DFT of length $n$ literally becomes a 2-D DFT on an $n_1\times n_2$ grid: transform every row, then every column. Done.

Algorithm

1. Reshape the input into an $n_1\times n_2$ array using the CRT index map.
2. Apply length-$n_1$ DFTs down the columns.
3. Apply length-$n_2$ DFTs across the rows.
4. Read the output back out with the inverse index map.

Complexity

• Multiplications: strictly fewer than Cooley-Tukey — the twiddle stage is gone
• Time: $O(n\log n)$ overall when applied recursively
• The index permutations are the price, and they are cache-unfriendly

Where it is used

Good-Thomas is a real component of production FFT libraries. FFTW’s planner combines:

• Good-Thomas for coprime factors (no twiddles),
• Cooley-Tukey for non-coprime factors (twiddles required),
• Rader for prime factors,
• Bluestein as the general fallback,
• hard-coded straight-line “codelets” for small sizes.

This is why FFTW is fast at lengths like $n=1008=16\cdot 63$ that a naive radix-2 implementation would have to pad to 1024.

The takeaway idea

The reusable lesson is the CRT index map: when a problem has a size that factors into coprime parts, the CRT often lets you treat a 1-D problem as an independent multi-dimensional one, with no interaction terms. The same move appears in:

• CRT for splitting modular arithmetic into independent prime-power components;
• counting problems over ${\mathbb{Z}}_n$ that factor into independent counts over each ${\mathbb{Z}}_{p^e}$;
• multiplicative function computation, where $f(n)=\prod f(p_i^{e_i})$.

Variants / Use Cases

• Cooley-Tukey — the general (non-coprime) decomposition
• Chinese Remainder Theorem — the index map
• FFT and NTT — the topic page
• Winograd FFT — pushes the multiplication count even lower using minimal-multiplication convolution algorithms for small sizes