LABORATORY 20 · COMPUTER SCIENCE

Fast Fourier Transform (FFT) & Polynomial Multiplication: Cooley-Tukey Radix-2 Decimation, Butterfly Operations, and Frequency Domain Convolution

To investigate the algorithmic principles of the Discrete Fourier Transform (DFT), analyze the Cooley-Tukey Radix-2 Decimation-in-Time (DIT) algorithm, explore in-place bit-reversal permutations, evaluate complex twiddle factor symmetries and recurrence relations, verify the exact butterfly scaling law B(N) = k_fft · (N log₂ N) + B_0 = 0.5000 · (N log₂ N) + 0.0000 butterflies across transform sizes N ∈ [64, 4096], and apply the Convolution Theorem to achieve O(N log N) asymptotic polynomial multiplication. Explore interactive search algorithms, compare operation counts and analyse complexity scaling.

COMPUTE · BENCHMARK · ANALYSE

Your virtual algorithm laboratory.

RADIX-2 BUTTERFLY OPERATIONS B(N)—

EXECUTION STATUS

Ready to execute N benchmark.

Transform Size N (Points / Degree Bound)256 samplesSet N (samples)

Power-of-two transform sizes N ∈ [64, 128, 256, 512, 1024, 2048, 4096] (decomposition depths log₂(N) ∈ [6..12]).

Adjust N n, then execute benchmark.

Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.

Algorithmic assumptions and limits

The simulated benchmark environment models idealized double-precision complex arithmetic where radix-2 butterfly operations execute deterministically (B(N) = 0.5 N log₂ N). In physical computing systems and DSP microprocessors, execution throughput is heavily modulated by CPU L1/L2 data cache line capacity and power-of-two memory stride conflicts (cache thrashing at large strides), SIMD vector register availability (AVX-512 vs AVX2 FMA throughput), floating-point round-off accumulation across deep butterfly networks, and operating system scheduling jitter. In the Cooley-Tukey Radix-2 Decimation-in-Time FFT benchmark across transform sizes N in [64, 4096] (where N = 2^M for integer M in [6, 12]), the transform decomposes recursively into M = log₂(N) butterfly stages. At each stage s in [1..log₂(N)], the data vector is divided into contiguous blocks of length 2^s with half-span m = 2^(s-1). Exactly N/2 dual-output butterfly arithmetic operations are executed per stage to combine the lower and upper sub-transform branches with complex twiddle factors W_{2^s}^j = exp(-2πi j / 2^s). Across all log₂(N) stages, the cumulative butterfly operation count is governed by the exact deterministic invariant B(N) = (N/2) · log₂(N) = 0.5000 · (N log₂ N) + 0.0000 butterflies. When plotted against the composite complexity coordinate x = N log₂(N), ordinary least-squares regression yields an empirical slope k_fft = 0.5000 butterflies/(N log₂ N) and baseline intercept B_0 = 0.0000 butterflies with an ideal coefficient of determination R² = 1.000000.

Computational tools & environment.

Cooley-Tukey Radix-2 Decimation-in-Time Engine

Executes recursive and iterative power-of-two discrete Fourier transform decompositions by partitioning input sequences into even and odd indices.

Bit-Reversal Permutation Permuter

Performs in-place index permutation by reversing the binary bit representation of array indices, enabling non-recursive bottom-up butterfly execution.

Trigonometric Twiddle Factor Look-Up Table

Precomputes and caches complex unit circle roots of unity W_N^k = exp(-2πi k / N) = cos(2πk/N) - i sin(2πk/N) to eliminate runtime transcendental math overhead.

Dual-Path Butterfly Arithmetic Kernel Unit

Executes the core butterfly computation: u = A[k], t = W · A[k+m], A[k] = u + t, A[k+m] = u - t using fused multiply-add (FMA) complex arithmetic.

Convolution & Polynomial Multiplier Subsystem

Implements the Convolution Theorem to perform O(N log N) polynomial coefficient multiplication via forward FFT, pointwise spectral product, and inverse FFT.

Microarchitectural Profiler & Cache Monitor

Tracks processor memory hierarchy operations, L1/L2 data cache misses across butterfly stride transitions, and verifies exact regression against the theoretical bound 0.5 N log₂ N.

FOLLOW THE METHOD

A reason behind every step.

To investigate the algorithmic principles of the Discrete Fourier Transform (DFT), analyze the Cooley-Tukey Radix-2 Decimation-in-Time (DIT) algorithm, explore in-place bit-reversal permutations, evaluate complex twiddle factor symmetries and recurrence relations, verify the exact butterfly scaling law B(N) = k_fft · (N log₂ N) + B_0 = 0.5000 · (N log₂ N) + 0.0000 butterflies across transform sizes N ∈ [64, 4096], and apply the Convolution Theorem to achieve O(N log N) asymptotic polynomial multiplication. Suggested independent settings: 64, 128, 256, 512, 1024, 2048, 4096 samples.

Signal Initialization & Power-of-Two Padding

Initialize the discrete input sequence or polynomial coefficient vector across benchmark sizes N ∈ [64, 128, 256, 512, 1024, 2048, 4096]. If the original data length is not a power of two, zero-pad trailing elements to the next integral power of two N = 2^M to ensure complete binary tree decomposition.

Bit-Reversal Permutation of the Data Array

Apply the in-place bit-reversal permutation algorithm. For each index i from 0 to N-1, calculate its M-bit reversed index rev_i. If i < rev_i, swap data elements at indices i and rev_i, placing the array into the exact leaf order required for iterative bottom-up butterfly evaluations.

Twiddle Factor Precomputation & Storage

Generate the complex twiddle factor lookup array for the current transform size N. Compute W_N^k = cos(2πk/N) - i·sin(2πk/N) for each sub-problem branch, verifying half-period anti-symmetry W_N^(k + N/2) = -W_N^k and quarter-period quadrature relations.

Iterative Multi-Stage Butterfly Network Execution

Execute the iterative Cooley-Tukey butterfly stages for s = 1, 2, ..., log₂(N). At each stage s, iterate across blocks of length 2^s with half-length step m = 2^(s-1). For each pair of elements within the block, apply the butterfly kernel and increment the verified butterfly operation counter by exactly 1.

Spectral Pointwise Product & Inverse FFT Verification

For convolution and polynomial multiplication benchmarks, evaluate forward FFTs on both input operands, compute the complex pointwise vector product C_freq = A_freq ⊙ B_freq in linear O(N) operations, and execute the inverse FFT using complex conjugated twiddle factors normalized by 1/N to extract exact product coefficients.

Linearized Complexity Regression & Model Validation

Plot the observed butterfly operations B(N) against the composite coordinate x = N·log₂(N). Compute ordinary least-squares regression to verify the theoretical multiplier k_fft = 0.5000 butterflies/(N log₂ N), intercept B_0 = 0.0000 butterflies, and correlation coefficient R² = 1.00000.

YOUR NOTEBOOK · 0 OBSERVATIONS

Turn measurements into asymptotic insight.

See a complete example report ↗

Points are your recorded benchmark observations. The regression line validates Fast Fourier Transform (FFT) complexity scaling.

LINEAR ASYMPTOTIC FIT · y = mx + b

B(N) = k_fft · (N log₂ N) + B_0 = 0.5000 · (N log₂ N) + 0.0000 butterflies

#	Transform Size N (Points / Degree Bound) (samples)	Radix-2 Butterfly Operations B(N) (butterflies)	Composite complexity x = N · log₂(N) (work units)	Butterfly operations B(N) = 0.5000 · (N log₂ N) + 0.0000 (butterflies)	Remove

No readings yet. Execute a N benchmark and record it.

Calculate it yourself.

Your estimate of k_fft (butterflies / (N log₂ N))

CHECK YOUR UNDERSTANDING

Explain what the operation counts mean.

In the Cooley-Tukey Radix-2 Decimation-in-Time algorithm for an N-point sequence, how many total stages and how many butterfly operations per stage are executed?

When multiplying two degree-d polynomials A(x) and B(x) using FFT-based convolution, what minimum power-of-two transform size N must be chosen to prevent circular aliasing?

What is the symmetry property of the complex twiddle factor W_N^k = exp(-2πi k / N) that enables combining even and odd sub-transforms in a butterfly operation?