# The Butterfly: One Thread, One Output

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

Written as a recursion the split is elegant and useless: a GPU cannot recurse, and
allocating a tree of half-length arrays would cost more than the arithmetic saves. Turn it
inside out instead. Every level of that recursion is one **pass** over the
whole array, and every pass is the same tiny operation repeated: take two elements
`a` and `b`, and produce

```js
a + w·b        and        a - w·b
```

Two in, two out, one twiddle factor `w`. Drawn on paper the crossing lines
look like a butterfly, and the name stuck.

Here is where a half-remembered recursive formulation has to be let go. A thread does not
*own a pair* and write two cells — it owns **one output cell**, exactly
as everywhere else in this course, and it works out for itself which two inputs and which
twiddle that cell needs. Nothing is ever swapped. Given the pass's half-block size
`half`, thread `i` asks three questions:

```js
// am I the lower member of my pair, or the upper?
const j = Math.floor(i / half) % 2;
// where the LOWER member of my pair sits
const base = i - j * half;
// my position inside the half-block
const r = i % half;
```

Then `a` is element `base`, `b` is element
`base + half`, and `w = e^(-iπ·r / half)`. Both members of a pair
compute the same `w` and read the same two elements; they differ only in the sign
between them. No communication, no barrier inside a pass — the same reason the halving
ladder in Reductions needs none.

## Figures

- **twelve butterflies, and which pair you belong to is a fact about your index**

## Goal

**Goal:** write one butterfly pass over the 8-point complex
`spectrum` — the kernel takes `(spectrum, half)` and returns one
number per output cell.

## Requirements

- Work out `base` and `r` from `this.thread.x` and `half` alone
- Read *both* planes of both elements — a complex multiply needs all four numbers
- Return `a + w·b` at the lower index and `a - w·b` at the upper one
- It must be right for `half = 1`, `2` and `4`

## Hint 1 — which pair am I in?

At `half = 2` the eight threads split 0,1 | 2,3 | 4,5 | 6,7 into
blocks of four: threads 0, 1, 4, 5 have `j = 0` and pair upward; threads
2, 3, 6, 7 have `j = 1` and pair downward. Subtracting
`j * half` lands both members of a pair on the same
`base`.

## Hint 2 — which twiddle?

`r = i % half` is your position inside the half-block, and it is
all `w` depends on. At `half = 1` every `r` is 0, so
`w = 1` and the first pass is pure addition and subtraction — which is why
a sign mistake in the twiddle will not show up until `half = 2`.

## Hint 3 — the ending

Compute the whole complex result, then return only the half this thread's
plane asked for:

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

## Same idea elsewhere

The butterfly is gather-shaped on every platform, for the reason Thinking in
Parallel gives: a thread writes its own cell and nobody else's. CUDA's cuFFT keeps a whole
radix-N butterfly in registers and exchanges through shared memory or
`__shfl_xor_sync`; WGSL and Metal compute shaders do the same through workgroup
memory plus a barrier. What none of them do is have one thread write two results.

## Starter code

```js
// One pass. Eight complex numbers in, eight complex numbers out.
const gpu = new GPU({ mode });

const butterfly = gpu.createKernel(function (spectrum, half) {
  const i = this.thread.x;
  const j = Math.floor(i / half) % 2; // 0 = lower member of my pair, 1 = upper

  // TODO: which pair am I in, and where do I sit inside the half-block?
  const base = i;
  const r = 0;

  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];

  // TODO: multiply w by b, then return a + w·b at the lower index of the
  // pair and a - w·b at the upper one — this thread's plane only.
  if (this.thread.y === 0) return ar;
  return ai;
}, { output: [8, 2] });

const once = butterfly(spectrum, 1);
console.log('after half = 1, real:', once[0]);
console.log('after half = 1, imag:', once[1]);
console.log('after half = 2, real:', butterfly(spectrum, 2)[0]);
```

---

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

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