# Drive log₂n Passes

*Task 4 of 6 · [The FFT Butterfly](https://gpu.rocks/learn/fft-butterfly-d4375da7.md) · GPU.js Learn*

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:

```js
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

**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:

```js
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.

## Starter code

```js
// The schedule first, the signal second. One launch per stage.
const gpu = new GPU({ mode });
const n = 256;

const scramble = gpu.createKernel(function (x) {
  let v = this.thread.x;
  let reversed = 0;
  for (let b = 0; b < this.constants.bits; b++) {
    reversed = reversed * 2 + (v % 2);
    v = Math.floor(v / 2);
  }
  if (this.thread.y === 0) return x[reversed];
  return 0;
}, { output: [n, 2], constants: { bits: 8 } });

const butterfly = gpu.createKernel(function (spectrum, half) {
  const i = this.thread.x;
  const j = Math.floor(i / half) % 2;
  const base = i - j * half;
  const r = i % half;

  const angle = (-Math.PI * r) / half;
  const wr = Math.cos(angle);
  const wi = Math.sin(angle);

  const ar = spectrum[0][base];
  const ai = spectrum[1][base];
  const br = spectrum[0][base + half];
  const bi = spectrum[1][base + half];
  const tr = wr * br - wi * bi;
  const ti = wr * bi + wi * br;

  if (this.thread.y === 0) {
    if (j === 0) return ar + tr;
    return ar - tr;
  }
  if (j === 0) return ai + ti;
  return ai - ti;
}, { output: [n, 2] });

const schedule = [];
// TODO: fill `schedule` with the half-block size of every pass — doubling
// from 1 while it stays below n. Notice that nothing in here can look at
// `signal`. That is the point.

console.log('passes:', schedule.length);
console.log('schedule:', JSON.stringify(schedule));

// TODO: scramble once, then run one butterfly pass per schedule entry.
let buffer = scramble(signal);

console.log('bin 5 magnitude: ', Math.hypot(buffer[0][5], buffer[1][5]));
console.log('bin 12 magnitude:', Math.hypot(buffer[0][12], buffer[1][12]));
```

---

Interactive version: https://gpu.rocks/learn/fft-butterfly-d4375da7/4

[Previous task](https://gpu.rocks/learn/fft-butterfly-d4375da7/3.md) · [Next task](https://gpu.rocks/learn/fft-butterfly-d4375da7/5.md)