Radix-3 computation of twiddle factors

Matteo Frigo

December 23, 2005

Let ω ∈ ℂ, |ω| = 1. We want to compute ω^{k} for 0 ≤ k < n. The following solution does not appear to be known. (We use it in FFTW3.)

For b_{r} ∈ −1, 0, 1, write k in base 3:

k = ∑_{i} b_{i}3^{i} .

Precompute w^{3^{i}} (accurately) and store the values in a table. To compute w^{k}, compute

w^{k} = ∏_{i} w^{b_{i}3^{i}} .

Because w^{0·3^{i}} = 1 and w^{−1·3^{i}} is the conjugate of w^{3^{i}}, all required values are readily available from the table.

Compared to its well-known base-2 analog, this scheme requires a table of size log_{3} n instead of log_{2} n, and its maximum relative error also grows as log_{3} n instead of log_{2} n.