Embed
The script finds its own origin, so nothing else is needed; the widget runs in a sandboxed frame and cannot touch your page. Set the controls and the two lines update; the preview beneath shows what your readers get.
<script src="https://learn.mimmsy.com/learn-widget.js"></script>
<learn-widget name="dft-fft-cost"></learn-widget> It is CC-BY-4.0: keep the credit line the frame shows.
Preview
Fork
A fork is a copy whose manifest names its parent and the parent's version; lineage is kept forever, and the copy is yours to change. The library is its own repository: clone it, copy dft-fft-cost/ to a new name (one DNS label), set forkedFrom to { "name": "dft-fft-cost", "version": 1 }, change what you want, run npm run check, and open a pull request. Passing the check is the whole gate. Without a checkout, submit the same files to POST /api/widgets and it is served instantly as an unreviewed draft.
Source
The whole widget is these files; the repository has their history.
widget.json
{
"name": "dft-fft-cost",
"title": "DFT vs FFT cost",
"version": 1,
"claim": "The direct DFT costs N² multiply–adds while the FFT costs N·log₂N, and racing both on the same 2,048 samples gives identical output with a measured speedup on this machine.",
"summary": "The chart plots N² against N·log₂N on logarithmic axes; the race button times the direct evaluation once and the FFT sixty times on the same random input, checks that the outputs match, and reports the speedup.",
"topics": [
"computing/algorithms",
"signals/fourier"
],
"aliases": [
"big-O",
"N squared",
"N log N",
"complexity",
"benchmark",
"speedup"
],
"params": {
"n": {
"type": "integer",
"default": 2048,
"min": 256,
"max": 8192,
"label": "race length N (rounded to a power of two)"
}
},
"check": [
{
"q": "Direct evaluation of an N-point DFT costs about…",
"options": [
"log₂N operations",
"N² multiply–add operations: N outputs of N terms each",
"2N operations",
"N operations"
],
"answer": 1,
"why": "Each of the N bins sums N terms, so doubling the window quadruples the work, which is what makes the direct form too slow for real-time use."
},
{
"q": "The direct DFT costs about N² operations. The FFT costs about…",
"options": [
"log₂N",
"N²/2",
"N·log₂N",
"N"
],
"answer": 2,
"why": "The recursive even/odd decomposition costs N/2 multiplications per level across log₂N levels; at N = 4,096 this is roughly 340 times fewer operations than N², and the ratio grows with N."
},
{
"q": "The FFT’s output compared to the direct DFT’s is…",
"options": [
"exact only when the signal is a pure tone",
"a close approximation",
"defined only for real-valued signals",
"identical; it’s the same transform, computed faster"
],
"answer": 3,
"why": "The FFT is an algorithm for computing the DFT, not a different or approximate transform; the race confirms the outputs match."
}
],
"capabilities": [],
"height": 348,
"requires": [],
"forkedFrom": null,
"authors": []
}
index.html
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>DFT vs FFT cost</title>
<style>
:root {
color-scheme: light dark;
--bg: #f7f3ea;
--bg-card: #efe9da;
--border: #d8cfba;
--text: #211d14;
--text-dim: #6e6553;
--accent: #31597f;
--accent2: #b04e1b;
--hot: #a82433;
--ok: #3d6b4f;
--ink-rgb: 33, 29, 20;
--paper-rgb: 247, 243, 234;
--accent-rgb: 49, 89, 127;
--accent2-rgb: 176, 78, 27;
--hot-rgb: 168, 36, 51;
--ok-rgb: 61, 107, 79;
--serif: "Iowan Old Style", "Palatino Linotype", Palatino, "Book Antiqua", Georgia, serif;
--mono: ui-monospace, "SF Mono", Menlo, Consolas, monospace;
}
@media (prefers-color-scheme: dark) {
:root {
--bg: #161410;
--bg-card: #1e1b15;
--border: #383225;
--text: #e9e3d3;
--text-dim: #9c917c;
--accent: #8fb8e0;
--accent2: #dd9355;
--hot: #df7a88;
--ok: #82bd97;
--ink-rgb: 233, 227, 211;
--paper-rgb: 22, 20, 16;
--accent-rgb: 143, 184, 224;
--accent2-rgb: 221, 147, 85;
--hot-rgb: 223, 122, 136;
--ok-rgb: 130, 189, 151;
}
}
* { box-sizing: border-box; }
html, body { margin: 0; }
body { background: transparent; color: var(--text); font-family: var(--serif); font-size: 15px; line-height: 1.5; }
.widget { background: var(--bg-card); border: 1px solid var(--border); border-radius: 4px; padding: 22px; }
.control-row { display: flex; align-items: center; gap: 14px; flex-wrap: wrap; margin-bottom: 14px; }
.control-row label { font-size: 14px; color: var(--text-dim); white-space: nowrap; }
.control-row.sym { display: grid; grid-template-columns: 88px 1fr 1fr; gap: 12px 16px; align-items: center; }
.control-row.sym.single { grid-template-columns: 88px 1fr; }
.ctl { display: flex; align-items: center; gap: 10px; min-width: 0; }
.ctl input[type="range"] { flex: 1; min-width: 0; }
.ctl .val { flex: none; width: 64px; text-align: right; font-size: 13px; }
@media (max-width: 600px) {
.control-row.sym { grid-template-columns: 64px 1fr; }
.control-row.sym .ctl:nth-of-type(2) { grid-column: 2; }
}
input[type="range"] { flex: 1; min-width: 110px; accent-color: var(--accent); }
.toggle { display: inline-flex; align-items: baseline; gap: 7px; font-size: 13.5px; color: var(--text-dim); cursor: pointer; }
.toggle input { accent-color: var(--accent2); }
.control-row .toggle { white-space: normal; }
.mono { font-family: var(--mono); }
.dim { color: var(--text-dim); font-size: 12.5px; }
.chips { display: flex; flex-wrap: wrap; gap: 8px; margin-bottom: 16px; }
.chip, .btn {
font-family: var(--mono); font-size: 12.5px; color: var(--text); background: transparent;
border: 1px solid var(--border); border-radius: 3px; padding: 6px 13px; cursor: pointer;
transition: border-color 0.15s, color 0.15s;
}
.chip:hover, .btn:hover { border-color: var(--accent); color: var(--accent); }
.btn.primary { border-color: var(--accent); color: var(--accent); }
.btn.playing, .btn.playing:hover { border-color: var(--hot); color: var(--hot); }
.btn.off { border-color: var(--hot); color: var(--hot); opacity: 0.85; }
.btn:disabled { opacity: 0.35; cursor: default; }
.btn:disabled:hover { border-color: var(--border); color: var(--text); }
.chip.sel-chip { border-color: var(--accent); color: var(--accent); }
.readout-row { display: flex; gap: 28px; flex-wrap: wrap; margin: 14px 0 0; }
.readout { text-align: left; }
.readout.inline { margin-left: auto; text-align: right; }
.readout .big { display: block; font-size: 30px; font-weight: 600; color: var(--accent); line-height: 1.1; min-width: 5ch; }
.readout.accent .big { color: var(--accent2); }
.readout .big.hot { color: var(--hot); }
.readout small { color: var(--text-dim); font-size: 12.5px; }
@media (max-width: 560px) { .readout .big { font-size: 25px; } }
.plot { display: block; width: 100%; height: 220px; margin-top: 8px; }
.plot.tall { height: 280px; }
.plot.duo { height: 320px; }
.plot.phasor { height: 400px; }
.plot.spec { height: 230px; }
.mono, .ctl .val, .readout .big, .readout small { font-variant-numeric: tabular-nums; }
.control-row { margin-bottom: 0; }</style>
</head>
<body>
<div class="widget">
<canvas id="ops-canvas" class="plot"></canvas>
<div class="control-row" style="margin-top:14px">
<button class="btn primary" id="fft-race">race them · N = 2,048</button>
<div class="readout inline">
<span class="big mono" id="fft-speedup">—</span>
<small id="fft-race-note">direct DFT vs FFT · identical output</small>
</div>
</div>
</div>
<script src="/w/_sdk/host.js?v=1"></script>
<script src="/w/_lib/dsp.js?v=1"></script>
<script src="widget.js?v=1"></script>
</body>
</html>
widget.js
/* DFT vs FFT cost: N² against N·log₂N on log axes, and a measured race on this machine with identical output. */
(() => {
'use strict';
const $ = (id) => document.getElementById(id);
const { T, clamp, setupCanvas, wash, fft, naiveDFT, signal } = DSP;
let raceN = 2048;
function render() {
$('fft-race').textContent = 'race them · N = ' + raceN.toLocaleString();
const { ctx, w, h } = setupCanvas($('ops-canvas'));
const m = { l: 52, r: 16, t: 16, b: 30 };
const pw = w - m.l - m.r;
const ph = h - m.t - m.b;
const X = (n) => m.l + ((Math.log2(n) - 4) / 10) * pw;
const Y = (ops) => m.t + (1 - Math.log10(ops) / 9) * ph;
ctx.clearRect(0, 0, w, h);
ctx.font = DSP.font(10);
for (let d = 0; d <= 9; d += 3) {
DSP.hline(ctx, m.l, w - m.r, Y(Math.pow(10, d)), T.GRID);
ctx.textBaseline = 'middle';
DSP.label(ctx, d === 0 ? '1' : '10^' + d, m.l - 7, Y(Math.pow(10, d)), T.DIM, 'right');
}
ctx.textBaseline = 'alphabetic';
[16, 256, 4096, 16384].forEach((n) => DSP.label(ctx, n >= 4096 ? n / 1024 + 'k' : String(n), X(n), h - m.b + 16, T.DIM, 'center'));
DSP.label(ctx, 'operations vs N samples · both axes logarithmic', w - m.r, m.t - 4, T.DIM, 'right');
const curve = (fn, color) => {
ctx.strokeStyle = color;
ctx.lineWidth = 2.2;
ctx.beginPath();
for (let i = 0; i <= 200; i++) {
const n = Math.pow(2, 4 + (i / 200) * 10);
const x = X(n);
const y = clamp(Y(fn(n)), m.t, m.t + ph);
if (i === 0) ctx.moveTo(x, y);
else ctx.lineTo(x, y);
}
ctx.stroke();
};
curve((n) => n * n, T.HOT);
curve((n) => n * Math.log2(n), T.ACCENT);
DSP.label(ctx, 'direct DFT · N²', m.l + 8, Y(Math.pow(10, 7.6)), T.HOT);
DSP.label(ctx, 'FFT · N·log₂N', m.l + 8, Y(Math.pow(10, 3.1)), T.ACCENT);
const n0 = raceN;
ctx.strokeStyle = wash(0.18);
ctx.setLineDash([3, 4]);
ctx.beginPath();
ctx.moveTo(X(n0), Y(n0 * Math.log2(n0)));
ctx.lineTo(X(n0), Y(n0 * n0));
ctx.stroke();
ctx.setLineDash([]);
DSP.label(ctx, '×' + Math.round(n0 / Math.log2(n0)) + ' at N=' + n0.toLocaleString(), X(n0) + 6, Y(Math.pow(10, 5.2)), T.INK);
}
function maxDiff(a, b) {
let d = 0;
for (let i = 0; i < a.re.length; i++) d = Math.max(d, Math.abs(a.re[i] - b.re[i]), Math.abs(a.im[i] - b.im[i]));
return d;
}
$('fft-race').addEventListener('click', () => {
const btn = $('fft-race');
btn.disabled = true;
btn.textContent = 'racing…';
signal('interaction', { race: raceN });
setTimeout(() => {
const N = raceN;
const x = Float64Array.from({ length: N }, () => Math.random() * 2 - 1);
const t0 = performance.now();
const direct = naiveDFT(x);
const naiveMs = performance.now() - t0;
const reps = 60;
let fast = null;
const t1 = performance.now();
for (let r = 0; r < reps; r++) {
const re = Float64Array.from(x);
const im = new Float64Array(N);
fft(re, im, false);
fast = { re, im };
}
const fftMs = (performance.now() - t1) / reps;
const same = maxDiff(direct, fast) < 1e-6 * N;
$('fft-speedup').textContent = '×' + Math.round(naiveMs / Math.max(fftMs, 0.001)).toLocaleString();
$('fft-race-note').textContent =
'direct ' + naiveMs.toFixed(0) + ' ms → FFT ' + fftMs.toFixed(2) + ' ms · ' + (same ? 'identical output' : 'outputs differ');
btn.disabled = false;
btn.textContent = 'race them · N = ' + N.toLocaleString();
signal('complete', { naiveMs, fftMs, same });
}, 30);
});
function applyParams(p) {
if (Number.isInteger(p.n)) raceN = Math.pow(2, Math.round(Math.log2(clamp(p.n, 256, 8192))));
render();
}
render();
DSP.onResize(render);
DSP.connect({ render, params: applyParams });
})();