Stride

Every FFT explainer draws the butterflies. Almost none of them draw the thing that makes the butterflies reachable: a permutation of the input that turns a recursive even/odd split into plain nested loops over adjacent slots.

The recursion is the famous part — a transform of 16 points is two transforms of 8, which are four of 4, and the sharing is where the n log n comes from. But written as recursion it allocates: each level splits an array into evens and odds and hands down copies. The iterative version that every library actually ships has no recursion and no scratch array, and the price of that is one shuffle up front.

Bit-reverse the index and the splits are already done. Slot 3 is 0011; read it backwards and it is 1100, which is 12. Do that to all 16 and the samples land exactly where four levels of even/odd splitting would have left them — so stage 1 combines neighbours (distance 1), stage 2 pairs 2 apart, then 4, then 8, and every butterfly reads two slots and writes the same two back. The permutation is on screen as the purple braid on the left, and it is cheaper than it looks: the map is its own inverse, so it falls apart into 6 swaps and 4 slots that were already home — 0000, 0110, 1001, 1111, the palindromes.

The left column is the signal, drawn as signed bars. The five columns of dials are the state between stages: the filled core is magnitude (scaled per column, since the values grow — the column header says by how much), the needle is phase. The right column is |X[k]|, and the grey outlines behind it are a direct O(n²) DFT of the same input, drawn first. The bars land inside the outlines, every time, which is the only claim worth making: this is not an approximation.

The counter is the whole argument

The picture is identical either way; the arithmetic is not, and both numbers are counted as the code runs rather than quoted from the textbook:

Agreement with the direct DFT is 2e-15 at n = 16 — a few ULP, which is the honest answer for 32 rounded multiplies against 256 of them.

The ordering is a choice about where the mess goes

Switch order to permute the output and watch the same picture run backwards: the input walks in straight, the butterflies start 8 apart and end 1 apart, and the purple braid moves to the right-hand side, because the answer now comes out in bit-reversed order and bin 13 is sitting in row 11.

That is the real lesson. Decimation-in-time and decimation-in-frequency are not two algorithms with different costs — they are the same 32 butterflies and the same shuffle, and the only decision is whether you pay it before or after. You can even skip it entirely: convolution runs forward with a DIF transform and backward with a DIT one, and the two bit-reversals cancel. Nobody draws that either.

Things to try

• impulse, stepped by hand. One sample set at t = 1 — watch where the permutation puts it (row 8, because 8 reverses to 1) and watch every bin come out the same height.
• sine, bin 3 against sine, bin 3.5. A tone that fits the window lands in one bin with nothing either side. Move it half a bin and it has nowhere clean to land: that smear across every bin is spectral leakage, and it is why windowing exists.
• square, and count: bins 1, 3, 5, 7 only, each roughly 1/k of the first. The even bins are not small, they are zero.
• Drag the bars on the left to draw your own signal. Click any column to jump the animation to it.

Reuse

src/stride.js is a framework-free ES module — no DOM, no timers, no rendering:

• fft(x, order) — in-place radix-2 Cooley–Tukey, 'dit' (bit-reversed in, natural out) or 'dif' (natural in, bit-reversed out). Returns the spectrum plus the multiply/add counts it actually performed.
• dft(x) — the direct O(n²) transform, counting the same way, so the comparison is a measurement.
• trace(x, { order }) — one frame per unit of visible work: each bit-reversal swap, each butterfly, each slot of the output shuffle. Each frame carries { t, col, filled, outFilled, active, w, wLabel, mults, adds, note }, plus columns[] — the settled state between stages — so a renderer never re-derives the arithmetic. Same trace-per-tick shape as thread, prune and lowest-common.
• bitReverse, reversalPairs, reversalPermutation — the permutation as geometry and as the swaps it costs.
• plan(n, order) — just the butterfly schedule.
• signal(name, n) / SIGNALS — the eight presets with the sentence each one is there to make.
• simulate(x) — both orderings and the direct DFT over one input, with the three pairwise errors, which is the test.

Complex numbers are { re, im } with cadd / csub / cmul / cabs exported alongside.

Gotchas

• n must be a power of two; bitsFor throws otherwise. This is radix-2 only — no Bluestein, no mixed radix.
• Nothing is normalised. The forward transform has no 1/n, so column maxima double every stage for a DC-heavy signal; the headers print the per-column max because the dials are scaled per column.
• The trace keeps a full copy of every column, which is fine at n ≤ 64 and not what you want at 4096. Use fft for that.
• The demo bundles its own copy of stride.js (self-contained by contract); re-copy after editing src/.
• node scripts/screenshot-demo.mjs [out] [--signal=] [--n=] [--order=] [--at=end|<frame>] [--overlay=0|1] [--w=] [--h=] regenerates thumb.png through site/scripts/lib/chromium.mjs.