Task 4 of 6

Drive log₂n Passes

Everything is in place: a permutation to run once, and a butterfly pass to run log₂(n) times with the half-block size doubling — 1, 2, 4, … n/2. That is the same skeleton Reductions and Prefix Sums drive their ladders with, a plain JavaScript loop over a kernel that takes the stage as an argument, ping-ponging between buffers. The difference is only what comes out the far end.

And as with a sorting network, the entire access pattern is fixed before any data is seen. Build the schedule first and print it:

const schedule = [];
for (let half = 1; half < n; half *= 2) schedule.push(half);

Eight numbers for n = 256, and not one of them could have been different for a different signal. Which pairs combine, in which pass, with which twiddle: all of it is a function of the index and the stage, so no thread ever waits on a value, no branch depends on data, and the whole transform is eight kernel launches with a barrier between them.

The signal below is a sine at bin 5 plus a half-amplitude cosine at bin 12. A tone of amplitude A sitting exactly on bin b puts magnitude A·n/2 into bin b and its mirror bin n − b, and near enough nothing anywhere else — so a correct transform of this input has exactly four non-zero bins, and you know all four numbers in advance.

Goal: build and print the 8-pass schedule before touching the data, run scramble + 8 butterfly passes over the 256 samples, and log the magnitude of bins 5 and 12.

Requirements

schedule holds the half-block sizes, doubling from 1 up to but not including n
Build it without reading signal — the schedule is complete before the first kernel call
Scramble once, then run one butterfly pass per entry, feeding each result into the next
console.log the pass count, the schedule, and the magnitudes of bins 5 and 12

Hint 1 — the loop bound

half < n, not half < n / 2. The last pass, the one with half = 128, is the one that finally combines the even-sample spectrum with the odd-sample spectrum — stop before it and you are left holding precisely the two halves task 1 started with.

Hint 2 — ping-pong

Each pass consumes the previous result and produces a new one, so a single variable is all the bookkeeping needed:

let buffer = scramble(signal);
for (let s = 0; s < schedule.length; s++) {
  buffer = butterfly(buffer, schedule[s]);
}

gpu.js locks an argument's type on a kernel's first call, and every pass hands back the same shape it took, so the chain is type-stable from the start.

Hint 3 — reading a magnitude

A bin is a complex number spread across the two planes, so its magnitude is Math.hypot(buffer[0][k], buffer[1][k]). For this signal bin 5 should come to 128 and bin 12 to 64.

Same idea elsewhere

One host-side loop issuing one launch per stage is exactly how an FFT ships: cuFFT's plan is a precomputed list of stages, WebGPU records one dispatch per pass into a command encoder, Metal encodes one compute pass each. The launches are the synchronisation — everything inside a pass is independent, and the boundary between passes is the only barrier anyone needs. It is also why FFT libraries make you build a "plan" before you hand over any data: the plan IS the schedule you just printed.

All tasks in The FFT Butterfly

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.