Task 3 of 5

Every Bin, One Thread Each

Nothing about bin 8 was special, and nothing about it depended on bin 9. Every bin is its own dot product over the same samples, and no bin reads another bin's answer — which makes the whole transform 512 threads that never speak to each other. Change output: [1, 2] to output: [256, 2], take the bin from this.thread.x instead of a constant, and you are done.

Be honest about the cost: every one of the 256 bins sums over all 256 samples, so this is O(n²) — 65,536 multiply-adds where the FFT needs about 2,000. The GPU does not care. Perfectly independent quadratic work is the shape hardware likes best, and this is the baseline any clever algorithm has to actually beat, not merely out-argue.

The signal is three cosines buried in one buffer. Bin k covers k × sampleRate / n hertz — with a sample rate of 8,192 Hz and 256 samples, each bin is 32 Hz wide. Scan the first half of the spectrum only; task 4 explains why the second half has nothing new to say.

Goal: transform the whole signal with one kernel — output: [256, 2], one thread per (bin, plane) — then find every bin in 1…128 whose magnitude clears 20 and log its frequency in hertz.

Requirements

output: [256, 2]: this.thread.x is the bin, this.thread.y the plane
Plane 0 adds signal[i] * Math.cos(angle), plane 1 subtracts signal[i] * Math.sin(angle)
In JavaScript, scan bins 1…128 and keep those with Math.sqrt(re * re + im * im) > 20
Log each survivor in hertz: k * sampleRate / 256 — expect 320, 800 and 1280

Hint 1 — the only two changes

The kernel body from the last task already works. Swap the constant bin for the thread's own:

const angle = 2 * Math.PI * this.thread.x * i / this.constants.n;

and widen the output to [256, 2]. That is the whole diff.

Hint 2 — reading the spectrum back

output: [256, 2] comes back as two rows of 256:

const spectrum = dft(signal);
const re = spectrum[0][k];
const im = spectrum[1][k];

Hint 3 — bins are not hertz

A bin index is a count of whole cycles across the buffer. To turn it into a frequency you need to know how long the buffer is, and that is what the sample rate tells you — n alone cannot:

const hz = k * sampleRate / 256;

Same idea elsewhere

This kernel is a matrix–vector product in disguise: the DFT matrix times the signal, which is exactly how cuBLAS-style GEMV would express it and why a naive DFT is embarrassingly parallel on every platform. It is also the honest control in any FFT benchmark — cuFFT, VkFFT and FFTW all publish against it, and Measuring Speed Honestly has the methodology for running that comparison yourself.

All tasks in The DFT, Honestly

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.