# Run It Backwards for Free

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

The inverse transform differs from the forward one in two small ways: the exponent
is `+2πi·kt/n` instead of `-`, and the result is divided by n. You
could write a second set of kernels. You do not have to — there is an identity that gets the
inverse out of the forward transform you already have:

```js
ifft(X) = conj( fft( conj(X) ) ) / n
```

Conjugating flips the sign of every imaginary part, which is exactly the sign flip the
exponent needs; doing it on the way in and again on the way out leaves everything else where
it was. Nine lines of kernel and a division, and the transform runs both ways.

And then the warning, which is the real content of this task. A round trip is a
**consistency** check, not a correctness check — it proves your inverse undoes
your forward transform, and nothing else. Flip the twiddle sign in the butterfly and the
forward transform computes the conjugate of the right spectrum; run it through this same
inverse and the signal comes back *perfectly*, to the last bit. The magnitudes were
already identical, the round trip is clean, and every plot looks right. The only thing that
catches it is the comparison you did in the last task: against the definition.

## Goal

**Goal:** write the conjugate-and-scale kernel, use it at both ends of a
forward transform to invert one, and confirm the 256 samples come back.

## Requirements

- One kernel `conjugate(spectrum, scale)`, used at both ends — it negates the imaginary plane and multiplies both planes by `scale`
- Going in the scale is `1`; coming out it is `1 / n`
- The recovered imaginary plane is ~0 — a real signal in, a real signal out
- `console.log` the largest round-trip error and the verdict

## Hint 1 — conjugation, both planes at once

The kernel owns one output cell, and which plane it is decides the sign:

```js
if (this.thread.y === 0) return spectrum[0][this.thread.x] * scale;
return -spectrum[1][this.thread.x] * scale;
```

The real part keeps its sign. Only the imaginary part turns over.

## Hint 2 — the whole inverse, one line

```js
const recovered = conjugate(fft(conjugate(spectrum, 1)), 1 / n);
```

Inside out: conjugate, transform, conjugate again and scale. The
`1` on the way in is not decoration — the same kernel has to take a scale
both times or gpu.js sees two different call shapes.

## Hint 3 — where the n goes

All of it, on the inverse. A forward transform followed by an unscaled inverse
gives you the signal multiplied by n — so if every recovered sample is 256 times too
big, the division is missing rather than misplaced.

## Same idea elsewhere

The conjugation trick is standard practice, not a curiosity: it is why cuFFT,
rocFFT and FFTW all describe their inverse as "unnormalized" and leave the 1/n to you —
the same kernels run both directions, and a library that scaled automatically would make
the common case (transform, filter, transform back, and the scales cancel) pay for
something nobody asked for. Where the 1/n lives, or whether it is split as 1/√n between the
two directions, is a convention you have to read off each library's documentation rather
than assume.

## Starter code

```js
// The forward transform, run backwards, using nothing new.
const gpu = new GPU({ mode });
const n = 256;

// ---- the forward transform, complete — now taking a COMPLEX input
const scramble = gpu.createKernel(function (spectrum) {
  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);
  }
  return spectrum[this.thread.y][reversed];
}, { 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] });

function fft(planes) {
  let buffer = scramble(planes);
  for (let half = 1; half < n; half *= 2) buffer = butterfly(buffer, half);
  return buffer;
}

const conjugate = gpu.createKernel(function (spectrum, scale) {
  // TODO: negate the IMAGINARY plane, leave the real plane alone, and
  // multiply whichever plane this thread owns by `scale`.
  return spectrum[this.thread.y][this.thread.x];
}, { output: [n, 2] });

// A real signal becomes two planes: the samples, and an empty imaginary plane.
const planes = [Float32Array.from(signal), new Float32Array(n)];
const spectrum = fft(planes);
console.log('bin 24 magnitude:', Math.hypot(spectrum[0][24], spectrum[1][24]));

// TODO: conjugate, transform, conjugate and scale by 1 / n.
const recovered = spectrum;

let worst = 0;
let leftover = 0;
for (let i = 0; i < n; i++) {
  worst = Math.max(worst, Math.abs(recovered[0][i] - signal[i]));
  leftover = Math.max(leftover, Math.abs(recovered[1][i]));
}

console.log('worst round-trip error:', worst);
console.log('largest imaginary leftover:', leftover);
console.log('round trip clean:', worst < 5e-3 && leftover < 5e-3);
```

---

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

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