Question 3 of 6: Why a longer zero-padded DFT runs faster

Question 3: Why a longer zero-padded DFT runs faster (12 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $N_a = 498$ nonzero samples; the 498-point DFT costs $t_a = 1$ s. Fourteen trailing zeros give $N_b = 498 + 14 = 512$ samples, and the 512-point DFT costs $t_b = 9.29$ ms. Both transforms are computed on the same machine with the same library.

Find. (a) a qualitative explanation of why the longer transform is the faster one, and (b) an arithmetic justification of the observed speed ratio.

Approach. Separate two independent facts: zero-padding does not add information, it only samples the same DTFT more finely; and the cost of a DFT depends on how the transform length factors, not on how large it is.

1. Dispose of the "more samples" half of the paradox. Appending zeros does not change the underlying DTFT: $X_1(e^{j\omega}) = X(e^{j\omega})$ because the added samples are zero. What changes is the grid on which that DTFT is sampled, $$X_1[k] = X(e^{j\omega})\Big|_{\omega = 2\pi k/512}, \qquad k = 0,\ldots,511,$$

   so the 512-point transform supplies 512 samples of the same curve instead of 498. Zero-padding is frequency-domain interpolation; no resolution is gained, because resolution is set by the 498 genuine samples of data.

2. Identify the real cause of the speed difference: the factorisation of $N$. Factoring the two lengths, $$498 = 2 \times 3 \times 83, \qquad 512 = 2^{9}.$$

   Because 83 is prime, 498 admits no decomposition into small radices beyond a single factor of 2 and 3, so a general-purpose routine falls back on the direct sum — an $\mathcal{O}(N^2)$ computation. In contrast 512 is a pure power of two, so the transform decomposes nine times, which is the radix-2 fast Fourier transform.

Complex multiplies against transform length: the direct DFT (upper curve, N^2) against the radix-2 FFT (lower curve, (N/2)log2 N). The two dashed lines mark N = 498 and N = 512.
3. Count the direct-DFT operations. Evaluating $$X[k] = \sum_{n=0}^{N-1} x[n]\,W_N^{kn}, \qquad k = 0,\ldots,N-1,$$

   costs one complex multiply and one complex add per $(n,k)$ pair, so

   $$M_{\text{direct}} = N_a^{2} = 498^{2} = 248\,004 \ \text{complex multiplies}.$$
4. Count the radix-2 FFT operations. A decimation-in-time radix-2 FFT of length $N_b = 2^{\nu}$ has $\nu = \log_2 N_b$ stages of $N_b/2$ butterflies, one twiddle multiply each:
   $$M_{\text{FFT}} = \frac{N_b}{2}\log_2 N_b = \frac{512}{2}\times 9 = 256 \times 9 = 2304 \ \text{complex multiplies}.$$
5. Form the ratio and compare with the measurement. The predicted speed-up is $$\frac{M_{\text{direct}}}{M_{\text{FFT}}} = \frac{248\,004}{2304} = 107.64,$$

   so if the run time is proportional to the multiply count the 512-point transform should take

   $$t_b = \frac{t_a}{107.64} = \frac{1\ \text{s}}{107.64} = \boxed{\,9.29\ \text{ms}\,}$$

   which is exactly the measured figure, and the measured ratio $1/(9.29\times10^{-3}) = 107.6$ reproduces the predicted one to three significant figures. Expressed in real multiplies (one complex multiply is four real ones) the counts are $992\,016$ against $9216$ — the same ratio.

6. State the engineering conclusion. There is no paradox: the two computations are different algorithms, not the same algorithm at two lengths. Padding to a highly composite length buys a factor of a hundred in time at the cost of fourteen stored zeros, and costs nothing in accuracy because the extra DFT bins interpolate a curve that was already fully determined. This is why practical spectrum analysis always pads to a power of two (or to another highly composite length such as $480 = 2^{5}\cdot3\cdot5$) rather than transforming the raw record length.