# There and Back Again

*Task 5 of 5 · [The DFT, Honestly](https://gpu.rocks/learn/the-dft-7b1e3f9b.md) · GPU.js Learn*

A transform earns the name by being reversible. The inverse DFT is the forward one
with two edits: the exponent's sign flips to `+`, and the whole thing is divided
by `n`. Both edits are load-bearing, and both are where people go wrong —
forget the `1/n` and your signal comes back 256 times too loud; leave the sign
negative and it comes back *time-reversed*, which is a spectacular way to fail a
test that only checks sample 0.

Summing complex terms means real arithmetic on pairs. With `c = cos(angle)`
and `s = sin(angle)`, one term of `(re + i·im) · (c + i·s)` is:

```js
real      += re * c - im * s;
imaginary += re * s + im * c;
```

The shapes line up for free. `output: [n, 2]` hands back exactly the
`[2][n]` nested array a kernel wants as input — `spectrum[0][k]` real,
`spectrum[1][k]` imaginary — so the forward transform's result drops into the
inverse with nothing in between. The original signal is real, so plane 1 of the round trip
should come back as float noise: that residue is a free correctness check.

## Goal

**Goal:** write the inverse transform — `output: [256, 2]`,
taking the `[2][256]` spectrum — and confirm that transforming
`signal` and transforming it back recovers all 256 samples.

## Requirements

- Loop over **bins** `k`, and use `this.thread.x` as the SAMPLE index
- The exponent turns positive: `real += re * c - im * s`, `imaginary += re * s + im * c`
- Divide the finished sum by `this.constants.n` — once, at the end
- Log how many of the 256 samples come back within `1e-3` — all of them should

## Hint 1 — the loop runs the other way round

The forward kernel's thread owned a bin and looped over samples. Here the
thread owns a *sample* and loops over bins, so `this.thread.x` is
`i` and the loop variable is `k`:

```js
const angle = 2 * Math.PI * k * this.thread.x / this.constants.n;
```

## Hint 2 — the two planes of the answer

Same branch as the forward transform, over the complex product:

```js
const c = Math.cos(angle);
const s = Math.sin(angle);
if (this.thread.y === 0) acc += spectrum[0][k] * c - spectrum[1][k] * s;
else acc += spectrum[0][k] * s + spectrum[1][k] * c;
```

## Hint 3 — the scaling

`return acc / this.constants.n;` — once, on the finished sum, not
inside the loop. Forward does not scale, inverse divides by n; put the 1/n on the wrong
side and the round trip is off by a factor of 65,536.

## Same idea elsewhere

The 1/n is a convention, not a law, and libraries disagree loudly about it: FFTW
computes an unnormalised inverse and leaves the scaling to you, numpy puts 1/n on
`ifft`, and cuFFT documents its own choice per plan — which is why "my round
trip is n times too big" is one of the most-asked FFT questions on every platform. The
sign of the exponent is equally conventional; what is not optional is that the forward and
inverse pair disagree about it.

## Starter code

```js
// Forward, then back again. The spectrum's [2][256] shape is exactly what
// an output: [256, 2] kernel hands you — no reshaping in between.
const gpu = new GPU({ mode });

// The forward transform, unchanged from the last task.
const dft = gpu.createKernel(function (signal) {
  let acc = 0;
  for (let i = 0; i < this.constants.n; i++) {
    const angle = 2 * Math.PI * this.thread.x * i / this.constants.n;
    if (this.thread.y === 0) acc += signal[i] * Math.cos(angle);
    else acc -= signal[i] * Math.sin(angle);
  }
  return acc;
}, {
  output: [256, 2],
  constants: { n: 256 },
});

const idft = gpu.createKernel(function (spectrum) {
  // TODO: loop over the 256 BINS k, with this.thread.x as the sample index.
  // The exponent turns positive here:
  //   plane 0 accumulates spectrum[0][k] * c - spectrum[1][k] * s
  //   plane 1 accumulates spectrum[0][k] * s + spectrum[1][k] * c
  // and the finished sum is divided by n.
  return spectrum[this.thread.y][this.thread.x];
}, {
  output: [256, 2],
  constants: { n: 256 },
});

const spectrum = dft(signal);
const back = idft(spectrum);

let worst = 0;
let matched = 0;
for (let i = 0; i < 256; i++) {
  worst = Math.max(worst, Math.abs(back[0][i] - signal[i]), Math.abs(back[1][i]));
  if (Math.abs(back[0][i] - signal[i]) < 1e-3 && Math.abs(back[1][i]) < 1e-3) matched++;
}
console.log('largest round-trip error:', worst.toExponential(2));
console.log('samples recovered within 1e-3:', matched);
```

---

Interactive version: https://gpu.rocks/learn/the-dft-7b1e3f9b/5

[Previous task](https://gpu.rocks/learn/the-dft-7b1e3f9b/4.md)