Bluestein's Algorithm

Purpose: Compute a DFT of arbitrary length $n$ — including large primes — in $O(n\log n)$, by turning it into a convolution. Also called the chirp-z transform.

The Chirp Trick

Start from the DFT and use the identity
$jk=\frac{j^2+k^2-(j-k{)}^2}{2}.$

Substituting into $X_k={\sum }_j{x}_j{\omega }^{jk}$:

$X_k={\omega }^{k^2/2}{\sum }_j\left(x_j{\omega }^{j^2/2}\right){\omega }^{-(j-k{)}^2/2}.$

The sum is a convolution of the sequences $a_j=x_j{\omega }^{j^2/2}$ and $b_m={\omega }^{-m^2/2}$. Convolutions of any length can be computed by zero-padding to a power of two and running an ordinary radix-2 FFT.

Algorithm

1. Form $a_j=x_j{\omega }^{j^2/2}$ for $j=\mathrm{0..}n-1$.
2. Form $b_m={\omega }^{-m^2/2}$ for $m=-(n-1)..(n-1)$.
3. Convolve $a$ and $b$ using FFT with padding to $N\ge 2n-1$, a power of two.
4. Multiply the result by ${\omega }^{k^2/2}$ to recover $X_k$.

Note ${\omega }^{j^2/2}$ requires a half power; use ${\omega }_{2n}=e^{i\pi /n}$ so the exponents stay integral: ${\omega }^{j^2/2}={\omega }_{2n}^{j^2}$.

Complexity

• Time: $O(n\log n)$ — three FFTs of size $\le 4n$
• Space: $O(n)$
• Constant factor: about 3-6× a native power-of-two FFT of the same length

When you need it

Situation	Use
$n$ is a power of 2	Cooley-Tukey directly
$n$ factors into small primes	mixed-radix Cooley-Tukey
$n=n_1{n}_2$, coprime	Good-Thomas
$n$ is prime	Rader or Bluestein
$n$ arbitrary, or a partial spectrum wanted	Bluestein

The competitive programming reality

You almost never need a DFT of a fixed non-power-of-two length. Zero-padding a convolution to the next power of two is correct and simpler. Bluestein earns its place for two other reasons:

1. Cyclic convolution of exact length $n$ — when wraparound matters and padding would change the answer.
2. Chirp-z evaluation — evaluating a polynomial at $n$ points in geometric progression $z^0,z^1,z^2,\dots$ in $O(n\log n)$, which is exactly what Bluestein computes and what several “evaluate at powers of $q$” problems require.

Chirp-z as polynomial evaluation

Given $P(x)$ of degree $<n$, evaluating at $\{z^k{\}}_{k=0}^{m-1}$ is

$P(z^k)={\sum }_j{p}_j{z}^{jk},$

the same shape as the DFT with $\omega$ replaced by $z$. The chirp identity applies unchanged, giving $O((n+m)\log (n+m))$ — a strictly more general tool than the DFT, and a genuinely useful one for problems involving geometric sequences of evaluation points.

Variants / Use Cases

• FFT and NTT — the topic page
• Rader’s algorithm — the other prime-length technique; uses a group-theoretic permutation instead of a chirp
• Multipoint evaluation — the $O(n{\log }^{2}n)$ method for arbitrary evaluation points
• Zoom FFT / spectral analysis — the signal-processing use of chirp-z