Task 3 of 6

Put the Input in the Right Order

One thing about the last task was quietly wrong. The first pass paired adjacent elements — but the split that started all this was by parity, so the first pass should be combining x[0] with x[4], x[1] with x[5]… at n = 8, and with strides that change every pass. Writing a kernel whose pair distance depends on the stage in a different way each time is possible and horrible.

The trick every iterative FFT uses instead: permute the input once, so that the pairs are adjacent at every stage afterwards. The permutation turns out to be beautifully simple — send element i to the position whose index is i with its bits reversed. At n = 8, sample 1 (binary 001) goes to position 4 (binary 100); sample 3 (011) goes to position 6 (110).

gpu.js will happily give you >>, & and |, and they produce correct answers — but each one compiles to a helper that loops over up to 32 bits in the shader, so the one-line spelling costs around eight hundred loop iterations per index. So do it in arithmetic instead, which is nine operations and, more to the point, says out loud what a bit reversal is: peel the low digit off one number and push it onto the front of another.

let v = this.thread.x;
let reversed = 0;
for (let b = 0; b < this.constants.bits; b++) {
  // push v's lowest bit onto the front of reversed
  reversed = reversed * 2 + (v % 2);
  // and drop it from v
  v = Math.floor(v / 2);
}

One happy accident is worth naming: reversing an index twice gives it back, so this permutation is its own inverse. It is the one rearrangement in the whole course where "push my value there" and "pull the value that belongs here" land on the same answer. Write it as the gather anyway — that habit is what makes the other ninety-nine cases work.

the permutation is just the index, spelled backwards

Goal: write the kernel that reads the 16 real samples of signal into bit-reversed order and presents them as a complex spectrum — real part permuted, imaginary part zero.

Requirements

Compute the reversal arithmetically, over this.constants.bits = 4 bits
It is a gather: cell i returns x[reversed]
Plane 1 (imaginary) is all zeros — the input signal is real

Hint 1 — one digit at a time

v % 2 is the lowest bit of v; Math.floor(v / 2) throws that bit away. Multiplying reversed by 2 before adding shifts everything already collected one place up, so the first bit taken ends up highest.

Hint 2 — how many bits?

Exactly log₂(n) — 4 for 16 elements. Fewer and the top bits never move; more and every index lands outside the array. It is already in this.constants.bits.

Hint 3 — the whole thing

Check yourself against the first three: 0 → 0, 1 → 8, 2 → 4. Then:

if (this.thread.y === 0) return x[reversed];
return 0;

Same idea elsewhere

The bit-reversal permutation is a named, tuned primitive everywhere: cuFFT and rocFFT fold it into the first pass's addressing so the array is never physically permuted, FFTW spends real effort on cache-friendly reversal orders, and hardware FFT blocks in DSPs ship a bit-reversed addressing mode in the address generator itself. It is also why so many library APIs offer a "bit-reversed output" variant — if you are about to multiply two spectra together and transform back, neither of them ever needs to be in order.

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.