Discrete Time Signal Synthesizer
Generates multi-tone complex input signals x[n] = ∑ A_m exp(2πi f_m n / N) corrupted by white noise.
Mathematics / Fast Fourier Transform (FFT)
FREE TO EXPLORELABORATORY 30 · MATHEMATICS
Fast Fourier Transform (FFT) & Cooley-Tukey O(N log N) Complexity
Implement the radix-2 decimation-in-time Cooley-Tukey Fast Fourier Transform, evaluate twiddle factor symmetries, construct the butterfly computational graph, and quantitatively verify the 5 N log₂ N floating-point operational scaling against naive O(N²) matrix multiplication. Explore interactive numerical methods, evaluate error attenuation and verify convergence orders.
COMPUTE · CONVERGE · ANALYSE
Your virtual mathematics laboratory.
TOTAL FLOATING-POINT OPERATIONS—
COMPUTATION STATUS
Ready to execute N = 64.
Adjust N, then execute computation.
Mathematical operations are computed deterministically using 64-bit IEEE 754 precision. Residuals reflect ordinary least-squares regression across successive observations.
Numerical assumptions and limits
Radix-2 FFT requires transform lengths equal to exact powers of two; prime-length DFTs require Bluestein's algorithm or Rader's algorithm. The simulation evaluates the radix-2 Cooley-Tukey FFT across transform sizes N = 64 to 2048. Floating-point operation counts scale linearly with the normalized complexity coordinate N log₂(N)/1000, confirming the theoretical operational constant C = 5.000 with R² = 1.000000.
Computational tools & numerical modules.
Bit-Reversal Permutation Engine
Reorders input samples into bit-reversed sequence to enable in-place butterfly computation without auxiliary arrays.
Twiddle Factor Trigonometric Table
Precomputes complex roots of unity W_N^k = cos(2πk/N) - i sin(2πk/N) with 64-bit precision.
Radix-2 Butterfly Execution Unit
Executes the core 2-point butterfly computation: u = X[k], t = W · X[k+m], X[k] = u + t, X[k+m] = u - t.
FLOP Telemetry Counter
Tracks the exact count of real floating-point additions and multiplications (5 N log₂ N FLOPs total).
Power Spectral Density Visualizer
Computes magnitude spectrum |X[k]|² and visualizes frequency peaks and spectral resolution.
FOLLOW THE METHOD
A reason behind every step.
Implement the radix-2 decimation-in-time Cooley-Tukey Fast Fourier Transform, evaluate twiddle factor symmetries, construct the butterfly computational graph, and quantitatively verify the 5 N log₂ N floating-point operational scaling against naive O(N²) matrix multiplication. Standardized input settings: 64, 128, 256, 512, 1024, 2048 points.
01
Initialize Signal Vector Dimensions
Set transform size N as a power of two (N ∈ {64, 128, 256, 512, 1024, 2048}) and synthesize test signal x[n].
02
Execute Bit-Reversal Permutation
Permute the complex input array in-place by swapping each element with its bit-reversed index mirror.
03
Iterate Across log₂(N) Transform Stages
Execute stage loop s = 1 to log₂(N), doubling butterfly sub-transform length m = 2^s at each stage.
04
Compute In-Place Butterfly Operations
For each sub-transform, multiply lower branch by twiddle factor W_m^j and perform complex add/subtract.
05
Count Total FLOPs Executed
Record total floating-point operations (each complex butterfly requires 1 complex multiply [6 FLOPs] and 2 complex adds [4 FLOPs], averaging 5 N log₂ N real operations).
06
Linearize Complexity & Confirm Constant C
Plot measured kFLOPs versus normalized coordinate (N log₂(N) / 1000) and perform linear regression to confirm C = 5.000.
YOUR NOTEBOOK · 0 OBSERVATIONS
Turn measurements into mathematical insight.
Points are your recorded observations. The solid regression line validates Fast Fourier Transform (FFT) mathematical scaling.
LINEAR ASYMPTOTIC FIT · y = mx + b
FLOPs(N) = C · (N log₂(N) / 1000) + b
| # | Transform Size (N = 2^p) (points) | Total Floating-Point Operations (kFLOPs) | Normalized Complexity Coordinate (N log₂(N) / 1000) | Measured Floating-Point Operations (kFLOPs) | Remove |
|---|
No readings yet. Execute a computation and record it.
Calculate it yourself.
CHECK YOUR UNDERSTANDING