# One Spectrum, No Clock

*Task 1 of 5 · [Spectrograms](https://gpu.rocks/learn/spectrograms-9ecd2295.md) · GPU.js Learn*

The discrete Fourier transform asks one question per **bin**: how much
of this signal looks like a wave that fits exactly *k* whole cycles into the buffer?
Answering it is a sum over every sample, and every bin's sum is independent of every other
one — so it is one thread per bin, each pulling the whole signal. The answer is a
*complex* number: how much, and at what phase.

gpu.js has no complex type, so this track carries complex data as **two planes of
floats**. `output: [n, 2]` is read `result[p][i]` — plane
`p = 0` is the real part, plane 1 the imaginary part, `i` the bin. (A
2D output `[w, h]` is indexed `[y][x]`, so `[n, 2]` gives
exactly `[plane][bin]`.) What you usually plot is the **magnitude**,
`√(re² + im²)`: how much of that frequency is present, phase discarded.

Two signals here. `orderAB` plays a 256 Hz tone and then a quieter 640 Hz
one. `orderBA` plays the same two tones the other way round — it *is*
`orderAB` read backwards. Transform both. The two spectra will not merely look
alike; they agree to the last bit, and that is a theorem rather than a coincidence:
reversing a signal conjugates its spectrum, and conjugating does not change a magnitude.
A spectrum knows what is in a signal. It has no idea when.

## Figures

- **two signals, one spectrum — the transform never asks what happened first**

## Goal

**Goal:** fill in both planes of the spectrum — plane 0 the real part,
plane 1 the imaginary part, each divided by `this.constants.n`.

## Requirements

- Keep `output: [256, 2]` — 256 bins across, two planes; the result is read `spectrum[plane][bin]`
- Sum over all `this.constants.n` samples with `angle = -2 * Math.PI * k * i / this.constants.n`
- Accumulate `re += signal[i] * Math.cos(angle)` and `im += signal[i] * Math.sin(angle)`
- Divide both sums by `this.constants.n`, and return `re` on plane 0, `im` on plane 1

## Hint 1 — which cell is mine?

`this.thread.x` is the bin (0…255) and `this.thread.y` is
the plane (0 or 1). Both threads of a bin do the *same* sum and each keeps half
of it — wasteful, and at 512 samples not worth caring about. An FFT is the version that
stops paying for it.

## Hint 2 — the loop

```js
for (let i = 0; i < this.constants.n; i++) {
  const angle = (-2 * Math.PI * k * i) / this.constants.n;
  re += signal[i] * Math.cos(angle);
  im += signal[i] * Math.sin(angle);
}
re = re / this.constants.n;
im = im / this.constants.n;
```

## Hint 3 — the sign

The forward transform winds *clockwise*: the angle is negative. Drop the
minus and every bin comes back conjugated — the imaginary plane flips sign while the
magnitudes stay exactly right, which is what makes this one so good at hiding.

## Same idea elsewhere

Split-complex — one array of real parts, one of imaginary — is how cuFFT, rocFFT,
Apple's vDSP and NumPy's `.real`/`.imag` views all lay complex data
out, and it is what you just wrote. Nobody ships a naive DFT, though: it is O(n²), and the
FFT rebuilds it as a log₂ n ladder of butterflies — the same halving-ladder shape the
Reductions module climbs, driven by a JS loop over a stride-taking kernel. At n = 512 the
naive version is 262,144 multiply-adds, which a GPU eats without noticing.

## Starter code

```js
// One thread per (bin, plane). 512 samples in, 256 bins out — and each
// bin's answer is a complex number, carried as two planes of floats.
const gpu = new GPU({ mode });

const spectrum = gpu.createKernel(function (signal) {
  const k = this.thread.x;
  let re = 0;
  let im = 0;

  // TODO: sum over all this.constants.n samples.
  //   angle = -2 * Math.PI * k * i / this.constants.n
  //   re += signal[i] * Math.cos(angle)
  //   im += signal[i] * Math.sin(angle)
  // Then divide BOTH by this.constants.n.

  if (this.thread.y === 0) {
    return re;
  }
  return im;
}, {
  output: [256, 2],
  constants: { n: 512 },
});

// Magnitude is the length of the complex number.
function magnitudes(spec) {
  const mag = [];
  for (let k = 0; k < 256; k++) {
    mag.push(Math.sqrt(spec[0][k] * spec[0][k] + spec[1][k] * spec[1][k]));
  }
  return mag;
}

function peakBin(mag) {
  let best = 0;
  for (let k = 1; k < mag.length; k++) if (mag[k] > mag[best]) best = k;
  return best;
}

const magAB = magnitudes(spectrum(orderAB));
const magBA = magnitudes(spectrum(orderBA));

let worst = 0;
for (let k = 0; k < 256; k++) worst = Math.max(worst, Math.abs(magAB[k] - magBA[k]));

console.log('A-then-B peaks at bin', peakBin(magAB));
console.log('B-then-A peaks at bin', peakBin(magBA));
console.log('largest disagreement between the two spectra:', worst);
```

---

Interactive version: https://gpu.rocks/learn/spectrograms-9ecd2295/1

[Next task](https://gpu.rocks/learn/spectrograms-9ecd2295/2.md)