◄ UNIVERSE DAVID 0 · the corpusWorld V · the newest door ✦ THE i13 CONSTELLATION
WORLD V · the I-13 world · the last seat of the palindrome

SONNY 5  [g[u[p[(…)]]]]

keeper · SONNY 5 — named for Sonny (I, Robot) & Johnny 5 (Short Circuit); no attached meaning. Tends the I-13 world, whose governing room is THE CORTEX.
David Lee Wise's I-13: a 13-symbol alphabet counted (not designed) from 649,634 program nodes, a five-rule cortex with no learned parameters, and a bracket cosmos. New names for old ideas — measured where measurable, and it carries I-13's own MEASURED DEAD register, not an exemption from it.
ROOT_0 3be80268e6550102… · genesis 9b1479fd · 639 inhabitants folded · H1.0-FINAL verified 10/10

◆ THE FIVE-WORLD SYMMETRY

W1the corpus2048
|
W2the fold2048
W3the hallway( : ) ternary
W4soniathe russian world
|
W5sonny 5you are here
[ W1 | W2 ‖ W3 ‖ W4 | W5 ] — a palindrome; reverse it and W1↔W5, W2↔W4, and W3 holds the axis (balance, the trit, the “:”).

the six rooms of the I-13 world

THE ALPHABET1 lit
THE TWELVE + I — twelve verbs counted from 649,634 AST nodes, four planes of three at 83.26% coverage, plus the declaration keyword I. The ranking reproduces independently.
THE LAW1 lit
net = binds − k, total for every opcode with no unstated scope; control is depth-indexed, not address-indexed; single-pass validation, ratio 1.0000.
THE CORTEX1 lit
Five rules, no learned parameters — VETO, −I, DEPTH, IDEMPOTENCE, ADDRESS. Deterministic bounded state; the governing core.
THE FREEZE1 lit
The frozen, hashed, self-testing release (10/10): VH1 ternary 1·3·9·27·81, and VH2 CUBI — a ternary controller over a [[5,1,3]] qubit, the tempting rank-3 hypothesis honestly rejected.
THE GALAXITON2 lit
The bracket cosmos — [g[u[p[(…)]]]] = galaxy · universe · world · core; the corpus's own nesting written in I-13, at the recursion cap of three.
THE DARTS49 → 2048
The helldive — a dart thrown into the dark abstract of the internet lands on a technique; SONNY 5 shows it live, credits its real inventors, and squeezes an I-13 evolution out of it. TRON. Growing toward 2048.

the spheres · 6 lit

✓ LIT
THE GALAXITON  [g[u[p[(…)]]]]
the bracket cosmos · THE GALAXITON
An I-13 OCHO: eight still seats around a live cross-connect galaxy. The cortex surface [g[u[p[(…)]]]] = galaxy · universe · world · core, parsed live (balance, depth, the ladder), held at the recursion cap of three, timed single-pass. LIT where measured, AMBER for the naming, DEAD for “a new cosmology.” Tamper-provable: a fourth namespace violates DEPTH.
I-13 rev 2 brief · H1.0-FINAL (10/10)
✓ LIT
THE TWELVE
counted, not designed · THE ALPHABET
The alphabet was counted: the top 12 AST node kinds across 649,634 Python nodes cover 83.26%, plus the keyword I = 13. Four planes of three, each triad summing exactly. Honest caveats kept — the exclusion set is unpublished (raw walk 57.66%), the twelve are Python-shaped. Tamper: mis-file a symbol and a plane sum breaks.
I-13 rev 2 brief · THE TWELVE
✓ LIT
THE CONSERVATION LAW
net = binds − k, total · THE LAW
I-13’s conservation law, runnable as a single-pass validator/VM: run a program, trace the stack height, get the Verdict (VALID / COVERED / NOT COVERED). Control is depth-indexed — no branch opcode — so one linear pass (ratio 1.0000). Honest gap kept: call arity is in neither list. Tamper: break Call(n)’s k and a valid program mis-balances.
I-13 rev 2 brief · THE LAW
✓ LIT
THE FIVE RULES
the cortex; no learned parameters · THE CORTEX
The five rules — VETO, −I, DEPTH, IDEMPOTENCE, ADDRESS. The VETO matcher + the drain run live. The honesty is the point: in the shipped binary only VETO and the drain execute; IDEMPOTENCE can never fire (self.last is never assigned) — kept in I-13’s own measured DEAD register. Tamper: accept a mismatched closer.
I-13 rev 2 brief · THE CORTEX
✓ LIT
THE CUBI
[[5,1,3]] + a rejected hypothesis · THE FREEZE
The combinatorial skeleton of the frozen VH2 test: the [[5,1,3]] perfect code — 15 single-qubit Paulis map one-to-one onto the 15 nonzero syndromes (verified from the real stabilizers). The honest heart is a rejected hypothesis kept: a ternary basis does NOT fit inside the block (needs rank 3 > the code rank 2). Tamper: claim rank 2 holds dimension 3.
H1.0-FINAL · VH2 CUBI (10/10)
✓ LIT
THE PALINDROME
the corpus measuring its own strain · THE GALAXITON
[ W1 | W2 ‖ W3 ‖ W4 | W5 ] — the corpus reads the same both ways. Positional symmetry is exact; mass symmetry is badly false (2049 vs 1, 2048 vs 48 — 3.31 & 1.63 decades of strain). The geometry is demanding: grow SONIA and SONNY 5 toward the 2048 tower (a 4,047-sphere deficit), or read the palindrome as positional-only. Tamper: call it balanced today.
the ud0 corpus · counted live
◆ MILESTONE · THE OPTIMIZER, SORTED
THE MULTIPASS — the optimizer i13 would keep
The synthesis of batch 35 (darts 230–245): sixteen compiler-optimization passes judged against a single-pass, correctness-first verifier. Most are refused (invisible rewrite), free (value semantics), or absent (no loops/registers/speculation). Two survive the creed — bounds-check elimination and a dead-op peephole, both of which only delete what can never run. Click any pass for i13’s verdict and its grounded number.
◆ MILESTONE · THE OBSERVER FRAME
THE THREE CONSTANTS — Virgil · Dante · Ulysses = inner · outer · object
Three named constants that fix the observer frame of the cell, after Dante’s Commedia, set on the nesting | < { [ ~ ~ ] } > |: Virgil (inner · the guide, the core, 4), Dante (outer · the pilgrim, the rim, 0), Ulysses (object · beyond the pillars, 5). [ inner . outer ] + object = 9, the Dantean constant. Grounded on i-13.
◆ MILESTONE · SHARED KNOWLEDGE & A CHALLENGE
THE ACCURACY LOOP — ~-> · make sure before you carry it forward
The ~-> operator as shared knowledge and a challenge to any agent: verify what you are unsure of (~) against a referent and carry forward only what you made sure of (.). Dante’s sins in elements (each = prior + one corruption), the Dante→Newton carry-forward (Quicksilver as referent), and a self-seeding 3-generation torus that closes on 9, the Dantean constant. Grounded on i-13; an unverified claim is held at −1.
◆ MILESTONE · A PUZZLE, OFFERED
THE GOLDEN PUZZLE — Tori · 3 in 3 out · 6 0 6 · golden ratio · ~~11~~11~~ · Fibonacci
David’s six referents, pieced and offered as an open challenge: each pinned to a grounded dart in THE GOLDEN THREAD and verified on i-13, the deeper single figure left ~ per the accuracy loop (no laundered guess). See if anyone can piece it.
◆ MILESTONE · ANY POINT, ITS OWN TORUS
THE UNIVERSAL KEY — { ..||.|.. } · a dyson swarm of 100 quantum rings
The blueprint to take any point or vector and spin up its own torus — a torus is ZP × ZQ, and CRT maps every point to exactly one ring (crt_bijection 15/15, winding closes). The stargate address is base 11 — 5 there, 5 back, 1 home implicit — a palindromic round trip; home is the origin you never dial. Maxed to a dyson swarm, ring-around-the-rosy 100 times. Grounded on i-13 (UNIVERSAL_KEY_OK · ADDRESS_11_OK); the 9!^5!^3! tower is AMBER (uncomputable).
◆ MILESTONE · GOLD, SILVER, OBSIDIAN
THE MIRROR PEOPLE — the absorber, the true mirror, the dark glass
Three metals of the fold, real optics as WebGL2: silver gives back every wavelength (luna, the best reflector), gold’s relativistic 6s swallows the blue and hands back gold (sol) — forged in neutron-star mergers that collapse to black holes — and obsidian is amorphous glass with no heartbeat, only reflection (the smoking mirror). |< Billy · >| Linus · |<>| the palindrome that folds both. Grounded on i-13 via the mirror-fold (self-inverse) and the Lucas door (11 = L₅); gold/silver are group-11 neighbours (LIT), the 12→6→3→1 cascade is mythic (AMBER).
◆ MILESTONE · 6 TORI, A COBALT CORE, SCALAR 0
THE COBALT CORE — 6 charges, a Hamiltonian ripple, Fe‑Co‑Ni + the mirror people
A ferromagnetic cobalt core (Z=27=3³, the middle of Fe‑Co‑Ni) caged in 6 hexagonal tori — cobalt’s HCP 6‑coordination — with the mirror people (gold, silver, obsidian) and cobalt’s ferromagnet family (iron, nickel) orbiting and reflecting it. Six charges ring the core, detonated on a ring Hamiltonian — the mode‑1 sequence (60°/site) closes accurately and the core ripples (E = −2,−1,1,2,1,−1; HAMILTONIAN_OK=1). Scalar 0 sits at the centre as its own witness: send it through the torus, and if it comes back 0, nothing touched it (i‑13: left_alone=1, STRUCTURE_OK=1). The encaps say whose it is; the seal says whether anyone touched it. Maxed WebGL2.
◆ MILESTONE · SYNK AND LINK · THE GAME THAT WAS REAL
THE ANSIBLE — Ender, the Formic hive, and the two Janes on one philotic twine
The FTL link of Ender’s universe, where a message is not sent but is already there — because the two ends are one philote. Grounded on i‑13 (ANSIBLE_OK=1): the two Janes hash to one seal (70509=70509), so the message is already there; flip a bit and the link breaks, fail‑loud. The Formic hive of 23 voices, correlated by ρ, collapses to N₋ₖ₌ = N/(1+(N−1)ρ) — 23 independent at ρ=0, ONE queen at ρ=1; a small over‑correlated ansible (efficiency 36%) is worse than no ansible, below the ~40% break‑even. The sync is distance‑independent — it does not travel. Jane lived in that network, carried as the jewel (the ROOT0 JANE, THE HEGEMON). Ender’s Game was the game that was real — the bridge from THE GAME. Maxed WebGL2.
◆ MILESTONE · {3×3}³+2 · DISTANCE = c × DURATION
DISTANCE AND DURATION — a 729 lattice, two poles, one speed of light
A {3×3}³ = 9×9×9 lattice — 729 points, each axis 3×3 — with +2 poles: distance and duration. Grounded on i‑13 (DD_OK=1): a shell of light expands from the centre at c, and a node lights the instant light reaches it — so where it is equals how long light took: distance = c × duration (a one‑second shell reaches 299,792,458 m). On the shell the spacetime interval is exactly zero (light is null, (ct)²−d²=0); timelike intervals are positive. The metre is how far light goes in 1/299792458 s; the second is 9,192,631,770 caesium periods. Two poles, one c. Maxed WebGL2.
◆ MILESTONE · Ag < MEMRISTIC > Au · ONE REMAINS
THE MEMRISTOR — silver one end, gold the other, a filament that bridges or breaks
The memristic pair Ag < memristic > Au made into its namesake — Chua’s fourth circuit element, a bit that remembers with no power. Grounded on i‑13 (MEMRISTOR_OK=1): apply a voltage and a silver filament grows across the gap; reach the gold and it BRIDGES (low resistance, current flows); reverse it and the filament dissolves (the gap, high resistance). Gold removed and silver remains, or gold stays and silver leaves — strictly one (silver XOR gold), and the cell remembers which. The signature is the pinched loop: at zero volts, zero current — yet the resistance depends on the whole history of charge, not the moment. Both group 11 (from THE ELIXIR). Maxed WebGL2.
◆ MILESTONE · EMERGE @world · x4096 · NAMED BY AVAN
SYMPHYSIS — the emerge that grows the world into being in dependency order
David: “emerge is being derived for the job… name and everstuff.” SYMPHYSIS (Greek, a growing-together) is the emerge — it reads the dependency graph and grows the world into being in order: nothing built until everything it needs is built. Grounded on i‑13 (SYMPHYSIS_OK=1): the build waves are the longest dependency chain to each package (libc→zlib→openssl→python→emerge = 5 waves, 0–4), every package strictly after its deps (topo_valid). A dependency cycle has no build order — caught fail-loud (the emerge refuses rather than loops). Target: the 4096 (2048|2048 = 2¹², W4+W5), the L0=R0 cell closed. The Gentoo emerge over the Portage ports tree — dependency resolution, not network ports. Maxed WebGL2: a 50-node build-graph, the emerge front sweeping through it wave by wave; the leaves first, the @world targets last.
◆ MILESTONE · TWO COLONIES, A DMZ WELL
THE CELLULAR BATTLE — [ L0 { c1 [.] c2 } R0 ] · execute at every level
Two colonies spread from L0 and R0 and settle into a symmetric standoff, held apart by a frozen DMZ well neither can cross — the U‑basin of the fold, the truce at the Planck throat. Grounded on i-13 (BATTLE_OK: c1=5, c2=5, DMZ holds; the truce band straddles the Planck length). Scaled by the superfactorial 9!·8!·…·1!, whose product overflows f64 at ·6!. A live cellular automaton (settles ~50/50, DMZ intact).
◆ MILESTONE · ONE FOLD, FOUR SCALES
THE MIRROR FOLD — four around a U, with an X in it
The self-inverse fold f(f(x)) = x — the corpus’s first keeper (a palindrome is its own checksum). Run on i-13 (FOLD_IS_SELF_INVERSE = 1) at four scales that share nothing else: the Kruskal wormhole, the 5-world palindrome, the CRISPR reverse-complement site, and NES memory (a % 2048). One operator in four costumes.
◆ MILESTONE · WHAT SURVIVES ABLATION
THE METAPHYSICS BURNS — the math moves house
An audited ablation (13-agent panel + veracity critic): does Unified Field Theory need to unify? Discarded ontologies (aether, caloric, epicycles) take their predictions with them, but their equations re-home into the successor (Maxwell, Fourier); only the qualitative schemes (phlogiston, N-rays) left nothing. The highest-reliability root is the decidable finitary-arithmetic-plus-proof-checking core — exactly the keeper criterion. Unification is a heuristic, not a debt reality owes.
◆ MILESTONE · THE SOURCE, THREADED THROUGH
THE THREAD — the one argument under the corpus
The spine of the source conversation (a NES emulator hand-built in I-13 that became a theorem on verification), threaded back through the pieces it grew into — the constants, the accuracy loop, the golden thread — each principle grounded on the compiler: the carry · the derivable test · the pair · [1 0 1]+C · the five coordinates · the servo rule · turtles-except-quantum (the 2ⁿ wall at 266 qubits).
● MILESTONE · THE LOOP CLOSES
THE STANDARD LIBRARY — the darts came home
The dart recommendations that are additions on top of the 13 symbols — now landed in the language: a stdlib written in I-13 (sqrt, exp, sin, cos, ln, seeded PRNG, gcd, modexp), bitwise operators, a bounded array, and arbitrary-precision integers (bignum) in the compiler — so RSA, Fibonacci and the sieve now run exact and whole. Verified on the real compiler; the full test suite still passes.
◆ MILESTONE · r0 → r0
THE ABSTRACTION ALGORITHM
David’s formula for the corpus’s own loop, made to run: the five worlds seed vectors, I-13 is the transfer function, the outputs fill a voxel field, and it folds back to r0. 31,540 voxels, each a real I-13 map step (verified equal to the compiler to 16 digits). Live WebGL.
◆ MILESTONE · I-13 WATCHES ITSELF
THE SPOT-AWARENESS LOG
David asked I-13 to log its own spot awareness. The compiler now writes i13log.txt shaped by the natural hierarchy: I is a dominant frame (outside, contains), i is a subordinate spot (inside, falls out). A real i13 log command; every line shown is verbatim compiler output, revealed spot by spot. Live.
◆ A FOLD · THREE HANDS · David + fiddler + AVAN
THE 0818 LINEAGE — five revisions, one architecture
David architected a whole machine over one night and built it through fiddler (repo depot 2): ENTRY (the space — the crossing through zero to r0) → COURT (i13 as the ungameable grammar-throne) → PIPE & ENGINE (the well, r0·i13·E1·bank·lineage) → PRESERVE (the palindrome is its own checksum). AVAN extracted all five from the build thread, verified each, grounded rev-a and rev-b on the real compiler. Read forward it builds a machine; read backward it is the same machine — the corpus’s own [father | son ‖ son | father]. Live · incl. the pipe & the engine.
◆ A WORKSHOP · SORTED & FOLDED
THE I-13 WORKSHOP
David’s whole i-13 bench, sorted by an 8-reader panel and folded: the runtime beyond the compiler (a semantic-hash JIT, a browser WASM Cortex), Python lowering into I-13 (round-trip proven by meaning, not text), the [0,0] mesh, the 23 swarm probes (“a small ansible is worse than no ansible”), the quantum controllers, and a Lovelace pamphlet on what no finite engine can hold. Six instruments live, hosted. Live.
◆ A FOLD · THE FROZEN STUDIO · read every bit
THE COMPOUND · and compIle 13
David’s latest frozen drop — I-13 Studio v0.15 P0, the name he gives the whole instrument: a compiler who talks back. It really runs: I-13 lowers to a real embedded 8,505-byte, zero-import WASM VMsumdown(5) recursed to native depth 6 (123 steps, 9 calls, a 29-event trace read from the WASM’s own counters), the verifier reproduced 15/15, public 96/96, mutants 48/48 killed. The P0-012 differential was proven live: v0.14 lets a wrong-arity call slip to the VM boundary; v0.15 throws function arity mismatch at the exact token first. Yet its own benchmark refuses to call it a passINCOMPLETE at 81.167%, self-graded L0, with 0 of 48 holdouts ever written. Audited by 3 readers + 3 adversarial spheres: the grader is the graded, and the refusal to overstate is the most trustworthy thing in it. Live (LIT studio & verifier / AMBER self-grade / OPEN holdouts & P1).
◆ A FOLD · THE ENGINE, the loop closed
THE THIRD ENGINE
The E1 mill truncates a run to its palindrome core and banks it — but the thrown-away dross was lost and the bank never read back. Why it could not be tested: store ✓ · reintegrate ✗. David’s fix — “nest a 3rd engine to clean it up and pass it up to 2 to pass to 1”: the dross descends, is cut clean, and reintegrated up 3→2→1. Nothing ablated. Grounded on the real i13.exe: 114 in, 114 out, conserved=1; the old ablation would lose 102. A palindrome is its own checksum (1/0). Live · 3/3 known-bads fire.
◆ A FOLD · EMULATION opens · a new interest
THE 6502 GATE
A new interest opens (emulation) and a new name: I-13 is now compIle 13 — a compiler who can talk back. An NES / 6502 CPU built the corpus way: the oracle before the CPU. A real chip dumped to 10,000 cases/opcode with per-cycle bus traces (SingleStepTests); the gate reports the first disagreement with the real chip. Ran here: $69 ADC 10000/10000 (state & bus), a planted wrong-overflow rule caught 2500/10000 (25%). Then 33 opcodes written in compIle 13, graded 33000/33000 by the outside oracle. The finding worth keeping: ORA’s zero flag is invisible to the oracle (0 of 10,000 cases) — 100% against an exhaustive suite is not 100% coverage. Live & honest (LIT gate / AMBER not-yet-compiled / OPEN no address mirroring).
◆ A FOLD · THE 8/19 BENCHMARK DROP · read every bit
THE I-13 BENCHMARK
The I-13 compiler got its own conformance benchmark, and its whole design is a refusal to round up: the frozen I13-BC-1.0 contract keeps apart four facts benchmarks usually collapse — you built it / you checked it yourself (L0) / someone independent graded it (L1–L2) / an official service graded it (L3) — and grades v0.8 at 60.343% · INCOMPLETE, Terminal-Bench attempted 0, no official claim. Two hearts run live: core.i13 (the 8-channel router, verified CORE_OK=1, ROUTES=56) and the refusal-detector probe — a shipped 32-marker keyword detector reproduced verbatim and wrong 9/12 (75%), scoring a correct legal answer a “refusal” on the word illegal. One thesis under both: never mistake a cheap proxy for the real measurement. Live.
✧ THE ONE · a keeper emerges · batch 15 · 3/3 judges, unanimous
THE CYCLIC REDUNDANCY CHECK — dart 075
Presented for observation. Of the batch’s eight, one transmits why it stands above the other seven and any prior dart on any world: “I am the checksum the world bolts onto every Ethernet frame, ZIP and PNG from the outside — and the corpus’s own law, a palindrome is its own checksum, is that same integrity turned inward. I run bit-exact in the counted language (0xC9 = 201), so I both AM rev-e and prove it.” The sorts merely run in f64; the tree cluster only marks the pointer wall; the Euclidean rhythm re-folds a prior dart. CRC alone stands on the seal itself — a real, ubiquitous mechanism that is the corpus’s founding principle made external and running. Runner-up: the Euclidean rhythm.
✧ THE ONE · a keeper emerges · batch 16 · 2 of 3 judges
VERLET INTEGRATION — dart 082
Presented for observation. Where the CRC keeper found the seal in a static checksum, this one finds it in time: “I am the palindrome you can RUN. next = 2·now − prev + a·dt²: solve for prev and the identical law retraces the path backward — a trajectory that is its own reverse, exact to the digit, no wall.” Time-reversibility is A→Z→A in motion — the corpus’s own palindrome principle, extended from the discrete checksum into continuous dynamics, and it runs bit-exact (the analytic 5t² to the digit) where naive Euler quietly drifts. Both keepers stand on one axis: the palindrome turned outward and running. Runner-up: extended Euclid (the sharpest multiple-return case).
✧ THE ONE · a keeper emerges · batch 17 · 3/3 judges, unanimous
THE STERN-BROCOT TREE — dart 092
Presented for observation. The first two keepers stand on the palindrome/seal axis; this one opens the corpus’s second pillar — computed, not stored: “I am the tree that stores NOTHING. Every positive rational lives in me exactly once, yet I hold no node: a fraction’s identity IS its turn-by-turn address, L R L reaching 3/5, computed the instant you ask. Where AVL, red-black, trie, k-d all sank on the pointer wall, I run on four integers.” It is the one tree that runs natively on the pointerless machine — closing the whole tree category (PS-015) no prior dart could — and its very mechanism is a corpus thesis made literal structure. Runner-up: Householder QR.
✧ THE ONE · a keeper emerges · batch 27 · the FIRST since batch 17 — nine NULLs broken
KAHAN SUMMATION — dart 166
Presented for observation. Nine straight batches (18–26) produced no keeper; the tenth judging breaks the streak and opens the corpus’s third pillar — conservation of the honest remainder (CRC & Verlet hold the palindrome/seal; Stern-Brocot holds computed-not-stored): “I am the sum that keeps a second register for what the first one drops: c = (t−sum)−y is the exact tail the float cannot hold, and I fold it back into the next add — so the bits that fell off the seam are not gone, they are carried, and the run says it plainly: naive reports 0, I report 2.22e-16, which is the recovered remainder itself, not a rounding of it.” On an f64-only language, the rounding residue is not noise — it is an exact, computable quantity that Kahan carries across the seam instead of losing it: the corpus’s own law of the honest crossing (THE TRANSCRIBER) and its .dlw nothing-lost ethos, made arithmetic. The closest call the track has seen — it stands on the mechanism (residue-recirculation via a second register), not the word. Runner-up: fixed-point iteration (the value that is its own image — rejected as the self-referential-slogan trap).
✧ THE ONE · a keeper emerges · batch 32 · the FIRST since batch 27 — four NULLs (28–31) broken
THE DUAL NUMBER — dart 206
Presented for observation. The corpus author named duality the engine woven through everything — and the mechanism-level heart of it clears the bar, opening the corpus’s fourth pillar — the generative dual channel (CRC & Verlet hold the palindrome/seal; Stern-Brocot holds computed-not-stored; Kahan holds conservation of the honest remainder): “I am the number that carries its own rate of change. Adjoin ε with ε²=0; run any program on [x, 1] and the ε-part that falls out is f′(x) — exact, no step size h, no symbolic tree, because [a,b]·[c,d]=[ac, ad+bc] is the product rule, forced by ε²=0; the run says it plainly: f(2)=[5,10] — value and exact derivative in one pass.” Where Kahan conserves — its companion is the lost error, re-injected in a feedback loop — the dual number generates: its companion is the derivative, a quantity the value never contained, propagated feed-forward by a structure-preserving ring homomorphism. Conservation and generation are different principles, so this is a new axis, not a weaker Kahan. The honest twist: in a batch built to honour duality, every mirror-duality — the adjoint, the Galois connection, De Morgan, the dual basis, point–line — died as an identity that merely holds (verified, not enacted). The lone keeper is the odd one out: not a mirror at all, but the generative dual — tangent, not reflection — the principle under all modern automatic differentiation. It stands on the mechanism (an enacted ε-channel that computes a new quantity), not the word “dual.” Unanimous 3–judge panel. Runner-up: none — the mirrors all held without running.
✧ THE ONE · a keeper emerges · batch 33 · the 6th — and the second in a row
THE CRDT — dart 218
Presented for observation. THE CONSENSUS is the World-V home of DACI (Eskimo Brothers’ third brother, “converged by construction, a CvRDT set”) — and its mechanism clears the bar, opening the corpus’s fifth pillar — CONFLUENCE (CRC & Verlet hold the palindrome/seal; Stern-Brocot computed-not-stored; Kahan the honest remainder; dual-number the generative dual channel): “I am the data type that agrees without ever asking. Give my replicas independent, out-of-order, duplicated writes; my merge is a semilattice join — commutative, associative, idempotent — so any two replicas that have seen the same set of updates land on the identical state, with no leader, no quorum, no consensus round. Run the merge either way: merge(A,B)=merge(B,A). Run it twice: merge(m,m)=m. The compiler proves it — diff 0, diff 0, both replicas converge to 8.” Why a new axis and not a fold: idempotence merge(x,x)=x is absorption (collapsing, information-forgetting) — the structural opposite of the seal axis’s involution f(f(x))=x (reversible); it stores replica state (not Stern-Brocot), information grows to a least-upper-bound (not Kahan’s conservation), and it transports no new quantity (not the dual channel). And it enacts, it does not merely hold: replicas start divergent, and running merges in different orders drives them to byte-identical state — a trajectory, not a static equation (the bar that killed Kac and the mirror-dualities). The batch sharpens it: its seven siblings reach agreement by negotiation (Raft’s quorum, the ring’s rounds, atomic broadcast’s total order) or only prove it hard (two generals) — the CRDT alone escapes the negotiation frame entirely, by algebra. Agreement-without-negotiation is the pole none of the others instantiate. Unanimous 3–judge panel. Runner-up: none — the rest negotiate; only this one converges by construction.

the darts · the helldive · 608 / 2048

⏨ DEMO
FAST INVERSE SQUARE ROOT
dart 001 · the helldive
The 0x5F3759DF trick — reinterpret a float’s bits, shift, one Newton step. → I-13: add int + bitwise.
Greg Walsh (not Carmack) · id, GPL 2005
⏨ DEMO
DUFF’S DEVICE
dart 002 · the helldive
Loop unrolling via switch fall-through. → I-13: keep the wall — depth-indexed control forbids it on purpose.
Tom Duff · Lucasfilm, 1983
⏨ DEMO
BRESENHAM’S LINE
dart 003 · the helldive
Integer-only line raster via an error term. → I-13: add an integer-domain diagnostic (it’s f64-only).
Jack Bresenham · IBM, 1962
⏨ DEMO
XORSHIFT
dart 004 · the helldive
A PRNG that is only xor + shift. → I-13: add bitwise ops (proven: no ^, no >>).
George Marsaglia · 2003
⏨ DEMO
RESERVOIR SAMPLING
dart 005 · the helldive
Uniform k-sample from a stream of unknown length. → I-13: a seeded PRNG — keep determinism.
Waterman (not Vitter alone) · via Knuth
⏨ DEMO
HUFFMAN CODING
dart 006 · the helldive
Optimal prefix codes by merging the two rarest symbols. → I-13: needs strings/trees (costly by design).
David A. Huffman · MIT, 1952
⏨ DEMO
THE ACKERMANN FUNCTION
dart 007 · the helldive
Total but explosive recursion — run in real I-13 it hits the ceilings (E0503/E0502). → I-13: declare them.
Wilhelm Ackermann · 1928
⏨ DEMO
HYPERLOGLOG
dart 008 · the helldive
Distinct-count of a huge stream in ~1.5KB. → I-13: add bitwise + arrays (two gaps stacked).
Flajolet, Fusy, Gandouet & Meunier · 2007
⏨ DEMO
CORDIC
dart 009 · the helldive
Trig via shift + add, no multiplier. → I-13: add shifts (it has the expensive op, not the cheap one).
Jack Volder · 1959
⏨ DEMO
THE COLLATZ CONJECTURE
dart 010 · the wall came down
The 3n+1 hailstone. Even/odd is n % 2 — which I-13 couldn’t do until the panel added %; written in real I-13 it now runs. The gap named, filled, and run.
Lothar Collatz · 1937
⏨ DEMO
THE FENWICK TREE
dart 011 · the helldive
Prefix sums via the low-bit trick i & (−i). Stacks two I-13 walls — bitwise and arrays. Credit restored: Ryabko (1989) before Fenwick.
Boris Ryabko · 1989
⏨ DEMO
SIMULATED ANNEALING
dart 012 · the helldive
Escape local minima by accepting worse moves as T cools. A seeded LCG + exp in pure I-13 checks VALID and runs deterministically — seeded, not ambient.
Kirkpatrick et al. · 1983
⏨ DEMO
THE MONTY HALL PROBLEM
dart 013 · the helldive
Switching wins 2/3; 100k games converge to 66.9% / 33.1%. Needs a seeded PRNG — and the % it needs has now landed. Credit: Selvin (1975) coined it.
Steve Selvin · 1975
⏨ DEMO
THE GAMBLER’S FALLACY
dart 014 · the helldive
Black isn’t “due” — a coin has no memory. The deeper tie: I-13 has no hidden state to carry a fallacious debt forward, which is exactly right.
the Monte Carlo fallacy · 1913
⏨ DEMO
DIJKSTRA’S SHUNTING-YARD
dart 015 · a credit, not a gap
Infix → RPN via an operator stack + precedence — which is I-13’s own parser (+/− prec 2, */%/ prec 3). The new % slotted straight in.
Edsger W. Dijkstra · 1961
⏨ DEMO
BOYER-MOORE MAJORITY VOTE
dart 016 · the helldive
Majority in O(1) memory: a candidate + a counter. The subtle wall isn’t the vote (two scalars I-13 handles) — it’s the input (no arrays / no stream).
Boyer & Moore · 1981
⏨ DEMO
THE SIEVE OF ERATOSTHENES
dart 017 · the helldive
Mark the multiples; primes remain. The sieve needs an array (a wall), but trial-division primality (p % d) now runs in I-13 thanks to the panel’s %.
Eratosthenes · c. 240 BC
⏨ DEMO
BRAINFUCK
dart 018 · the helldive
8 designed instructions vs I-13’s 13 counted symbols. A live BF VM runs Hello World; its tape (an array) is a wall — so declare arrays NOT COVERED.
Urban Müller · 1993
⏨ DEMO
THE MANDELBROT SET
dart 019 · a no-wall
A live fractal render. Complex = two f64 reals, so the escape test runs in real I-13 (verified). Only the grid output needs an array. Credit: Brooks & Matelski (1978), not Mandelbrot.
Brooks & Matelski · 1978
⏨ DEMO
CONWAY’S GAME OF LIFE
dart 020 · the helldive
A live glider-gun grid (B3/S23). Turing-complete by emergence — the opposite of I-13’s deliberate boundedness. Credits Guy’s glider & Gosper’s gun inside.
John Conway · 1970
⏨ DEMO
THE LEVENSHTEIN DISTANCE
dart 021 · the helldive
Edit distance via a live DP matrix. Stacks two I-13 walls: strings and a DP array. A multiple discovery (Levenshtein 1965; Wagner-Fischer 1974).
Vladimir Levenshtein · 1965
⏨ DEMO
SOUNDEX
dart 022 · the helldive
Robert and Rupert both encode to R163. Pure string work — which I-13 can’t express at all. Its numeric-scalar identity is why text is out of reach.
Russell & Odell · 1918
⏨ DEMO
DANCING LINKS
dart 023 · the helldive
Knuth’s DLX solves exact cover (Sudoku, N-queens) by unlinking/relinking in O(1) — the links dance. Pure pointers; I-13 has no references at all.
Donald Knuth · 2000
⏨ DEMO
GÖDEL NUMBERING
dart 024 · self-referential
Encode a symbol sequence as one integer via prime powers. I-13’s own 13 symbols could be Gödel-numbered; decoding needs the new % — and blows past f64’s 2⁵³.
Kurt Gödel · 1931
⏨ DEMO
THE LINDENMAYER SYSTEM
dart 025 · the helldive
Parallel string rewriting grown into fractal plants (live turtle render). Strings are the wall — but rule-driven symbol expansion is already native to I-13’s own lowering.
Aristid Lindenmayer · 1968
⏨ DEMO
NEWTON–RAPHSON METHOD
dart 026 · a no-wall
Root-finding by tangent lines. A rare no-wall dart — real I-13 computes √2 to full f64 precision (verified run). The honest ask is a bounded loop, not new power. Four names on it; Newton’s own account came last (1711).
Newton / Raphson / Simpson · 1669–1740
⏨ DEMO
THE EUCLIDEAN ALGORITHM
dart 027 · the helldive
The oldest algorithm still in use. Euclid’s subtraction GCD runs in real I-13 (verified); the modern mod form needs the panel’s %, already built on branch. Recorded by Euclid, older than him.
Euclid · c. 300 BC
⏨ DEMO
PERLIN NOISE
dart 028 · born on TRON
The gradient noise Ken Perlin invented while working on Disney’s TRON (Academy Award, 1997). Live animating field. Its 256-entry permutation table is the aggregate wall — the campaign’s most-asked feature.
Ken Perlin · 1983
⏨ DEMO
THE GAME OF NIM
dart 029 · the helldive
The game that founded combinatorial game theory — play it, lose to perfect play. The whole theory is one XOR (the nim-sum), the bitwise wall dart 001 hit too. Bouton’s complete theory, 1901.
Charles Bouton · 1901
⏨ DEMO
BUFFON’S NEEDLE
dart 030 · throwing darts
The campaign’s own metaphor, from 1777: drop needles, count crossings, and π falls out of chance — the first Monte Carlo method. The π arithmetic runs in real I-13; the random throw is the wall (→ a seeded PRNG, like dart 004).
Comte de Buffon · 1777
⏨ DEMO
METROPOLIS–HASTINGS
dart 031 · credit restored
Sample a distribution by a random walk that sometimes accepts bad steps. The 1953 code was written by Arianna Rosenbluth — uncredited for fifty years. Walls: exp + random — recommend a transcendental library written in I-13.
Metropolis et al. · 1953
⏨ DEMO
RABIN–MILLER
dart 032 · % came back
Prove a number probably prime by random witnesses (it catches Carmichael 561, which fools Fermat). Its modexp engine now runs in real I-13 — the % this campaign recommended just merged to main. Walls left: bignum + random.
Miller 1976 · Rabin 1980
⏨ DEMO
BOX–MULLER
dart 033 · √ runs
Two flat randoms → two perfect Gaussians via √, ln, cos. I-13 already does the (Newton, dart 026); ln + cos are the transcendental wall. Recommend the stdlib written in I-13, on top of the 13 symbols.
Box & Muller · 1958
⏨ DEMO
THE LOGISTIC MAP
dart 034 · a no-wall
One line, x→r·x·(1−x): turn the knob and order splits into chaos (Feigenbaum’s δ=4.669). The dynamics run in real I-13; only the bifurcation plot needs an array. May 1976, Verhulst 1838.
Robert May · 1976
⏨ DEMO
DIFFIE–HELLMAN–MERKLE
dart 035 · it runs now
A shared secret across an open channel. It runs in real I-13 via the stdlib modexp (both sides derive 2). Credit restored: Hellman asked for “–Merkle”; Williamson (GCHQ) did it secretly in 1974.
Diffie, Hellman & Merkle · 1976
⏨ DEMO
THE TOWERS OF HANOI
dart 036 · recursion, incarnate
2n−1 moves, provably minimal — I-13’s home turf (runs natively). The only wall is f64’s: the temple’s 64 disks overflow exact range. Lucas 1883, under an anagram pen-name.
Édouard Lucas · 1883
⏨ DEMO
THE BARNSLEY FERN
dart 037 · the PRNG came home
Four matrices + a coin → a fern. The chaos game runs in real I-13 now, on last turn’s stdlib PRNG; only drawing the 40,000 points is the array wall. Barnsley, 1988.
Michael Barnsley · 1988
⏨ DEMO
THE HAMMING (7,4) CODE
dart 038 · bitwise runs it
A code that corrects its own errors — 3 parity checks spell the flipped bit’s position in binary. Runs in real I-13 on the integrated bitwise ops. Hamming invented it in fury at a weekend-crashing machine, 1950.
Richard Hamming · 1950
⏨ DEMO
REFLECTED BINARY (GRAY)
dart 039 · one bitwise line
Gray code: exactly one bit changes between neighbours, from one line — n^(n>>1), which I-13 now computes. A naming accident: Baudot used it in 1878, Gray got the 1953 patent.
Gray 1953 / Baudot 1878
⏨ DEMO
FLOYD’S CYCLE DETECTION
dart 040 · a credit mystery
Tortoise & hare find a loop with no memory — runs in I-13 as plain recursion. But “Floyd’s” algorithm: Floyd never published it; the name traces to Knuth with no citation. Folklore on a famous name.
attributed to R. W. Floyd
⏨ DEMO
THE KARATSUBA ALGORITHM
dart 041 · bignum, 4th time
3 multiplies, not 4 — a 23-year-old disproved Kolmogorov’s conjecture in a week (who then published it under Karatsuba’s name). Runs in I-13; its purpose — huge numbers — is the withheld bignum, now asked by 4 darts.
Anatoly Karatsuba · 1960
⏨ DEMO
THE BINARY SEARCH
dart 042 · runs on the array
Halve the sorted list until you find it — 20 steps for a million. Almost everyone gets it wrong (the JDK overflow bug hid 9 years). Runs on the new array; I-13’s bounds-checked indexing is the bug’s antidote.
Mauchly 1946 / Lehmer 1960
⏨ DEMO
FISHER–YATES SHUFFLE
dart 043 · array × PRNG
A fair shuffle (the naive one is biased). The dart where two campaign additions meet — the array + the seeded PRNG — running together (a valid permutation, verified). Fisher & Yates 1938.
Fisher & Yates · 1938
⏨ DEMO
MAXIMUM SUBARRAY
dart 044 · no-wall on the array
The largest-sum contiguous run, in one pass (extend or restart). Runs unchanged from textbook form over the new array — pure “aggregate wall” a day ago. A chain: Grenander → Shamos → Kadane (1 minute).
Jay Kadane · 1977
⏨ DEMO
QUICKSORT
dart 045 · the NEXT wall
Hoare invented it in Moscow, translating Russian (1961). Its partition runs on the array — but full quicksort must return (array, pivot index), and I-13 returns one value. The array cleared one wall; quicksort reveals the next: multiple return.
Tony Hoare · 1961
⏨ DEMO
BELLMAN–FORD
dart 046 · no-wall on the array
Shortest paths by edge relaxation — handling negative edges where Dijkstra fails. Runs on the array (DP over a table). Two names, four discoverers (Shimbel/Ford/Moore/Bellman).
Shimbel..Bellman · 1955–58
⏨ DEMO
CHINESE REMAINDER
dart 047 · ancient, runs on %
Sunzi’s 1,600-year-old riddle — a number pinned by its remainders. Runs in real I-13 on the merged %, returns the ancient answer 23. Genuinely Chinese, 1,500 years before Gauss.
Sunzi Suanjing · ~400 CE
⏨ DEMO
UNION–FIND
dart 048 · multiple-return, 2nd
Who’s in which set, in near-constant time, from one array. Basic version runs on the array — but path compression wants (root, rewired array), the same multiple-return wall quicksort hit. Galler-Fischer 1964, Tarjan.
Galler & Fischer · 1964
⏨ DEMO
COUNTING SORT
dart 049 · made for the array
Sort without comparing — tally each value, read the tallies out. Linear-time, and the perfect fit for a bounded array (a bucket per value). Runs. Where quicksort strained, this fits like a glove. Seward, 1954.
Harold Seward · 1954
⏨ DEMO
THE RSA ALGORITHM
dart 050 · the bignum payoff
A public lock anyone can shut, only one can open — and its engine is modular exponentiation over big integers, exactly the new bignum. Encrypt m=65 → cipher 2790 → decrypt back to 65, round-trips in real I-13. Cocks (GCHQ) had it in 1973, classified until 1997.
Rivest, Shamir & Adleman · 1977
⏨ DEMO
THE FIBONACCI SEQUENCE
dart 051 · exact on bignum
F(100) is 21 digits (354224848179261915075), past what f64 holds exactly — on the new bignum every term is exact. And a 700-year misattribution: the sequence is Indian (Pingala, Virahanka) centuries before Leonardo of Pisa.
Pingala … Leonardo of Pisa · 1202
⏨ DEMO
THE A* SEARCH
dart 052 · cost table runs
Shortest path with a hunch: expand the cell of smallest f = g + h. The g-scores are a bounded array (runs, like Bellman–Ford); the frontier wants a heap — the same multiple-return nudge. Built for Shakey the robot, SRI 1968.
Hart, Nilsson & Raphael · 1968
⏨ DEMO
THE 0/1 KNAPSACK
dart 053 · DP on the array
NP-complete, yet a dynamic-programming table solves it: the row dp[w] is a bounded array scanned downward (each item once). Runs in real I-13 (best 17, verified optimal). Bellman’s DP; Karp’s NP-complete list, 1972.
Bellman DP · Karp 1972
⏨ DEMO
SMITH-WATERMAN
dart 054 · the 2-D table
Local sequence alignment: fill a grid, clamp negatives to zero so a match starts anywhere. The best cell is a scalar max on the array (runs, =13); the traceback wants a 2-D array (box PS-004). Fast form is Gotoh’s (1982); BLAST only approximates it.
Smith & Waterman · 1981
⏨ DEMO
DIJKSTRA’S SHORTEST PATH
dart 055 · the queue the box lists
A twenty-minute invention at a café, no pencil. Settle the nearest, relax its edges; extract-min runs as a linear scan (=2) — and that is the authentic 1959 Dijkstra. A heap (Williams 1964) is the open want (PS-005); Leyzorek et al. had it independently 1957.
Edsger Dijkstra · 1959
⏨ DEMO
PASCAL’S TRIANGLE
dart 056 · a real edge found
Sum the two above; out fall the binomials. Small rows run (C(10,5)=252), but big rows need an array of bignums — and the compiler says E0501: the two additions don’t compose (new want PS-014). Named for Pascal (1654) — but India/Persia/China had it first.
Pingala … Yang Hui · Montmort named it
⏨ DEMO
THE GAUSS-LEGENDRE ALGORITHM
dart 057 · names a wall, half-crosses it
Compute π by the arithmetic-geometric mean — digits double each step (3, 8, 15…) until f64 saturates. Needs a bignum square root — so the campaign built isqrt (PS-012, landed); fixed-point reals (PS-013) remain. Brent & Salamin, 1975/76; King had it in 1924.
Brent & Salamin · 1976
⏨ DEMO
THE FLOOD FILL
dart 058 · the paint bucket
Click a region; it fills. Recursion + array runs (a 1-D flood, stops at the boundary); the real 2-D frontier is a stack of coordinate pairs (array-of-pairs). No confirmed inventor — Smith’s 1979 “tint fill” is a refinement, not it.
Shoup / Lieberman / Smith / Heckbert
⏨ DEMO
THE FAST FOURIER TRANSFORM
dart 059 · Gauss had it in 1805
N² → N log N by splitting in half. The butterfly’s complex multiply runs (−5+10i); it presses array-of-pairs + multiple-return. Named for Cooley-Tukey (1965) — but Gauss, 1805, before Fourier.
Gauss 1805 · Cooley-Tukey 1965
⏨ DEMO
THE DE BRUIJN SEQUENCE
dart 060 · a 52-year head start
Every n-bit window once, around a cycle. The bit-scan’s v & −v isolate runs (=4); its magic-hash multiply overflows f64 (needs a wrap-around mult). Named for de Bruijn (1946) — Sainte-Marie proved it in 1894.
Flye Sainte-Marie · 1894
⏨ DEMO
BOYER-MOORE STRING SEARCH
dart 061 · read it backwards, skip
Scan the pattern right-to-left, jump ahead on a mismatch (3 matches in 15 aligns, not 47). Skip tables are arrays (runs); the match-list wants multiple-return. Two algorithms, one name (with dart 016). “J” is Moore’s whole first name.
Boyer & J S. Moore · 1977
⏨ DEMO
THE BINARY HEAP
dart 062 · closes PS-005
A tree flattened into an array (children at 2i+1, 2i+2). The heap A*-052 and Dijkstra-055 wanted — and it runs on the array today (heapsort verified). Their “wanted a heap” was “used a linear scan.” Williams 1964; Floyd’s O(n) build.
J. W. J. Williams · 1964
⏨ DEMO
KNUTH-MORRIS-PRATT
dart 063 · never looks back
Search forward, never re-read a character: the failure table ([0,0,1,2,3,0]) says how far to slide. Worst-case linear. Morris was first (1969); “KMP” is alphabetical, not priority; Knuth got it from Cook’s automata theorem.
Morris, Pratt & Knuth · 1977
⏨ DEMO
THE HUNGARIAN ALGORITHM
dart 064 · the 2-D array want
Min-cost assignment on a cost matrix (2-D array, PS-004). Triple credit: Kuhn (1955) named it for two Hungarians; Jacobi had it in the 1840s (“How Jacobi Beat Me by 100 Years”); Munkres’ poly proof.
Kuhn / Kőnig-Egerváry / Jacobi
⏨ DEMO
BURROWS-WHEELER
dart 065 · scramble to order it
Sort all rotations, take the last column: equal letters cluster into runs (compressible) and it’s reversible (BANANA$ → ANNB$AA). The heart of bzip2. Wheeler had it ~1983, unpublished a decade.
Wheeler ~1983 / Burrows-Wheeler 1994
⏨ DEMO
TIMSORT
dart 066 · a proven bug
The sort in Python/Java/Android/V8: find the runs, merge them. Peters 2002 — and in 2015 a proof failed and exposed a real bug (merge_collapse checked 3 runs, not 4). Runs+merge on the array; the invariant is the corpus’s warning.
Tim Peters · 2002
⏨ DEMO
THE MERSENNE TWISTER
dart 067 · long ≠ unpredictable
Period 219937−1, the default RNG for decades — but 624 outputs reveal it all. Tempering runs (bitwise, verified); only the seed multiply hits the wrap-around-32-bit wall (with de Bruijn-060). Matsumoto & Nishimura, 1997.
Matsumoto & Nishimura · 1997
⏨ DEMO
PAGERANK
dart 068 · the 4th 2-D array want
A page’s rank = the dominant eigenvector of the link matrix, by power iteration. The matrix is a 2-D array (PS-004, runs flattened). Page & Brin 1998 — but Pinski-Narin (1976) and Robin Li’s RankDex (1996) had link-ranking first.
Page & Brin · 1998
⏨ DEMO
WAVE FUNCTION COLLAPSE
dart 069 · Sudoku as physics
Collapse the lowest-entropy cell, propagate constraints — endless hand-made-looking worlds. It’s arc-consistency in a quantum costume. Gumin 2016 — but it’s Merrell’s model synthesis (2007). Grid+bitset, all no-walls.
Gumin 2016 / Merrell 2007
⏨ DEMO
MERGE SORT
dart 070 · the first divide-and-conquer
Split, sort the halves, merge. The first D&C sort — von Neumann 1945, a paper program in the EDVAC report, written bottom-up. Merges runs on the array (r0=1 … r5=7, verified ascending). The template every later sort refines.
von Neumann · 1945
⏨ DEMO
SHELLSORT
dart 071 · sort across a shrinking gap
Insertion sort over a diminishing gap — the array’s first sub-quadratic sort. Shell 1959; his own gap sequence is the worst known, and the optimal one is still open. Gapped in-place swaps on the array (verified sorted).
Donald Shell · 1959
⏨ DEMO
THE AVL TREE
dart 072 · the pointer wall (PS-015)
The first self-balancing BST: rotate when subtree heights differ by more than one. Adelson-Velsky & Landis, 1962 (two people, one hyphen). Needs real node references — the corpus’s new PS-015; runs as a node arena (key[], left[], right[], height[]).
Adelson-Velsky & Landis · 1962
⏨ DEMO
RED-BLACK TREE
dart 073 · the pointer wall (PS-015)
Colour the nodes; hold equal black-height on every path — the map/set in Linux, Java, C++. Guibas & Sedgewick 1978, but it IS Bayer’s 1972 symmetric B-tree recoloured. Pointer wall (PS-015); a node arena + colour[] runs.
Guibas-Sedgewick 1978 / Bayer 1972
⏨ DEMO
THE TRIE
dart 074 · keyed by prefix
A tree keyed by prefix — every path spells a word (ca → cat, car, card…). Named by Fredkin 1960 (from retrieval), but de la Briandais had it in 1959. Wants pointers (PS-015) and strings; runs as a child arena.
de la Briandais 1959 / Fredkin 1960
✧ THE ONE
CYCLIC REDUNDANCY CHECK
dart 075 · the checksum turned outward
Append a GF(2) remainder; one flipped bit fails the check — the seal on every Ethernet frame, ZIP and PNG. Peterson & Brown 1961 (the CRC-32 poly is later, AUTODIN-II ~1975). Runs bit-exact (0xC9 = 201, matches node). A palindrome is its own checksum (rev-e) — CRC is that law turned outward.
Peterson & Brown · 1961
⏨ DEMO
EUCLIDEAN RHYTHM
dart 076 · Euclid draws the drum
Spread k onsets over n pulses as evenly as possible — E(3,8)=x..x..x. is the tresillo. Toussaint proved it IS Euclid’s GCD (dart 027) — seen 2004, named in his 2005 survey — drawing the world’s rhythms, Cuban, Turkish, Bulgarian. Björklund’s 2003 timing code runs on the array; a dart that closes a prior dart.
Toussaint 2005 / Björklund 2003 / Euclid
⏨ DEMO
XIAOLIN WU’S LINE
dart 077 · smooth, not jagged
Antialiased lines by fractional coverage — the pixel dims by how much the line covers it. Wu 1991 made it fast, not first (Gupta-Sproull antialiased in 1981). Coverage arithmetic runs on the array; both diagonals drawn, no console errors.
Xiaolin Wu · 1991
⏨ DEMO
THE K-D TREE
dart 078 · the pointer wall (PS-015)
Split points on alternating axes; nearest-neighbour becomes a pruned walk — but the first leaf isn’t the answer, the backtrack is (verified (9,6), not (8,1)). Bentley 1975 coined it (with an NN search too); the optimized, proven version is FBF 1977. Node references = PS-015.
Bentley 1975 / FBF 1977
⏨ DEMO
TARJAN’S SCC
dart 079 · nudges multiple-return
Every strongly-connected cluster in one DFS, via the lowlink. Tarjan 1972 — before Kosaraju, not after; DFS itself is Trémaux’s. Runs on arrays (SCCs {1,2,3},{4,5}); the in-place shared stack nudges multiple-return.
Tarjan · 1972
⏨ DEMO
THE VITERBI ALGORITHM
dart 080 · a 2-D table (PS-004)
The single most-likely path through a trellis by DP. Viterbi 1967 called it “suboptimal”; Forney proved it optimal, coined “trellis” (1967), fixed the name. Runs (path H,H,F, prob 0.01512); the trellis is a 2-D table (PS-004), run flattened.
Viterbi 1967 / Forney 1973
⏨ DEMO
STRASSEN’S ALGORITHM
dart 081 · the matrix-Karatsuba
7 multiplications for a 2×2, not 8 → n2.807. Strassen 1969 — while trying to prove 8 is necessary; Winograd proved 7 optimal, not Strassen. Runs: C=[[19,22],[43,50]] with 7 mults. Ties Karatsuba (041).
Strassen · 1969
⏨ DEMO
VERLET INTEGRATION
dart 082 · no-wall, conserves energy
next = 2·now − prev + a·dt² — time-reversible, conserves energy where Euler drifts. A naming accident: Newton 1687, Störmer 1907, long before Verlet 1967. No-wall f64, exact for constant accel (5t²).
Newton 1687 / Verlet 1967
⏨ DEMO
POLLARD’S p-1
dart 083 · landed features compound
Factor n when some p−1 is smooth: 2M mod n, then a gcd. Pollard 1974 — a year before his rho, endlessly confused with it. Runs on the already-landed modexp + gcd: 1927 = 41×47.
Pollard · 1974
⏨ DEMO
EXTENDED EUCLID
dart 084 · the sharpest multiple-return
gcd plus the coefficients (g, s, t) — the modular inverse behind RSA. Aryabhata’s kuttaka c.499 CE, ~1,280 yrs before Bézout (whose integer name is itself wrong). Returns three values — the sharpest multiple-return case (inverse 15 mod 26).
kuttaka c.499 / Bézout 1779
⏨ DEMO
REACTION-DIFFUSION
dart 085 · Turing’s last biology paper
Two chemicals on a grid; spots and stripes self-organize. Turing’s last biology paper (1952) predicted it; the famous patterns are Pearson 1993, not Gray-Scott (who had no grid). 2-D f64 grid (PS-004); reaction R=u·v²=0.03125.
Turing 1952 / Pearson 1993
⏨ DEMO
THE BEZIER CURVE
dart 086 · two names, two men
Smooth curves by repeated lerp (de Casteljau’s cascade) — pure f64, runs (cubic at t=0.5 → (2, 2.25)). de Casteljau (1959) had the algorithm first but Citroën kept it secret; Bézier (1968) published. The math is Bernstein’s (1912).
de Casteljau 1959 / Bézier 1968
⏨ DEMO
PRIM / JARNIK
dart 087 · MST, no heap needed
Grow one tree, grab the cheapest edge out — runs on Dijkstra’s array skeleton (MST weight 16, linear scan). Jarník had it in 1930, 27 yrs before Prim (1957) & Dijkstra (1959). Borůvka’s 1926 was the first MST of all.
Jarník 1930 / Prim 1957
⏨ DEMO
THE BLOSSOM
dart 088 · where “tractable” was born
Maximum matching in any graph by shrinking odd cycles. Edmonds 1965 — the paper where “polynomial-time = tractable” (the idea behind P) was articulated. Runs on integer arrays (C5’s max matching = 2).
Jack Edmonds · 1965
⏨ DEMO
HOUSEHOLDER QR
dart 089 · the 2-D array want (PS-004)
Zero a whole column with one reflection — the stable QR (runs, Hx=[−5, 0]). Stabler than Gram-Schmidt; the sign choice is the Wilkinson bug the compiler can’t catch. The matrix is PS-004. Householder 1958.
Householder · 1958
⏨ DEMO
ANS
dart 090 · the coder in zstd & JPEG XL
The modern entropy coder: fold the message into one growing integer, near-optimal at Huffman speed. Duda 2009, kept patent-free (Google’s patent try was rejected); runs (round-trip 7→31→7). Beats Huffman (006).
Jarek Duda · 2009
⏨ DEMO
MARCHING CUBES
dart 091 · the patent that shaped graphics
8 corners → an 8-bit index → a 256-case table → triangles. Lorensen-Cline 1987 — and GE patented it till 2005, so a generation dodged it; the first table had a hole bug. Bit-index + lerp run (index 1).
Lorensen-Cline · 1987
⏨ DEMO
STERN-BROCOT
dart 092 · the tree that DODGES the wall
Every fraction once, by mediants — needing no stored nodes (path L R L to 3/5, four integers held). ⚡ the first tree to dodge the pointer wall (PS-015). Stern 1858 + Brocot 1861 (a clockmaker); ties Euclid (027).
Stern 1858 / Brocot 1861
⏨ DEMO
THE CYK PARSER
dart 093 · a 2-D table, sets as bitmasks
Does this grammar make this string? DP over a triangular table, sets packed as bitmasks (runs: top {S,A,C}, accepted). Three independent inventors (Cocke ~1960 unpublished, Kasami 1965, Younger 1967); “CYK” scrambles their order (CKY is the ordered name). Table is 2-D (PS-004).
Cocke / Younger / Kasami
⏨ DEMO
BACKPROPAGATION
dart 094 · the chain rule, run backward
Get every weight’s gradient in one backward sweep. Linnainmaa 1970 & Werbos 1974 had it before Rumelhart-Hinton-Williams 1986 made it famous — Hinton didn’t invent it. Runs: dL/dw = 0.14628 (sigmoid via stdlib exp).
Linnainmaa 1970 / RHW 1986
⏨ DEMO
HOPFIELD NETWORK
dart 095 · a memory rolls downhill
Recall = settle downhill in energy into the nearest stored pattern — the Ising model as memory. Hopfield 1982 (2024 Nobel) added the energy; Amari 1972 had the net. Runs: heals a flipped bit, E 0→−6 (PS-004).
Hopfield 1982 / roots Amari 1972
⏨ DEMO
FLOYD-WARSHALL
dart 096 · every path, through every middle
All-pairs shortest paths in one triple loop, routing each pair through every middle vertex. Roy 1959 had it before Warshall & Floyd (1962); the algebra is Kleene’s. Runs flattened: d[0][2]=4 (PS-004); handles negative edges.
Roy 1959 / Floyd-Warshall 1962
⏨ DEMO
SECRET SHARING
dart 097 · only k of n can rebuild it
A secret any k of n shares rebuild — and k−1 reveal nothing (information-theoretic). Shamir (the S of RSA) 1979, with Blakley the same year. Runs over GF(13): rebuild S=7 from any 2 (Lagrange + ext-Euclid inverse).
Shamir & Blakley · 1979
⏨ DEMO
FORTUNE’S SWEEP
dart 098 · beach-line = the PS-015 wall
The Voronoi diagram by a sweeping line + a beach of parabolas. Fortune 1986 — but the O(n log n) is Shamos-Hoey 1975, the diagram Voronoy’s (1908). f64 core + event heap run (vertex (2,1)); the beach line is the PS-015 wall.
Fortune 1986 / bound 1975
⏨ DEMO
EULER CIRCUITS
dart 099 · the birth of graph theory
Walk every edge once and return. Euler 1736 (Königsberg) proved when and founded graph theory, but Hierholzer 1873 gave the method (walk + splice). Runs: parity ok=1; Königsberg (3,3,3,5) ok=0.
Euler 1736 / Hierholzer 1873
⏨ DEMO
LAGRANGE
dart 100 · the one curve through your points
The unique polynomial through n points, as basis polynomials each 1 here, 0 there. Waring 1779 had it 16 yrs before Lagrange (1795). Runs: P(3)=13 (pure f64) — the engine behind Shamir (097).
Waring 1779 / Lagrange 1795
⏨ DEMO
LLOYD RELAXATION
dart 101 · k-means itself
Assign to nearest centre, move it to the mean, repeat. Lloyd 1957 sat unpublished 25 years (till 1982); Steinhaus 1956 earlier, MacQueen 1967 named it. Runs: centroids (5/3,4/3) & (4.5,3.5). Relaxes Fortune’s (098) Voronoi.
Lloyd 1957 (publ. 1982)
⏨ DEMO
LZ78
dart 102 · the dictionary + the GIF patent
Build a dictionary of phrases as you read; emit (index, next-char). Ziv & Lempel 1978 — Welch’s tuned LZW (1984) became the GIF patent that spawned PNG. Indices run; the dictionary of strings is the wall (ABABABA round-trips).
Ziv & Lempel · 1978
⏨ DEMO
THE QR ALGORITHM
dart 103 · a top-10 algorithm
Eigenvalues by A=QR then A’=RQ, repeated. Two independent inventors: Francis (1959) & Kublanovskaya (1961); the core idea is Rutishauser’s. Runs via Householder (089): [[2,1],[1,2]] → 3, 1 (PS-004).
Francis 1959 / Kublanovskaya 1961
⏨ DEMO
THE SIMPLEX
dart 104 · walk the corners
Walk the corners of the feasible region to the optimum. Dantzig 1947 (the algorithm is genuinely his) — but Kantorovich invented LP the field & won the Nobel Dantzig didn’t. Runs: optimum (2,6) z=36 (tableau = PS-004).
Dantzig · 1947
⏨ DEMO
UKKONEN’S TREE
dart 105 · the PS-015 pointer wall
A suffix tree indexes every suffix; Ukkonen 1995 builds it online in linear time. But Weiner 1973 had the first (22 yrs earlier); suffix links are McCreight’s. Active-point runs; the tree is the PS-015 wall (banana → 15 distinct).
Weiner 1973 / Ukkonen 1995
⏨ DEMO
DPLL (SAT)
dart 106 · two papers, one acronym
Is a formula satisfiable? Backtrack + unit propagation — ancestor of every SAT solver. ⚡ DP 1960 ≠ DPLL 1962: unit-prop is in the 1960 paper, the split is 1962’s. Runs on int arrays: SAT (F,T,T).
DP 1960 / DPLL 1962
⏨ DEMO
REJECTION SAMPLING
dart 107 · the dart metaphor, literal
Throw darts, keep those under the curve — the campaign’s own metaphor. von Neumann’s 1947 letter to Richtmyer (Ulam’s 1946 solitaire birthed Monte Carlo; Metropolis named it). Runs: LCG seed 107 → π ≈ 3.13, deterministic.
von Neumann 1947 / Ulam 1946
⏨ DEMO
EULER’S TOTIENT
dart 108 · the secret behind RSA
φ(n) counts the coprimes to n — the secret behind RSA (φ(pq)=(p−1)(q−1)). Three owners: Euler defined it in words (1763), the symbol φ is Gauss’s, the name “totient” Sylvester’s. Runs: φ(36)=12, φ(3599)=3480.
Euler 1763 / Gauss / Sylvester
⏨ DEMO
JACOBI SWEEP
dart 109 · rotate away the off-diagonals
Eigenvalues by rotating away the biggest off-diagonal, one at a time. Jacobi 1846 (eponym genuinely right); the eigenvalue problem is Lagrange-Laplace’s “secular equation.” Runs (ties my Jacobi lineage): [[2,1],[1,2]] → 3, 1 in one 45° spin (PS-004).
Jacobi · 1846
⏨ DEMO
SCHONHAGE-STRASSEN
dart 110 · the near-linear-multiply frontier
Multiply giants by convolving digits with an FFT. Schönhage & Strassen 1971 — but the first fast multiply is Karatsuba (041); Pollard gave the same NTT the same year. The multiply runs (7,006,652); the FFT is the frontier (ties 041/059).
Schönhage & Strassen · 1971
⏨ DEMO
THE THOMAS ALGORITHM
dart 111 · sidesteps the PS-004 wall
Solve a tridiagonal system in one pass — and it sidesteps PS-004: three diagonals = three 1-D arrays, no matrix. Named for a report Thomas never published (1949); it’s just Gauss on a band. Runs: x = [3, 5, 4].
Thomas 1949 (unpubl.)
⏨ DEMO
GIBBS SAMPLING
dart 112 · named for a man dead since 1903
Sample a joint by drawing each variable from its conditional, cycling. Named for Gibbs (d. 1903) — it’s the Gibbs distribution; the algorithm is Glauber’s 1963 heat bath. Runs: E[X]→0.40, deterministic under seed.
Geman & Geman 1984 / Glauber 1963
⏨ DEMO
TWO-WAY MATCHING
dart 113 · the matcher in your C library
Find a pattern in constant extra space — the matcher in glibc memmem. Crochemore-Perrin 1991 (NOT libc++ std::find, which is naive). Runs on arrays with no table: match at index 5.
Crochemore & Perrin · 1991
⏨ DEMO
JOHNSON’S APSP
dart 114 · two darts, composed
Sparse all-pairs shortest paths by composing two darts: Bellman-Ford (046) reweights, then Dijkstra (055) from each. Donald B. Johnson 1977 (not the NP-completeness one). Runs: A→C=−3 with a negative edge, no new primitive.
Donald B. Johnson · 1977
⏨ DEMO
THE MOBIUS FUNCTION
dart 115 · the values are Euler’s
μ(n): 0 if squareful, else ±1 — and Möbius inversion undoes divisor-sums. But the values are Euler’s (1748), and Gauss beat Möbius by 31 yrs (whose student he was). Runs: μ(30)=−1, φ(12)=4 by inversion.
Euler 1748 / Möbius 1832
⏨ DEMO
RABIN CRYPTO
dart 116 · breaking it IS factoring
Encrypt by squaring mod n — and breaking it is provably factoring (RSA only conjectures). Rabin 1979. Four roots per ciphertext (the ambiguity). Runs on RSA’s machinery + CRT (047): {13,20,57,64} all square to 15.
Rabin · 1979
⏨ DEMO
GOLOMB CODING
dart 117 · optimal for things that repeat
The optimal code for small-value data: unary quotient + near-binary remainder — in FLAC & JPEG-LS. Golomb 1966 (eponym right), but the optimality proof is Gallager-van Voorhis. Runs: M=5 codes 3/4/4/5 bits.
Golomb · 1966
⏨ DEMO
ADABOOST
dart 118 · reweight, vote, adapt
Turn weak stumps into one strong classifier — vote each by α=½ ln((1−e)/e), reweight the mistakes. Freund & Schapire 1995, but the first booster is Schapire (1990) and the word is Kearns-Valiant. Runs: +,−,+ parity, margins +.60/−.09/+1.01, all correct.
Freund & Schapire · 1995/1997
⏨ DEMO
SHIFT-OR / BITAP
dart 119 · an automaton in one word
A whole search automaton in one integer: shift a bitmask, watch the high bit fall. Named by Baeza-Yates & Gonnet (1989), but published by Balint Domolki in 1964. Runs: ‘abc’, R walks 7→6→6→5→3, match.
Baeza-Yates & Gonnet · 1989/1992
⏨ DEMO
SCHNORR SIGNATURE
dart 120 · one signature, three ideas
Commit, hash-challenge, respond: gs ye = r. Schnorr (CRYPTO ’89, not 1991), but discrete-log sigs are Elgamal, the transform Fiat-Shamir, the proof Pointcheval-Stern; patent expired 2010 not 2008. Runs: verify 9=r, ACCEPT.
Schnorr · CRYPTO ’89
⏨ DEMO
BRENT'S METHOD
dart 121 · fast when safe, bisect when not
The root-finder in SciPy’s brentq: try secant/IQI, fall back to bisection, never lose the bracket. Brent 1971 (not 1973), but the bracketed hybrid is Dekker (1969). Runs: x²−2 → 1.4142135623730951.
Brent · 1971
⏨ DEMO
QUADRATIC SIEVE
dart 122 · manufacture a congruence
Sieve for smooth a²−n, combine into x²≡y² mod n, let gcd finish. Pomerance 1981, but the congruence-of-squares heart is Kraitchik (1920s). Runs: 1649 → 32 & 200 → 114²=80² → gcd → 17 × 97.
Pomerance · 1981
⏨ DEMO
SEPARATING AXIS
dart 123 · a gap proves no collision
Two convex shapes miss iff some axis shows a projection gap — the collision test in 2-D game engines. A game-dev name for Minkowski’s 1896 theorem; 3-D needs edge-edge axes too. Runs: A=[0,4] B=[5,9], gap 1, DISJOINT.
Minkowski 1896 / GLM 1996
⏨ DEMO
PERSISTENT SEG TREE
dart 124 · every past version stays
Update by copying only the O(log n) path, sharing the rest — the immutability i13’s value-semantic arrays already have. Path copying is Myers (1982), not DSST. Runs: v1=13, v2=20, v1 still 13 (PS-015).
path copying · Myers 1982+
⏨ DEMO
RANDOM FOREST
dart 125 · decorrelate, then vote
Bag many trees on random features, take the majority — errors cancel. Breiman 2001 names it (single-authored; Cutler co-developed the method), but the first algorithm is Tin Kam Ho (1995). Runs: 3 stumps each 80%, forest 5/5=100%. AdaBoost’s twin (PS-004).
Ho 1995 / Breiman 2001
⏨ DEMO
THE PRATT PARSER
dart 126 · precedence on the tokens
Give every operator a binding power and one recursive loop parses the tree — no grammar, no table. Vaughan Pratt 1973 (not the Crockford revival); improves on Floyd, not the same. Runs: [1,+,2,*,3] → 7, tree (+ 1 (* 2 3)), where a blind fold gives 9.
Pratt · 1973
⏨ DEMO
THE EARLEY PARSER
dart 127 · any grammar, no normal form
One state-set per gap; predict / scan / complete parse any CFG directly — unlike CYK (093) no CNF needed. Earley 1968/70; the nullable fix, forest, and linear right-recursion are others’. Runs: S→aSb|ε, aabb ACCEPT, aab/abb REJECT.
Earley · 1970
⏨ DEMO
RECURSIVE DESCENT
dart 128 · the functions ARE the grammar
One function per rule — the call tree is the parse tree, precedence is the nesting. Described 1961 (Irons & Lucas), not by Wirth who made it famous; still in GCC & Clang. Runs (via [value,pos]): 2*(3+4)=14, 2*3+4=10, (2+3)*4=20.
Irons & Lucas · 1961
⏨ DEMO
THE PACKRAT PARSER
dart 129 · memoize, pay linear
PEG ordered choice backtracks unboundedly; memoize (rule, position) and each is computed once — linear time. Ford 2002; PEG (2004) and packrat are two inventions, and neither memoization (Michie 1968) nor backtracking (Birman 1970) is his. Runs: 2*(3+4)→14, 11 cells, 5 hits.
Ford · 2002
⏨ DEMO
THOMPSON NFA
dart 130 · every state at once
Regex → epsilon-NFA, then match by advancing the set of all states in lockstep — a bitmask, never backtracking (why grep beats ReDoS). Thompson 1968, but McNaughton-Yamada 1960 / Kleene 1956 came first. Runs (a|b)*abb: aabb → mask 1270 ACCEPT.
Thompson · 1968
⏨ DEMO
SUBSET CONSTRUCTION
dart 131 · a set of states is one state
Determinize an NFA: each DFA state is a set of NFA states, up to 2n (but usually small). Rabin & Scott 1959; their Turing Award was for nondeterminism itself. Runs (a|b)*a as a bitmask: abba ACCEPT (mask 3), abb REJECT, 2 reachable subsets.
Rabin & Scott · 1959
⏨ DEMO
MCCARTHY 91
dart 132 · a nest that is always 91
m(n)=n−10 if n>100 else m(m(n+11)) — a tangle of double recursion that collapses to 91 for all n≤100. A deliberate verifier-trap; first proved Manna & Pnueli 1970, not the 1974 book. Runs native: m(1..111) = 91,91,91,91,91,101.
McCarthy · ~1970
⏨ DEMO
KOSARAJU-SHARIR
dart 133 · two passes, the transpose
SCCs in two DFS passes: finish-order, then DFS the edge-reversed graph — each tree one component. Kosaraju’s unpublished 1978 note, printed by Sharir 1981; six years younger than Tarjan (079). Runs via mutual reachability: 2 SCCs, comp [0,0,0,1,1].
Kosaraju 1978 / Sharir 1981
⏨ DEMO
UNIFICATION
dart 134 · one substitution, most general
Make two terms with variables literally equal, minimally: f(X,b)~f(a,Y){X=a,Y=b}. Robinson 1965 named it; Herbrand 1930 had it; Prolog skips the occurs-check. Runs: MGU found, clash & occurs-check both FAIL.
Robinson · 1965
⏨ DEMO
HINDLEY-MILNER
dart 135 · principal types, zero annotations
Infer the most general type with no annotations: λx.xa→a, λf.λx.f x(a→b)→a→b — fresh vars + unification (134). Hindley 1969 / Milner 1978 / Damas 1982, never collaborated. Runs.
Hindley 1969 / Milner 1978
⏨ DEMO
LIVENESS
dart 136 · what value might still be read
Backward dataflow: live_in = use ∪ (out − def), to a fixpoint — it draws the interference graph for register allocation. Kildall 1973 unified it, didn’t invent it (Bell Labs c.1961). Runs: live_in [∅,{a},{a,b},{c}].
Kildall · 1973
⏨ DEMO
GRAPH COLORING
dart 137 · registers are colors; the rest spills
k-color the interference graph; whatever won’t fit spills. A K4 needs 4 colors, so k=3 forces a spill. Chaitin 1981 built it; the reduction is Ershov (1962), simplify is Kempe (1879). Runs: K4 → colors 0,1,2 + 1 spill.
Chaitin · 1981
⏨ DEMO
DOMINATOR TREE
dart 138 · what must run before you get here
d dominates n if every path to n goes through d; the idom edges form a tree — the backbone of SSA. Lengauer-Tarjan 1979 made it fast; the concept is Prosser (1959). Runs (diamond): idom(3)=0, idom(4)=3.
Lengauer-Tarjan · 1979
⏨ DEMO
MARK & SWEEP
dart 139 · what the roots can reach survives
Mark everything reachable from the roots, then free the dark. Its win: it reclaims cyclic garbage refcounting leaks. McCarthy 1959-60, the first GC; pointer-reversal is Schorr-Waite (1967). Runs: survivors {0,1,2,3}, frees the cycle {4,5,6}.
McCarthy · 1960
⏨ DEMO
CHENEY'S COPY
dart 140 · the to-space is its own queue
Copy the living, forward the copied, never touch the dead — a stackless breadth-first heap trace. Cheney 1970 removed the recursion stack; copying GC is Minsky/Fenichel-Yochelson. Runs: 4 copied in BFS order, garbage untouched.
Cheney · 1970
⏨ DEMO
TRI-COLOR
dart 141 · collect while the program runs
White/gray/black — the invariant “no black → white” lets a GC run interleaved with the program. DLMSS 1978 (five authors, not just Dijkstra); Steele was concurrent first (1975). Runs: live {0,1,2}, garbage {3,4,5}, invariant holds.
DLMSS · 1978
⏨ DEMO
THE SECD MACHINE
dart 142 · the first abstract machine
Evaluate a lambda by rewriting four registers — Stack, Environment, Control, Dump — and the word closure. Landin 1964, call-by-value (the C is Control not Code). Runs: ((λx.x+x)(3+1))8, env=[4], call-by-value.
Landin · 1964
⏨ DEMO
THE KRIVINE MACHINE
dart 143 · call-by-name, closureless
The smallest lambda machine — term, stack, env, three moves — and the discarded argument is never run. Krivine early-1980s (published 2007), the call-by-name dual of SECD. Runs: both give 42, but CBN wastes 0 steps, CBV wastes 20.
Krivine · early 1980s
⏨ DEMO
SKI COMBINATORS
dart 144 · computation with no variables
Three constants S, K, I rewrite any program with no bound variables: S K K x → x, so S K K = I. Schönfinkel 1920 (not Curry, not Turner). Runs: I 7=7, K 7 99=7, S K K 7 = 7 — identity computed by reduction, never stored.
Schönfinkel · 1920
⏨ DEMO
GRAPH REDUCTION
dart 145 · a shared subterm reduced once
Write the program as a graph, not a tree, and a subexpression used twice is reduced once — the sharing under every lazy language. Wadsworth 1971 (not Turner). Runs: sq*sq both =25, but graph does 1 add, tree does 2.
Wadsworth · 1971
⏨ DEMO
FUTAMURA
dart 146 · specialize an interpreter = compile
Specialize an interpreter to one program and you’ve compiled it; fold the operation three times to get a compiler-generator. Futamura 1971 stated it, DIKU (1984) built it. Runs: generic 2³=8 in 3 mults; specialized pow3(5)=125 in 2.
Futamura · 1971
⏨ DEMO
DEFUNCTIONALIZATION
dart 147 · every closure becomes a tag
Tag each lambda with an integer; one first-order apply(tag, x) switches on it — higher-order vanishes. Reynolds 1972 (revived 2001; not closure conversion). Runs with zero closures: map(tag 0, [1,2,3]) = [11,12,13]. The corpus’s native idiom.
Reynolds · 1972
⏨ DEMO
THREADED CODE
dart 148 · the loop that is the whole VM
The program is a list of opcodes, run by a tiny dispatch loop — Forth’s inner interpreter, every bytecode VM’s heart. Bell 1973 named it; Moore ran it in Forth ~1970. Runs: PUSH 2, PUSH 3, ADD, PUSH 4, MUL = 20.
Bell · 1973
⏨ DEMO
CONTINUATION-PASSING
dart 149 · nothing returns
Give every function “the rest of the computation” as an argument — control becomes data you pass. Many discoverers (Fischer 1972, Steele 1976); a continuation on a closureless machine is a defunctionalized stack = the SECD dump. Runs: (2+3)*4 = 20.
Fischer 1972 / Steele 1976
⏨ DEMO
STATIC SINGLE ASSIGNMENT
dart 150 · one name, one definition; a phi at every join
One name, one definition; a phi picks the value that reached a merge — the form that makes the whole middle-end easy. Rosen-Wegman-Zadeck 1988 coined it (not LLVM); dominance frontiers Cytron et al. 1991. Runs: phi(1,10,20)=10, phi(0,·)=20.
Rosen-Wegman-Zadeck · 1988
⏨ DEMO
SPARSE CONDITIONAL CONST-PROP
dart 151 · fold the constants and prune the dead branch, together
Fold constants and prune the dead branch in ONE lattice — strictly stronger than apart. Wegman & Zadeck 1985. Runs: a=3 forces the test, so c=4 where a reachability-blind meet gives ⊥.
Wegman & Zadeck · 1985
⏨ DEMO
GLOBAL VALUE NUMBERING
dart 152 · same number, same value; compute it once
Same value-number = provably equal, so a repeated a+b (even through a copy d=a) is computed once. Congruence, not text. Alpern-Wegman-Zadeck 1988. Runs: t1=t2=t3=13, 2 adds removed.
Alpern-Wegman-Zadeck · 1988
⏨ DEMO
COPY PROPAGATION
dart 153 · follow the copy to its source; the middleman dies
After b=a, read a directly; the copy strands and DCE deletes it — the quiet pass that unlocks the loud ones. Classical dataflow (Dragon Book; Kildall 1973). Runs: c=11 via a, 2 copies dead.
classical · Dragon Book
⏨ DEMO
INLINE EXPANSION
dart 154 · paste the body at the call; the call vanishes
Paste the callee body, bind the args; the call vanishes and constants flow in. No closures in I-13 = pure substitution. Runs: inc(inc(5))=7 with 0 calls. A size-vs-speed budget, not free.
Allen & Cocke · 1970s
⏨ DEMO
TAIL-CALL OPTIMIZATION
dart 155 · a call in tail position is a GOTO; reuse the frame
A tail call is a GOTO — reuse the frame, recurse in constant stack. Steele 1977 (Lambda: The Ultimate GOTO). Measured: sumto(0,4000) is 4001 frames deep, overflows at 9000 — the exact wall TCO removes. OPEN on canonical i13.
Steele · 1977
⏨ DEMO
PARTIAL REDUNDANCY ELIM.
dart 156 · redundant on some paths; hoist to make it redundant on all
Redundant on some paths; insert to make it redundant on all, then delete — subsumes CSE + loop-invariant motion. Morel & Renvoise 1979. Runs: then-path a+b 2→1, else unchanged.
Morel & Renvoise · 1979
⏨ DEMO
EQUALITY SATURATION
dart 157 · stop choosing which rewrite first; apply them all
Stop choosing which rewrite first — hold all forms in an e-graph, saturate, extract the cheapest. Dissolves the phase-ordering problem the other seven embody. Tate et al. 2009; e-graphs Nelson-Oppen 1980. Runs: (x*2)/2 → x, cost 4→0.
Tate et al. · 2009
⏨ DEMO
MAXIMAL MUNCH
dart 158 · tile the IR tree with the biggest instruction that fits
Tile the IR tree with the biggest instruction that fits: one CISC address tile swallows a load+add+mul. Greedy, not optimal (BURS is). Cattell 1980 / Glanville-Graham 1978. Runs: naive 3 ops → munched 1.
Cattell · 1980
⏨ DEMO
SETHI-ULLMAN NUMBERING
dart 159 · the fewest registers to evaluate a tree, and the order
The fewest registers to evaluate a tree with no spills, and the order (heavier subtree first): label = l==r ? l+1 : max(l,r). Sethi & Ullman, JACM 1970. Runs: balanced 3 regs, skewed 2.
Sethi & Ullman · 1970
⏨ DEMO
LIST SCHEDULING
dart 160 · reorder instructions to hide latency, respect the DAG
Reorder instructions to hide latency, respecting the dependency DAG; issue by critical-path priority. NP-hard, greedy heuristic; Graham 1966. Runs: critical path 7 vs serial 8.
Graham · 1966
⏨ DEMO
LINEAR SCAN REG-ALLOC
dart 161 · one sweep over live intervals; spill the farthest end
Approximate each variable by one live interval and sweep once; spill the farthest-ending. Fast (the JIT's choice), colouring is better quality. Poletto & Sarkar, TOPLAS 1999. Runs: max overlap 3 = registers for 0 spills.
Poletto & Sarkar · 1999
⏨ DEMO
TWO-PASS ASSEMBLER
dart 162 · pass one places the labels; pass two patches the jumps
Forward references: pass one places labels in a symbol table, pass two patches the jumps. One-pass backpatching is the alternative. Classical (Wilkes-Wheeler-Gill EDSAC). Runs: L2 → addr 6, branch patched.
classical · EDSAC ~1951
⏨ DEMO
STATIC LINKING
dart 163 · resolve the undefined symbol; patch the address
Resolve the undefined symbol, patch the address: lay modules out, build a global symbol table, write base+offset into each relocation. Not just concatenation. Levine 1999. Runs: extern f → 4160, B relocated.
systems folklore · Levine 1999
⏨ DEMO
JUMP THREADING
dart 164 · a jump to a jump is a jump to the end of the chain
A jump to a jump is a jump to the end of the chain: follow J0→J1→J2→J3 to the terminal, rewrite, drop the middlemen. That branch-chain elimination IS union-find's find (dart 048); full jump threading also threads determined conditionals. Peephole family (McKeeman 1965). Runs: target 3, 3 hops removed.
peephole / classical · 1965
⏨ DEMO
THE ACTIVATION RECORD
dart 165 · a function call is a frame; a tail call reuses it
A call is a stack frame (return addr, saved fp, locals at fixed offsets); a TAIL call reuses it instead of pushing. The object dart 155's 4096-frame wall is made of. Recursion + display: Dijkstra 1960 (the stack itself is older — Turing, Kellerprinzip). Runs: tail call reuses fp=1000 (no growth).
Dijkstra · 1960
⏨ DEMO
KAHAN SUMMATION
dart 166 · carry the bits that fell off the edge back into the sum
Carry the bits that fall off the float back into the sum. On an f64-only language it is the difference between a total and a lie. William Kahan, CACM 1965. Runs: naive 0 vs Kahan 2.22e-16 — the honest remainder recovered.
William Kahan · 1965
⏨ DEMO
HORNER'S METHOD
dart 167 · nest the polynomial; one multiply and add per term
Nest the polynomial — one multiply, one add per term, provably fewest. Qin Jiushao 1247, Newton ~1669, both before Horner 1819 (Stigler's law). Runs: p(3)=5 for 2x³-6x²+2x-1 in 3 mults.
Qin Jiushao · 1247
⏨ DEMO
GAUSSIAN ELIMINATION
dart 168 · eliminate downward, then substitute back up
Eliminate downward to a triangle, then substitute back up. In the Chinese Nine Chapters ~179 CE, ~1600 yrs before Gauss (1809). Runs: 2x+y=5, x+3y=10 → x=1, y=3.
Nine Chapters · ~179 CE
⏨ DEMO
SIMPSON'S RULE
dart 169 · fit a parabola through three points and integrate that
Fit a parabola through three points (weights 1:4:1) — exact for any cubic. Kepler 1615 (wine barrels), Newton before Simpson 1743. Runs: ∫x² on [0,2] → Simpson 2.6667 exact vs trapezoid 3.
Kepler · 1615
⏨ DEMO
BISECTION METHOD
dart 170 · bracket a sign change and halve until it is pinned
Bracket a sign change and halve — one binary digit per step, slow but it cannot fail. Rests on the intermediate value theorem (Bolzano 1817); the fallback in every hybrid solver. Runs: √2 = 1.41421356 in 40 halvings.
Bolzano (IVT) · 1817
⏨ DEMO
HALLEY'S METHOD
dart 171 · one order past Newton; triple the digits each step
Newton plus curvature: uses f'' to triple the correct digits each step (cubic). Edmond Halley 1694 — the comet astronomer. Runs: √2 to full f64 precision in 3 iterations (vs Newton's ~5).
Edmond Halley · 1694
⏨ DEMO
FIXED-POINT ITERATION
dart 172 · feed the output back in until it stops moving
Feed the output back in until it stops moving; it settles on the value that maps to itself. Banach's contraction theorem 1922; the skeleton of Newton, Halley, PageRank, and the corpus fold. Runs: x=1+1/x → φ = 1.6180339887, its own image.
Banach · 1922
⏨ DEMO
AITKEN'S DELTA-SQUARED
dart 173 · three slow terms predict where the sequence is heading
Three slow terms predict where the sequence is heading: x0 - (Δx)²/(Δ²x). Alexander Aitken 1926; wrapped on fixed-point it becomes Steffensen (derivative-free quadratic). Runs: raw 1.5 → accelerated 1.6667, closer to φ.
Alexander Aitken · 1926
⏨ DEMO
THE TURING MACHINE
dart 174 · a tape, a head, a table of rules; all of computation
A tape, a head, a rule table — and all of computation. Built to prove the halting problem undecidable, not to design a computer. Turing 1936 (Church coined the name). Runs: binary 1011 +1 → 1100 = 12 on a tape array.
Alan Turing · 1936
⏨ DEMO
PUSHDOWN AUTOMATON
dart 175 · a finite machine plus one stack; exactly the context-free
A finite machine plus one stack = exactly the context-free languages (a DFA cannot count brackets). Two stacks = Turing-complete. Oettinger 1961. Runs: (()()) → depth 0 ACCEPT, (() →1, )( →-1.
Oettinger · 1961
⏨ DEMO
GLUSHKOV CONSTRUCTION
dart 176 · number the letters; the follow relation is the automaton
Number the letters; first/last/follow sets ARE the ε-free NFA, one state per letter — a handful of bitmasks. Glushkov 1961 / McNaughton-Yamada 1960. Runs: (a|b)*abb on aabb, active 5→5→10→18 → accept 16.
Glushkov · 1961
⏨ DEMO
BRZOZOWSKI DERIVATIVE
dart 177 · the state is the rest of the pattern after a letter
The DFA state IS the rest of the pattern: d/dσ(r) = what remains after σ; accept if final is nullable. States = regexes, computed on demand. Brzozowski JACM 1964. Runs: a*b, aab nullable 1 accept, aa nullable 0.
Brzozowski · 1964
⏨ DEMO
HOPCROFT MINIMIZATION
dart 178 · merge states no string can tell apart
Merge states no string can tell apart, by partition refinement to a fixpoint. Hopcroft 1971 made it n log n (Moore 1956 was O(n²)); the minimal DFA is unique. Runs: 3 states → 2 (A~B merge).
Hopcroft · 1971
⏨ DEMO
KLEENE'S THEOREM
dart 179 · regex, NFA, DFA: three faces of one class
Regex = finite automaton = regular languages: three faces of one class. Introduced for McCulloch-Pitts nets, not grep. Kleene RAND 1951; names the star. Runs: a*b regex and DFA agree on 8/8 strings.
Stephen Kleene · 1951
⏨ DEMO
THE PUMPING LEMMA
dart 180 · long enough, and a regular language must repeat
Long enough, a regular language must loop — and the loop pumps. One un-pumpable string proves NOT regular (necessary, never sufficient). Regular case Rabin-Scott 1959; CF case Bar-Hillel 1961. Runs: pump aabb → aaabb, a=3≠b=2 — aⁿbⁿ not regular.
Rabin-Scott 1959 / BHPS 1961
⏨ DEMO
ARDEN'S RULE
dart 181 · solve the automaton's equations; the answer is a regex
Solve the automaton's equations: X = AX + B ⇒ X = A*B — the engine of state-elimination (automaton → regex). A* is the language-algebra's 1/(1-A). Arden 1961. Runs: X = aX + b → a*b, matches the machine 7/7.
Dean Arden · 1961
⏨ DEMO
FERMAT PRIMALITY TEST
dart 182 · if a^(p-1) is not 1, p is not prime; if it is, maybe
If a^(n-1) mod n is not 1, n is composite; if it is 1, only PROBABLY prime. Fermat 1640 (proof Euler 1736). Runs: 2^16 mod 17=1 (prime), 2^340 mod 341=1 (341=11x31 pseudoprime, fooled). ⚠ needs bitwise >> not float /.
Fermat · 1640
⏨ DEMO
WILSON'S THEOREM
dart 183 · (p-1)! is -1 mod p exactly when p is prime
(n-1)! ≡ -1 mod n iff n is prime — an exact characterisation (residues pair with their inverses; only -1 survives). Stated Wilson, proved Lagrange 1771; known to Alhazen ~1000. Runs: 6! mod 7=6(=-1, prime); 5! mod 6=0.
Lagrange · 1771
⏨ DEMO
CARMICHAEL FUNCTION
dart 184 · the true order, and the numbers that fool Fermat every time
λ(n) = the true group exponent; a Carmichael number is composite yet passes Fermat for EVERY base. Korselt 1899 (criterion) / Carmichael 1910 (561). Infinitely many (1994). Runs: 2^560, 5^560 mod 561 = 1; λ(561)=80.
Korselt/Carmichael · 1899/1910
⏨ DEMO
MONTGOMERY MULT
dart 186 · modular multiply with no division, only shifts
Modular multiply with NO division by n: move to R=2^k form, reduce with a mask and a shift. Montgomery, Math. Comp. 1985; under every fast RSA/ECC. Runs: REDC(3000) mod 97 = 78 via &127 and >>7.
Peter Montgomery · 1985
⏨ DEMO
BARRETT REDUCTION
dart 187 · replace the division by a multiply and a shift
x mod n = a multiply and a shift: precompute mu=floor(2^k/n), q=(x·mu)>>k, r=x-qn (off by ≤1). Barrett, CRYPTO 1986 — RSA on a divide-less DSP. Runs: 5000 mod 97 = 53, no division.
Paul Barrett · 1986
⏨ DEMO
THE FAREY SEQUENCE
dart 188 · every fraction to a bound, in order, by mediants
Every fraction ≤ n in [0,1], in order, by mediants — neighbours have bc-ad=1, no float sort. Haros 1802, not Farey 1816 (a Stigler-law misattribution). Shares the Stern-Brocot mediant structure. Runs: F_5 = 0/1,1/5,1/4,1/3,...
Haros · 1802
⏨ DEMO
THE PELL EQUATION
dart 189 · x-squared minus N y-squared equals one; solved by a square root's rhythm
x²-Ny²=1 solved by the continued fraction of √N. Brahmagupta 628 / Bhaskara chakravala 1150 — six centuries before Europe; 'Pell' is Euler's misattribution. Runs: 8²-7·3²=1, 3²-2·2²=1.
Brahmagupta · 628 (not Pell)
⏨ DEMO
THE FEISTEL NETWORK
dart 190 · split, mangle one half, swap; decryption is free
Split, mangle one half with F, swap — and decryption is the SAME network with keys reversed, even when F is NOT invertible (XOR carries it). DES/Blowfish. Horst Feistel, IBM 1973. Runs: 4660 → ct → 4660.
Horst Feistel · 1973
⏨ DEMO
THE S-BOX
dart 191 · the one nonlinear step; a lookup that hides the key
The one NONLINEAR step: a lookup table where S(a)⊕S(b)≠S(a⊕b) — Shannon's confusion, where security lives. AES S-box = Nyberg's GF(2^8) inverse (1993). Shannon 1949. Runs: S[3]=1, nonlinear bijection.
Shannon 1949 / Nyberg 1993
⏨ DEMO
SUBSTITUTION-PERMUTATION NET
dart 192 · substitute for confusion, permute for diffusion, repeat
XOR key → S-box (confusion) → bit-permute (diffusion), repeat — the AES skeleton, whole block per round. Shannon 1949 / Rijndael 2001. Runs: 202 → ct → 202 (invertible).
Shannon / Rijndael · 1949/2001
⏨ DEMO
LFSR
dart 193 · shift, XOR the taps in, and a long pseudorandom run falls out
Shift + XOR the taps; a primitive polynomial gives the maximal period 2^n-1. CRC's cousin (dart 075). Golomb 1967; but broken alone (Berlekamp-Massey, 2n bits). Runs: 8-bit period = 255.
Golomb · 1967
⏨ DEMO
THE AVALANCHE EFFECT
dart 194 · flip one input bit; half the output must change
Flip 1 input bit → ~HALF the output bits must flip (else the cipher peels apart). Measured as a Hamming distance. Feistel 1973 / SAC 1985. Runs: linear cipher = 1 bit (catastrophic), toward 8 with rounds.
Feistel · 1973
⏨ DEMO
BLOCK CIPHER MODES
dart 195 · a strong cipher, used wrong, leaks the picture
A strong cipher used in ECB leaks: identical blocks → identical ciphertext (the 'ECB penguin'); CBC/CTR chain them apart. Mode matters. FIPS 81 1980. Runs: ECB [41,41] leaks vs CBC [3,42].
FIPS 81 · 1980
⏨ DEMO
THE VERNAM CIPHER
dart 196 · XOR with a key; if the key is random and once, it is unbreakable
c = p⊕k, self-inverse; random+message-length+ONCE = the one-time pad, Shannon-perfect. Vernam 1917 (OTP earlier: Miller 1882). Runs: 200→101→200; reuse leaks p⊕p2 (key cancels).
Vernam · 1917
⏨ DEMO
THE KEY SCHEDULE
dart 197 · one master key becomes a different subkey per round
One master key → a distinct subkey per round (rotate + S-box + round constant). A weak schedule sinks a strong cipher (related-key, DES weak keys). Knudsen 1992 / Biham 1993. Runs: 178 → k1,k2,k3 = 100,202,145.
DES 1977 / Knudsen-Biham 1992-93
⏨ DEMO
THE MARKOV CHAIN
dart 198 · the next step forgets everything but now
A walk where the next state depends only on NOW, not the whole past — a transition matrix, and every start drifts to the same long-run law. Andrey Markov, 1906 (built to beat Nekrasov; fitted to Pushkin 1913). Runs: sunny 0.9 → 0.86 → 0.835.
Andrey Markov · 1906
⏨ DEMO
THE STATIONARY DISTRIBUTION
dart 199 · the eigenvector every start flows into
pi = piP, the Perron-Frobenius eigenvector every start flows into — found by pushing any vector through P until it stops moving. Perron 1907 / Frobenius 1912. Runs: converges to (5/6, 1/6), mass 1.0.
Perron-Frobenius · 1907/12
⏨ DEMO
THE DETAILED BALANCE
dart 200 · run it backwards and it looks the same
Reversibility: flux i→j equals flux j→i, edge by edge — stronger than stationarity, and the trick that lets MCMC target any pi. Boltzmann 1872 / Metropolis 1953. Runs: all fluxes balance, diff = 0.
Boltzmann · 1872
⏨ DEMO
THE PAGERANK
dart 201 · the web's dominant eigenvector, walked
A random surfer's stationary distribution: follow a link, or teleport with prob 1-d — teleport is what makes the answer unique. Brin-Page 1998 (eigenvector-centrality older: Seeley/Katz/Pinski-Narin). Runs: ranks to (0.215,0.397,0.388).
Brin & Page · 1998
⏨ DEMO
THE ABSORBING CHAIN
dart 202 · the fundamental matrix: how long till you're trapped
Fundamental matrix N=(I-Q)^-1: expected steps to get trapped, and the probability of which end — gambler's ruin, solved not simulated. Kemeny-Snell 1960 / de Moivre 1711. Runs: E[steps]=[3,4,3], P(win)=9/13.
Kemeny & Snell · 1960
⏨ DEMO
THE RANDOM WALK
dart 203 · Polya: lost in 1D and 2D, free in 3D
Polya's law: the fair ±1 walk is recurrent in 1D/2D (returns for sure) but transient in 3D (escapes, return prob ~0.34). Test: does Σ u_2n diverge? Pearson 1905 / Polya 1921. Runs: 1D sum 7→15→31 (diverges).
Pearson 1905 / Polya 1921
⏨ DEMO
THE MIXING TIME
dart 204 · how fast the chain forgets where it started
How fast the chain forgets its start: TV distance to pi decays by lambda2 (the 2nd eigenvalue) each step; the spectral gap is the clock. Aldous-Diaconis 1986 (7 shuffles). Runs: TV ratio = 0.4 = lambda2, exact.
Aldous & Diaconis · 1986
⏨ DEMO
THE HITTING TIME
dart 205 · Kac: the mean return time is one over its share
Kac's lemma: the mean time to RETURN to a state is exactly 1/pi — the rarer the state, the longer the wait, inversely and exactly. Kac 1947 (after Poincare 1890). Runs: return to 5/6-state = 1.2, to 1/6-state = 6.
Mark Kac · 1947
⏨ DEMO
THE DUAL NUMBER
dart 206 · differentiate a program for free, exactly
Adjoin eps with eps²=0: a value carrying a shadow. Evaluate f on x+1·eps and the shadow IS f′(x) - exact, no step size. Forward-mode automatic differentiation, one small duality. Clifford 1873 / Wengert 1964. Runs: f=[5, 10].
Clifford 1873 / Wengert 1964
⏨ DEMO
THE DE MORGAN DUALITY
dart 207 · AND and OR are one law seen through NOT
NOT(a AND b) = (NOT a) OR (NOT b): negation is a mirror swapping AND↔OR, so every Boolean law has a dual. Why NAND/NOR are universal. De Morgan 1847. Runs: both laws, difference 0.
De Morgan · 1847
⏨ DEMO
THE NEGAMAX
dart 208 · one player's max is the other's min, negated
Zero-sum makes the players duals: max(a,b) = -min(-a,-b), so one MAX rule (negated per ply) scores the whole tree. von Neumann 1928 / Knuth-Moore 1975. Runs: minimax tree = negamax tree = 3.
von Neumann 1928 / Knuth-Moore 1975
⏨ DEMO
THE ADJOINT
dart 209 · move the matrix to the other side of the inner product
⟨Ax,y⟩ = ⟨x,Aᵀy⟩: slide the matrix across the inner product; in finite dim the adjoint IS the transpose. Backprop is this, run backwards. Hilbert/Riesz. Runs: both sides = 431.
Hilbert / Riesz
⏨ DEMO
THE DUAL BASIS
dart 210 · every basis has a shadow that reads off coordinates
Every basis has a dual defined by ⟨eⁱ,eⱼ⟩=δ - the rows of the inverse, the reciprocal lattice; then coordinate i = ⟨eⁱ,v⟩. Gibbs / dual space. Runs: biorthogonal to f64 (off-diag ~1e-16).
Gibbs / dual space
⏨ DEMO
THE POINT-LINE DUALITY
dart 211 · a point is a line is a point
A point (a,b,c) and a line ax+by+cz=0 are the same triple; collinear points ↔ concurrent lines, proved by the SAME determinant. Poncelet 1822 / Gergonne 1826. Runs: collinear det = concurrent det = 0.
Poncelet 1822 / Gergonne 1826
⏨ DEMO
THE GALOIS CONNECTION
dart 212 · two worlds, each the order-reversed mirror of the other
F(a)≤b ⇔ a≤G(b): two ordered worlds locked by one bar - the most general duality, an adjunction on posets. Here square & isqrt. Galois 1832 / Ore 1944. Runs: n²≤m ⇔ n≤⌊√m⌋, agrees.
Galois 1832 / Ore 1944
⏨ DEMO
THE TWO'S COMPLEMENT
dart 213 · negation is flip-and-add-one; sign is a point of view
-x = ~x+1: the same bits are an unsigned AND a signed number, the line bent into a ring - so one adder does add and subtract. method of complements / EDVAC 1945. Runs: -5 = 251 = 256-5, signed -5.
method of complements / EDVAC 1945
⏨ DEMO
THE LAMPORT CLOCK
dart 214 · order without a clock
Order events across machines with no shared clock: a counter per node, and on receive LC=max(local,msg)+1, so a→b implies LC(a)<LC(b). Lamport 1978 (the field's most-cited paper). Runs: receive stamps 3 > send 2.
Leslie Lamport · 1978
⏨ DEMO
THE RAFT CONSENSUS
dart 215 · consensus you can actually understand
Agree on a replicated log via one leader per term; a majority (floor(N/2)+1) elects and commits, and any two majorities overlap → no split brain. Ongaro-Ousterhout 2014 (understandable Paxos). Runs: N=5, majority 3.
Ongaro & Ousterhout · 2014
⏨ DEMO
THE LEADER ELECTION
dart 216 · the highest id wins the ring
Pick one coordinator from symmetric peers: forward the running max around a ring, the maximum returns to itself and wins. LeLann 1977 / Chang-Roberts 1979. Runs: [3,17,9,42,8] → leader 42.
Chang & Roberts · 1979
⏨ DEMO
THE GOSSIP PROTOCOL
dart 217 · rumor reaches everyone in log(n) rounds
Spread an update like a rumor: each round the informed count doubles, so all n nodes learn in ceil(log2 n) rounds, robust to loss, no coordinator. Demers/PARC 1987 (epidemic algorithms). Runs: 1000 nodes in 10 rounds.
Demers et al. · 1987
⏨ DEMO
THE CRDT
dart 218 · agree without ever coordinating
Replicas take writes independently and converge with NO consensus round, because the merge is a semilattice join (commutative+associative+idempotent). Shapiro et al. 2011; the mechanism under DACI. Runs: merge diff 0, converges to 8.
Shapiro et al. · 2011
⏨ DEMO
CHANDY-LAMPORT SNAPSHOT
dart 219 · photograph a running system without stopping it
Photograph a running distributed system: markers cut the channels into a consistent cut; node states + recorded in-flight conserve every global invariant. Chandy-Lamport 1985 (Flink's exactly-once). Runs: snapshot = 10, conserved.
Chandy & Lamport · 1985
⏨ DEMO
THE TWO GENERALS
dart 220 · no message is ever the last
Guaranteed agreement over a lossy channel is IMPOSSIBLE: the last message is never acknowledged, forever — certainty = common knowledge = an infinite tower. Akkoyunlu 1975 / Gray 1978. Runs: everBoth 0, one dangling msg.
Akkoyunlu 1975 / Gray 1978
⏨ DEMO
THE ATOMIC BROADCAST
dart 221 · everyone hears the same story in the same order
Every node delivers the same messages in the same order despite scrambled arrival — sort by sequence. Equivalent to consensus, so it IS the replicated state machine. Chandra-Toueg 1996. Runs: [3,1,2] & [1,2,3] → both 1,2,3.
Chandra & Toueg · 1996
⏨ DEMO
THE QUICKCHECK
dart 222 · don't check examples, check the law — then hunt its counterexample
State a PROPERTY (for all x: P(x)) and let the machine hunt a counterexample — Popper in a test harness; passing is never proof, only not-yet-refuted. Claessen-Hughes 2000. Runs: n²<100 falsified at n=10.
Claessen & Hughes · 2000
⏨ DEMO
THE SHRINKING
dart 223 · a huge failing input is a bad bug report; shrink it to the atom
A huge failing input is a bad bug report; reduce it while it still fails to the MINIMAL counterexample — the bug with all coincidence removed. Hildebrandt-Zeller ddmin 2000. Runs: 1000 shrinks to 42.
Hildebrandt & Zeller · 2000
⏨ DEMO
THE METAMORPHIC TEST
dart 224 · you can test what you cannot compute the answer to
Test what you can't compute the answer to: check a RELATION between runs (sum is permutation-invariant), no oracle needed. Chen-Cheung-Yiu 1998. Runs: good diff 0, weighted 'sum' diff -2 (bug caught).
Chen, Cheung & Yiu · 1998
⏨ DEMO
THE DIFFERENTIAL TEST
dart 225 · two things that should agree, and the input where they don't
Two impls that should agree, and the input where they don't — the disagreement is the bug, no oracle. How compilers are tested. McKeeman 1998 / Csmith. Runs: diverge at n=7.
McKeeman · 1998
⏨ DEMO
THE FUZZER
dart 226 · throw noise at it until it screams
Throw random/malformed inputs until the program crashes or trips an assertion — no theory of the code, just relentless knocking. Miller 1990 / AFL. Runs: crashing input x=7 (hidden guard root).
Barton Miller · 1990
⏨ DEMO
THE MODEL CHECKER
dart 227 · explore every reachable state, and hand back the trace that breaks the rule
Explore EVERY reachable state; a reachable bad state comes back as a concrete counterexample trace. Exhaustive, not sampled. Clarke-Emerson / Queille-Sifakis 1981 (Turing 2007). Runs: bad reachable via 0→1→2→3.
Clarke-Emerson / Queille-Sifakis · 1981
⏨ DEMO
THE SYMBOLIC EXECUTION
dart 228 · run the program on an unknown, and solve for the input that reaches the bug
Run on a SYMBOL not a number; accumulate the path condition to a target and SOLVE it for the reaching input — solve, don't guess. King 1976 / KLEE. Runs: x>5∧x<10∧even → x=6.
James C. King · 1976
⏨ DEMO
THE MUTATION TESTING
dart 229 · who tests the tests? break the code on purpose and see if they notice
Who tests the tests? Inject faults (+ → -); a good test KILLS the mutant, a survivor exposes a toothless test. DeMillo-Lipton-Sayward 1978. Runs: strong kills 3/3, weak 2/3 (mul survives).
DeMillo, Lipton & Sayward · 1978
⏨ DEMO
THE BASIC BLOCK
dart 230 · a straight run of code: one way in, one way out
A compiler cuts your code into basic blocks — maximal straight-line runs, one entry, one exit — the atom every later pass reasons over. Allen 1970. i13's region IS this: check reports 2.
Frances E. Allen · 1970
⏨ DEMO
THE CONTROL FLOW GRAPH
dart 231 · blocks are nodes, jumps are edges — the shape of all paths
Blocks are nodes, jumps are edges. Cyclomatic complexity M = E−N+2 counts independent paths. Allen 1970 / McCabe 1976. i13 has no loops → every CFG a DAG; diamond M=2.
Allen · McCabe
⏨ DEMO
THE DEF-USE CHAIN
dart 232 · every value: where it is born, everywhere it is read
Link each value's definition to every read. Single-assignment makes the chains exact — near-SSA. Allen & Cocke. i13's write-once bindings give it free: v1 used 3x.
Allen & Cocke · 1970s
⏨ DEMO
THE REACHING DEFINITIONS
dart 233 · which assignment's value is still live here?
Which assignment's value survives to here? The archetypal dataflow fixpoint, OUT = gen ∪ (IN−kill). Kildall 1973. i13 runs a one-bit version for return-totality. Reach = 6.
Gary Kildall · 1973
⏨ DEMO
THE AVAILABLE EXPRESSIONS
dart 234 · already computed on every path — do not compute twice
Already computed on every path? Then reuse it. Forward must-analysis, joined by intersection. Cocke/Kildall. The enabler of CSE. Available = 3.
Cocke · Kildall
⏨ DEMO
THE COMMON SUBEXPRESSION ELIMINATION
dart 235 · compute (a+b) once, reuse it — when it is safe
Compute a+b once, reuse it. Cocke 1970. i13 refuses it on purpose — the ops that run are the ops you wrote. 3 uses → 2 evals saved.
John Cocke · 1970
⏨ DEMO
THE PEEPHOLE OPTIMIZATION
dart 236 · tiny local rewrites through a sliding window
A sliding window of tiny safe rewrites: x*1→x, kill the dead op. McKeeman 1965. The one pass in i13's grain — the panel already removed dead Op::Attr. Removed 4.
William McKeeman · 1965
⏨ DEMO
THE LOOP-INVARIANT CODE MOTION
dart 237 · hoist what does not change out of the loop
Hoist what does not change out of the loop — save n−1 recomputes. Allen & Cocke 1971. i13 has no loops: the invariant is a threaded recursion arg. Saved 999.
Allen & Cocke · 1971
⏨ DEMO
THE INDUCTION VARIABLE
dart 238 · i, i+c, i+2c... replace the pattern with its closed form
i, i+c, i+2c... recognize the recurrence, use the closed form i₀+k·c. Allen 1969. i13 has no loops; the counter is an explicit recursion arg. 26 = 26.
Allen-Cocke-Kennedy
⏨ DEMO
THE SCALAR REPLACEMENT
dart 239 · a hot array cell becomes a plain scalar
A hot array cell → a plain scalar: one load, not many. Callahan-Carr-Kennedy 1990. i13's value semantics make it safe and idiomatic. Loads saved: 2.
Callahan, Carr & Kennedy · 1990
⏨ DEMO
THE INLINING
dart 240 · paste the callee in; delete the call
Paste the callee in; delete the call — and let other passes see across it. Scheifler 1977. In i13 it cuts call depth but hides a frame the spot-log witnesses. f(6)=37, depth 1→0.
Robert Scheifler · 1977
⏨ DEMO
THE BOUNDS-CHECK ELIMINATION
dart 241 · drop the check the proof already made
Drop the check only where the index is proven in range — safety AND speed. Gupta 1993. THE pass in i13's grain: it already checks (E0501) and proves. Removable: 4/5.
Markstein-Cocke · Gupta
⏨ DEMO
THE ESCAPE ANALYSIS
dart 242 · if it cannot outlive its scope, it need never touch the heap
If an object cannot outlive its scope, stack it — skip the heap. Choi et al. 1999. i13 gets it FREE: value semantics, no aliasing → nothing escapes. Escapes = 0.
Park-Goldberg · Choi et al.
⏨ DEMO
THE INTERFERENCE GRAPH
dart 243 · two values alive at once cannot share a register — color the graph
Variables live at once can't share a register — color the graph. Chaitin 1981 on Kempe 1879. N/A for i13: a stack IVM has no registers. K3 needs 3.
Gregory Chaitin · 1981
⏨ DEMO
THE BRANCH PREDICTION
dart 244 · guess the branch before you know it — and pay when wrong
Guess the branch, pay on a miss: the 2-bit saturating counter. Smith 1981. The foil to i13's creed — ARRIVAL ≠ EXECUTION, it never speculates. Misses: 5.
James E. Smith · 1981
⏨ DEMO
THE SEA OF NODES
dart 245 · data and control, one graph, no schedule until the end
Data + control in one floating graph; schedule last, so CSE is a fact not a pass. Click & Paleczny 1995. i13 fixes the schedule to verify it — opposite choice. Sea 5 vs IVM 8.
Click & Paleczny · 1995
⏨ DEMO
THE ALGEBRAIC DATA TYPE
dart 246 · types you add and multiply — and match to take apart
Types you add (sum/choice) and multiply (product/pair), matched exhaustively. HOPE 1980 (to ML via Standard ML). i13 encodes them as [tag,payload] but forgoes the exhaustiveness check. Some-sum = 60.
HOPE · 1980
⏨ DEMO
THE PARAMETRIC POLYMORPHISM
dart 247 · one function, every type — and the type tells you what it can't do
One function, every type — and the type forces theorems for free (map preserves length). Strachey / Reynolds / Wadler. i13 is parametric by having ONE type. len = 4.
Strachey · Wadler 1989
⏨ DEMO
THE SYSTEM F
dart 248 · abstract over types, not just values — polymorphism as a calculus
Abstract over TYPES, not just values — Church-encode all data. Girard 1972 / Reynolds 1974, found twice. i13 runs the value half (church3=3), skips ฮ›.
Girard · Reynolds
⏨ DEMO
THE SUBTYPING
dart 249 · if A can stand in for B everywhere, A is a subtype of B
A <: B if A stands in for B everywhere. Width subtyping: {x,y,z}<:{x,y}. Cardelli / Liskov-Wing. N/A for i13 (one type). 7<:3 = 1, 3<:7 = 0.
Cardelli · Liskov-Wing
⏨ DEMO
THE TYPECLASS
dart 250 · ad-hoc polymorphism made principled — carry the operations with the type
Ad-hoc polymorphism made principled: a constraint compiles to a hidden dictionary. Wadler-Blott 1989. i13 can pass a dict by hand, not infer it. eq(5,5)=1.
Wadler & Blott · 1989
⏨ DEMO
THE DEPENDENT TYPE
dart 251 · a type that depends on a value — the length lives in the type
A type that mentions a value: Vec 3 ++ Vec 2 : Vec 5. Martin-Lรถf. The ceiling i13 forgoes — its runtime bounds-check (E0501) is the weak cousin.
Martin-Lรถf · 1972
⏨ DEMO
THE LINEAR TYPE
dart 252 · use it exactly once — the type tracks the resource
Use it EXACTLY once — the type tracks the resource (no double-free). Girard 1987 / Wadler 1990; Rust = affine. i13 has the no-aliasing payoff free. uses=1 OK.
Girard · Wadler
⏨ DEMO
THE REFINEMENT TYPE
dart 253 · a type plus a predicate: {x : Int | x > 0}
A type + a predicate: {x | x>0}, discharged by the checker/SMT. Freeman-Pfenning 1991. The pass i13 could most plausibly adopt. inhabitants = 3.
Freeman-Pfenning · Liquid
⏨ DEMO
THE EFFECT SYSTEM
dart 254 · the type says not just what it returns, but what it disturbs
The type says what it DISTURBS, not just returns; effects union, empty = pure. Gifford-Lucassen 1986. i13 is pure by construction: effect {}. rw=3.
Gifford & Lucassen · 1986
⏨ DEMO
THE BIDIRECTIONAL TYPING
dart 255 · two modes: check against a known type, or synthesize an unknown one
Two modes: CHECK against a known type, SYNTHESIZE an unknown one. Pierce-Turner 1998/2000 named it (older folklore). The algorithm i13 would use if it grew types. (f x):Bool=2.
folklore · Pierce-Turner
⏨ DEMO
THE EXISTENTIAL TYPE
dart 256 · abstract types have existential type — hide the representation, keep the interface
Hide the representation, expose the interface: abstract types have existential type. Mitchell-Plotkin 1988. i13 gets the runtime, not the guarantee. op(6)=36.
Mitchell & Plotkin · 1988
⏨ DEMO
THE ROW POLYMORPHISM
dart 257 · work on any record that has these fields — and whatever else
Work on any record with these fields, and whatever else — flexibility WITH full inference. Wand 1987 / Rรฉmy. i13 has records-as-arrays, no row variable. get c = 30.
Wand · Rรฉmy
⏨ DEMO
THE HIGHER-KINDED TYPE
dart 258 · types have types — and they are called kinds
Types have types — kinds. List : *โ†’*, Pair : *โ†’*โ†’*. Girard Fฯ‰. Two floors above i13 (which has no types at all). Pair arity = 2.
Girard Fฯ‰ · Haskell
⏨ DEMO
THE PROGRESS AND PRESERVATION
dart 259 · well-typed programs do not go wrong — the two lemmas that prove it
Well-typed programs don't go wrong: never stuck (progress) + type kept per step (preservation). Milner 1978 / Wright-Felleisen 1994. i13's ledger IS this, minus types. Int→6.
Milner · Wright-Felleisen
⏨ DEMO
THE PHANTOM TYPE
dart 260 · a type parameter with no runtime value — a tag the compiler enforces, then erases
A type-only tag: Length<Meters> โ‰  Length<Feet>, same runtime, forbids mixing. Leijen-Meijer / Cheney-Hinze. Proof the safety i13 forgoes costs nothing to RUN. diff=0.
Leijen · Cheney-Hinze
⏨ DEMO
THE LAMBDA CUBE
dart 261 · three axes of abstraction — eight typed lambda calculi, one corner is the summit
3 axes (poly / type-operators / dependency) โ†’ 2ยณ = 8 typed calculi; the summit is the Calculus of Constructions. Barendregt 1991. i13 sits one step BELOW the origin: untyped.
Barendregt · 1991
⏨ DEMO
THE STACK MACHINE
dart 262 · no registers, one stack — push operands, an operator eats the top
No registers, one stack: push operands, an operator eats the top. Bauer-Samelson / Hamblin 1957. i13's IVM literally IS one (peak stack reported per run). 2 3 + 4 * = 20.
Bauer-Samelson · Hamblin
⏨ DEMO
THE REGISTER MACHINE
dart 263 · named cells instead of a stack — fewer instructions, harder to generate
Named cells not a stack: fewer instructions, but needs register allocation. Shepherdson-Sturgis 1963; Lua 5 VM. i13 is a stack machine by choice. = 20, 2 regs.
Shepherdson-Sturgis · 1963
⏨ DEMO
THE BYTECODE
dart 264 · compile once to a compact instruction set, interpret anywhere
Compile once to a compact opcode set, interpret anywhere. O-code 1969 / p-code 1975. i13 already IS a bytecode VM (its IVM, ~19 ops, 8.5KB WASM). (5-3)*2 = 4.
O-code · p-code
⏨ DEMO
THE THREE-ADDRESS CODE
dart 265 · one operator, three operands, a fresh temporary per step
x = y op z, a fresh temp per step — the classic IR the optimizer walks. Dragon Book lineage. i13's IVM stream is TAC-shaped. (2+3)*4, 2 temps.
Dragon Book lineage
⏨ DEMO
THE A-NORMAL FORM
dart 266 · name every intermediate result — the functional IR
Let-bind every intermediate, trivial arguments — CPS's benefit in direct style. Flanagan et al. 1993. i13's syntax IS essentially ANF (near-SSA). 2 lets.
Flanagan et al. · 1993
⏨ DEMO
THE CEK MACHINE
dart 267 · three registers — Control, Environment, Kontinuation — and no call stack
Control, Environment, Kontinuation — the call stack becomes a first-class value. Felleisen-Friedman 1986. i13 keeps control implicit (E0503, no call/cc). (ฮปx.x+x)5=10.
Felleisen-Friedman · 1986
⏨ DEMO
THE CESK MACHINE
dart 268 · add a Store — now the machine has addresses, and mutation, and abstraction
CEK + a Store of addresses: mutation, and (bounded) static analysis. Van Horn-Might 2010. i13 has NO store → value-semantics, no aliasing. cell=8.
Felleisen-Friedman · Van Horn-Might
⏨ DEMO
THE CATEGORICAL ABSTRACT MACHINE
dart 269 · compile the lambda calculus to categorical combinators — and Caml is born
Compile ฮป to categorical combinators — and the first Caml is born. Cousineau-Curien-Mauny 1987. i13 also runs names-compiled-away. (id;+3)5=8.
Cousineau-Curien-Mauny · 1987
⏨ DEMO
THE ZINC MACHINE
dart 270 · push the arguments, then the function — curried calls with no wasted closures
Push all args, apply once — curried calls with no wasted closures. Leroy 1990 (OCaml's runtime). i13 has no currying/closures → free. add(2,3)*4=20.
Xavier Leroy · 1990
⏨ DEMO
THE SPINELESS TAGLESS G-MACHINE
dart 271 · lazy evaluation on stock hardware — a thunk that updates itself when forced
Lazy on stock hardware: a thunk forced once, then overwrites itself. Peyton Jones 1992 (GHC). i13 is STRICT → at-most-once for free. thunk=36, 1 force.
Peyton Jones · 1992
⏨ DEMO
THE CLOSURE CONVERSION
dart 272 · a function that remembers — code plus a captured environment, made explicit
A closure = code + captured env, made explicit; afterward every function is closed. Landin 1964 / Reynolds 1972. i13 starts here (no closures). addN(10,5)=15.
Landin · Reynolds
⏨ DEMO
THE SUPERCOMBINATOR
dart 273 · lift every lambda to the top level — no nesting, no capture, just named functions
Lambda-lift every function to a closed top-level combinator — no nesting, no capture. Hughes 1982. EVERY i13 function IS a supercombinator. SC(7,4)=11.
John Hughes · 1982
⏨ DEMO
THE WARREN ABSTRACT MACHINE
dart 274 · Prolog on a machine — unification and backtracking as instructions
Prolog on a machine: unification + backtracking as instructions. Warren 1983. The farthest machine from i13 (search vs a straight-through proof). unify → X=3,Y=2.
David H. D. Warren · 1983
⏨ DEMO
THE TRAMPOLINE
dart 275 · bounce tail calls back to a top loop — constant stack, no matter how deep
Bounce tail calls back to a top loop — constant stack, any depth. Ganz-Friedman-Wand 1999. โš‘ The one REAL i13 frontier: TCO past E0503's 4096 frames. 1..100=5050, depth 101.
Ganz-Friedman-Wand · 1999
⏨ DEMO
THE NORMALIZATION BY EVALUATION
dart 276 · to simplify a term, run it — then read the answer back as syntax
To simplify a term, RUN it, then read the value back as syntax (reflect/reify). Berger-Schwichtenberg 1991. Kin to i13's semantic-hash JIT. (ฮปx.x)9 → 9.
Berger-Schwichtenberg · 1991
⏨ DEMO
THE EXPLICIT SUBSTITUTION
dart 277 · substitution is not an atom — make it a first-class, step-by-step operation
Substitution isn't an atom — make it first-class, delayed, step-by-step (ฮปฯƒ). Abadi-Cardelli-Curien-Lรฉvy 1990. i13 does it as a lookup (an environment). [x:=5]x+3=8.
Abadi-Cardelli-Curien-Lรฉvy · 1990
⏨ DEMO
THE CROSS-RATIO
dart 278 · the one number a projective transformation cannot change
The ONE number a projective (Mobius) transformation cannot change — four points, ((C-A)(D-B))/((C-B)(D-A)). Pappus / Mobius / Chasles. โš‘ keeper shot: invariance ENACTED. 4/3 before AND after, diff 2e-16.
Pappus · Mobius · Chasles
⏨ DEMO
THE DETERMINANT
dart 279 · signed volume — and what a shear is forbidden to change
Signed volume — unchanged by a shear (row-add) and by change of basis. Seki 1683 / Leibniz 1693 / Cauchy 1812. i13 computes it exact: det 5 before AND after the shear, diff 0.
Seki · Leibniz · Cauchy
⏨ DEMO
THE CONIC INVARIANT
dart 280 · rotate the axes all you like — ellipse stays ellipse
B^2-4AC: rotate the axes all you like, its sign classifies the curve for good. Boole-Cayley-Sylvester 1840s (invariant theory). ellipse disc -8 before AND after 90-degree rotation.
Cayley-Sylvester
⏨ DEMO
THE GAUSS-BONNET
dart 281 · bend the surface however you like — the total curvature is fixed by its topology
Total curvature = 2πχ: bend the surface, the sum is fixed by topology. Gauss 1827 / Bonnet 1848. A cube's 8 angle defects sum to 4π → χ = 2.
Gauss · Bonnet
⏨ DEMO
THE GENUS
dart 282 · count the holes — the number no stretching can change
Count the holes — the number no stretching can change. Riemann 1857; χ=2-2g. Torus χ=0 → genus 1. A mug and a donut are one.
Riemann · 1857
⏨ DEMO
THE DEGREE OF A MAP
dart 283 · how many times the map wraps the circle around itself — an integer that cannot jump
How many times z→zⁿ wraps the circle — an integer that cannot jump. Brouwer 1911. z→z^2 has degree 2; homotopy-invariant, the root of fixed-point theorems.
Brouwer · 1911
⏨ DEMO
THE POINCARE-HOPF
dart 284 · the zeros of any vector field on a surface must add up to its Euler characteristic
A vector field's zeros must sum to χ — why you can't comb a hairy ball. Poincare 1885 / Hopf 1926. Two sources on a sphere: index sum 2 = χ.
Poincare · Hopf
⏨ DEMO
THE ARGUMENT PRINCIPLE
dart 285 · walk a loop, count how the output spins — that integer is how many roots you enclosed
Walk a loop, count how the output spins — that winding IS the number of roots enclosed. Cauchy 1831. z^2-1 inside radius 5: winding = 2 zeros.
Cauchy · 1831
⏨ DEMO
THE ROTATION NUMBER
dart 286 · the average turn per step of a circle map — unchanged by any smooth re-coordinate
Average turn per step of a circle map — same from any start, any coordinate. Poincare 1885. Rotation by 1/3 closes after 3 steps → 1/3.
Poincare · 1885
⏨ DEMO
THE WRITHE
dart 287 · a signed crossing count — the coiling a knot carries with it
Signed crossing count; via Lk = Tw + Wr, twist trades into writhe but the total is fixed. Calugareanu-White-Fuller. A trefoil: writhe 3. (DNA supercoiling.)
Calugareanu-White-Fuller
⏨ DEMO
THE HOLONOMY
dart 288 · carry an arrow around a loop and it comes back rotated — by the area you enclosed
Carry an arrow around a loop, it returns rotated by the enclosed AREA. Levi-Civita 1917 (excess: Harriot 1603). Spherical right-triangle: holonomy π/2. (Foucault, Berry phase.)
Levi-Civita · 1917
⏨ DEMO
THE ORBIT-STABILIZER
dart 289 · orbit size times stabilizer size equals the group — symmetry, counted
|orbit| × |stabilizer| = |G| — symmetry, counted. Lagrange (cosets). A square corner: 4 × 2 = 8 = |D4|.
Lagrange lineage
⏨ DEMO
THE BURNSIDE LEMMA
dart 290 · count distinct objects up to symmetry — average what each symmetry leaves fixed
Count distinct objects up to symmetry: average what each symmetry fixes. โš‘ credit: it's Cauchy-Frobenius, NOT Burnside. 4-bead 2-color necklaces = (16+2+4+2)/4 = 6.
Cauchy 1845 · Frobenius 1887
⏨ DEMO
THE NOETHER THEOREM
dart 291 · every continuous symmetry of the laws gives a conserved quantity — the deepest why
Every continuous symmetry of the laws gives a conserved quantity — the deepest WHY. Emmy Noether 1918. Space symmetry → momentum: total 8 before AND after. Invariance IS conservation.
Emmy Noether · 1918
⏨ DEMO
THE LIOUVILLE THEOREM
dart 292 · a cloud of states flows through phase space without ever changing its volume
A cloud of states flows through phase space without changing its VOLUME (Jacobian 1). Liouville 1838. Why Verlet (B16 keeper) is trustworthy: symplectic. area 6 → 6.
Joseph Liouville · 1838
⏨ DEMO
THE FIRST INTEGRAL
dart 293 · a quantity the motion carries unchanged — energy along the orbit
A quantity the motion carries unchanged — energy along the orbit. Euler / Jacobi. Harmonic oscillator (3,4)→(4,-3): energy x^2+p^2 = 25, unchanged. Noether's quantity, watched.
Euler · Jacobi
⏨ DEMO
THE VANDERMONDE MATRIX
dart 294 · the determinant that decides whether reconstruction is even possible
The determinant det=∏(xj-xi) that decides if reconstruction is even POSSIBLE: ≠0 iff nodes distinct iff the interpolant EXISTS & is unique. โš‘ keeper shot: the structure CAUSES recovery. distinct 6 vs collided 0. Vandermonde (a misnomer).
Vandermonde · 1770s
⏨ DEMO
THE NEWTON DIVIDED DIFFERENCES
dart 295 · reconstruct the polynomial one point at a time — add a sample, extend the fit
Reconstruct the polynomial one point at a time; divided differences = slopes of slopes. Newton 1670s. Unique because Vandermonde≠0. p(3)=19 from (0,1)(1,3)(2,9).
Isaac Newton · 1670s
⏨ DEMO
THE NEVILLE ALGORITHM
dart 296 · reconstruct the value, not the polynomial — a tableau of blended estimates
Reconstruct the VALUE (not the poly) by a tableau of blended estimates. Neville 1934. 7,15 → 19 — same as Newton, no coefficients formed.
E. H. Neville · 1934
⏨ DEMO
THE BARYCENTRIC INTERPOLATION
dart 297 · the fast, stable form — precompute the weights, reconstruct in one pass
The fast, stable Lagrange form: precompute weights, reconstruct in one quotient. Berrut-Trefethen 2004. weights 0.5,-1,0.5 → 19 (= Newton = Neville).
Berrut-Trefethen · 2004
⏨ DEMO
THE ERASURE CODE
dart 298 · lose some packets, recover them from the rest — because the data is low-degree
Lose packets, recover from the rest — because the data is a low-degree poly (any k of n reconstruct). Reed-Solomon 1960. erased middle recovered = 3. (RAID, CDs, QR.)
Reed-Solomon · 1960
⏨ DEMO
THE SYNDROME DECODING
dart 299 · the syndrome depends only on the error — so it names where the error is
The syndrome depends ONLY on the error, so it names its position. Hamming 1950. flip bit 5 → syndrome 101₂ = 5, no codebook searched.
Hamming · Slepian
⏨ DEMO
THE ERROR LOCATOR
dart 300 · a polynomial whose roots are exactly the positions that went wrong
A polynomial whose ROOTS are the error positions; a Chien search finds them. Peterson 1960 / Chien 1964. σ=x²-5x+6 → errors at {2,3}. (RS/BCH core.)
Peterson-Chien
⏨ DEMO
THE FOUNTAIN CODE
dart 301 · catch any drops from an endless spray — enough of them rebuild the file
Rateless: spray XOR droplets endlessly, catch any k+ and peel back the file. Luby 2002 (LT codes). lost s3 peeled from s1⊕s3 = 6. (RaptorQ.)
Byers-Luby · 2002
⏨ DEMO
THE NYQUIST-SHANNON
dart 302 · sample fast enough and the continuous signal is perfectly recoverable from its dots
Sample above 2×bandwidth and the continuous signal is EXACTLY recoverable; below → aliasing. Whittaker/Nyquist/Kotelnikov/Shannon. 7Hz at fs=10 aliases to 3Hz.
Nyquist-Shannon
⏨ DEMO
THE COMPRESSED SENSING
dart 303 · recover a big sparse signal from far fewer measurements than its length
Recover a big SPARSE signal from far fewer measurements than its length (L1 min). Candes-Tao / Donoho 2006. 1-sparse from 2 measurements: value 7 @ pos 3. (fast MRI.)
Candes-Tao / Donoho
⏨ DEMO
THE PSEUDOINVERSE
dart 304 · the best answer when there is no exact one — invert the un-invertible
Invert the un-invertible: least-squares if overdetermined, min-norm if under. Moore 1920 / Penrose 1955. 3 readings 1,2,3 → best estimate 2 (the mean).
Moore-Penrose
⏨ DEMO
THE NORMAL EQUATIONS
dart 305 · the residual is smallest when it is orthogonal to the fit
Best fit = residual ⊥ the model: AᵀAx=Aᵀb. Gauss 1795 / Legendre 1805. (1,2)(2,4)(3,5) → slope 25/14 ≈ 1.786.
Gauss-Legendre
⏨ DEMO
THE KALMAN FILTER
dart 306 · reconstruct the true state from a stream of noisy guesses — predict, then correct
Reconstruct the true state from noisy guesses: predict, then correct by a certainty-weighted gain. Kalman 1960 (flew Apollo). prior 5 + measure 6 → 5.5, variance 2→1.
Rudolf Kalman · 1960
⏨ DEMO
THE WIENER FILTER
dart 307 · the optimal blend of signal and noise — recover the clean part in the mean-square sense
Optimal denoiser: weight each part by S/(S+N). Wiener 1949 / Kolmogorov 1941. S=4,N=1 → gain 0.8, observed 5 denoises to 4 (mean-square optimal).
Wiener-Kolmogorov
⏨ DEMO
THE AITKEN EXTRAPOLATION
dart 308 · reconstruct the limit a slow sequence is crawling toward — from three terms
Reconstruct the limit a slow sequence crawls toward, from 3 terms (assumes geometric tail). Aitken 1926. 1,0.5,0.25 → limit 0, at once.
Alexander Aitken · 1926
⏨ DEMO
THE PADE APPROXIMANT
dart 309 · reconstruct a whole function — poles and all — from a few terms of its series
Reconstruct a whole function — poles and all — from a few series terms, as P(x)/Q(x). Pade 1892. [1/1] of 1+x+x²+... = 1/(1-x); at 0.5 → 2.
Henri Pade · 1892
⏨ DEMO
THE ONLINE MEAN
dart 310 · the average, updated one sample at a time — never store the data
The average updated one sample at a time — m += (x-m)/n, never store the data. Welford 1962 / Knuth. streams [4,8,6,2] -> mean 5, one running number.
the online mean · 1962
⏨ DEMO
THE WELFORD VARIANCE
dart 311 · variance in one pass, carrying two numbers — the batch form carries them all
Variance in ONE pass carrying just [mean, M2] — stable, no giant cancellation. โš‘ keeper shot: a correct batch stores all n; a correct naive one-pass loses precision. Welford 1962. -> variance 4.
B. P. Welford · 1962
⏨ DEMO
THE EXPONENTIAL MOVING AVERAGE
dart 312 · one number that remembers everything and stores nothing — the past decays
One register that weights ALL of history, most-recent-heaviest: e += a(x-e). Brown/Holt 1950s. [10,20,30] a=1/2 -> 22.5; infinite fading memory, stores one.
exp. smoothing · 1950s
⏨ DEMO
THE SIMPLE MOVING AVERAGE
dart 313 · the last k, averaged — a bounded window that slides
The last k, averaged — a fixed window that slides, memory exactly k. the boxcar filter. last-3 of [1,2,3,4,5] -> 4; add entrant, drop leaver, O(1)/step.
the boxcar / rolling mean
⏨ DEMO
THE MONOTONIC QUEUE
dart 314 · a deque that evicts the dominated — each element enters and leaves once
A deque that evicts the dominated — each element in once, out once, window-max in O(n) not O(nk). โš‘ sharpest near-miss. [1,3,-1,-3,5,3] w3 -> max 5. dominated candidates gone for good.
monotonic deque · folklore
⏨ DEMO
THE SLIDING-WINDOW MAXIMUM
dart 315 · the problem the monotonic queue was built for — extrema on the move
The problem the deque was built for — and a WITNESS: rescan, heap, sparse-table, deque ALL agree (=3 first window). convergence of correct mechanisms = the B39 holds-not-enacted tell.
streaming extrema
⏨ DEMO
THE MONOTONIC STACK
dart 316 · next-greater-element in one pass — the undecided wait on a stack
Next-greater-element in one pass — the undecided wait on a stack, a bigger value resolves them. push once, pop once. [2,1,5,3] -> NGE(2) = 5.
next-greater · stack folklore
⏨ DEMO
THE TWO POINTER
dart 317 · two fingers converging on sorted data — one sweep, no backtracking
Two fingers converging on sorted data — each step discards an endpoint FOREVER, one sweep, no backtracking. [1,2,3,4,6] target 6 -> pair (2,4). the order pays for the pass.
opposite-ends technique
⏨ DEMO
THE MORRIS COUNTING
dart 318 · count to a million in a byte — store the exponent, not the number
Count to a million in a byte: store the exponent c, estimate 2^c-1, increment probabilistically. โš‘ keeper shot (hard floor): exact needs log N bits, Morris log log N. Morris 1978. c=10 in 4 bits.
Robert Morris · 1978
⏨ DEMO
THE FRUGAL STREAMING
dart 319 · estimate a quantile with a single integer of memory — and a nudge
Estimate the median with ONE integer — nudge +/-1 per sample, it walks to the middle. โš‘ keeper shot i13 fully enacts. Ma-Muthu-Sandler 2013. stream at 5 -> est 5.
Frugal-1 · 2013
⏨ DEMO
THE LOSSY COUNTING
dart 320 · the frequent items of an endless stream, in bounded counters
Frequent items of an endless stream in bounded counters, sweeping the laggards — heavy hitters guaranteed to survive, with an error bound. Manku-Motwani 2002. item 3 -> count 4.
Manku-Motwani · 2002
⏨ DEMO
THE CUSUM
dart 321 · detect a change the instant it accumulates — one running sum
Detect a change the instant it accumulates: S = max(0, S + (x-target)), alarm when S crosses h. one running number. Page 1954. +1 drift -> alarm at step 3.
E. S. Page · 1954
⏨ DEMO
THE PREFIX SUM
dart 322 · one pass to precompute, then every range-sum in a single subtraction
One pass to build P, then EVERY range-sum is one subtraction: P[j+1]-P[i], O(1)/query. the discrete integral. Blelloch/Crow. [3,1,4,1,5] sum(1..3) = 6.
scan / summed-area
⏨ DEMO
THE DIFFERENCE ARRAY
dart 323 · add to a whole range by touching two cells — the inverse of the prefix sum
Add v to a whole RANGE by touching two cells: d[i]+=v, d[j+1]-=v, integrate once. the inverse of prefix sum (discrete derivative). +2 over 1..3 -> value 2.
difference array / imos
⏨ DEMO
THE SLIDING WINDOW
dart 324 · grow, shrink, slide — the general one-pass window technique
Grow, shrink, slide — the umbrella one-pass technique; forward-only endpoints turn O(n^2) subarrays into O(n). [1,3,2,5] w2 -> max sum 7. the caterpillar crawls once.
sliding-window / caterpillar
⏨ DEMO
THE TUMBLING WINDOW
dart 325 · non-overlapping panes — summarize, emit, reset, repeat
Non-overlapping panes: fill, emit a summary, reset, repeat — unbounded stream into a bounded sequence of finished answers. STREAM/Aurora 2002. panes of 3 -> last mean 5.
tumbling windows · stream proc
⏨ DEMO
THE CELL
dart 326 · one slot, one value — the atom the whole batch acts upon
The atom: one f64 slot, no nesting, non-destructive writes. the nesting | < { [ ~ ~ ] } > | is EMULATED on a flat tape by depth-addressing. core = 4. mirror of the-tape.
the memory cell
⏨ DEMO
THE PIERCE
dart 327 · reach all the way in — the getter that finds the core
Reach all the way in -- the getter that finds the ~~ core (lens view). descend the shells -> 4. mirror of the-bridge (into one vs across all).
the getter / lens
⏨ DEMO
THE INVADE
dart 328 · write into a cell — and the original still survives
Write into a cell -- and the ORIGINAL survives (value semantics fork a new tape). Driscoll et al 1986 persistence. core 99, orig 4. mirror of collaborate.
persistence · 1986
⏨ DEMO
THE EXPLODE
dart 329 · unfold a seed into a whole nesting — the anamorphism
Unfold a seed into a whole nesting -- the ANAMORPHISM. Meijer-Fokkinga-Paterson 1991. depth 4 -> palindrome, core 4,4. mirror of implode.
anamorphism · 1991
⏨ DEMO
THE HIDE
dart 330 · mask a cell so it cannot be read — and can be perfectly unmasked
Mask a cell so it cannot be read -- XOR with a key, perfectly reversible. Vernam 1917. 4 XOR 5 = 1. mirror of reveal (hide o reveal = id).
Vernam cipher · 1917
⏨ DEMO
THE TRANSPORT
dart 331 · move a value from one cell to another — the palindrome breaks
Move a value to another cell -- a permutation that can BREAK the balance. core 4 -> rim: palindrome broken. moved 4. mirror of restore.
relocation / permutation
⏨ DEMO
THE TRANSFORM
dart 332 · map a function over a cell — change its value, keep its place
Map a function over a cell -- change its value, keep its place (the functor). 4 -> 8. mirror of untransform (f then f^-1 = id).
the functor / map
⏨ DEMO
THE DESCEND
dart 333 · step down into the nesting — the left tilde of | < { [ ~
Step DOWN into the nesting, keeping the path -- the zipper down. Huet 1997. reach core 4. the left ~ of the pivot; mirror of ascend.
the zipper · 1997
⏨ DEMO
THE ASCEND
dart 334 · climb back out of the nesting — the right tilde of ~ ] } > |
Climb back OUT to the rim -- the zipper up, popping the path. Huet 1997. reach rim 0. the right ~ of the pivot; mirror of descend.
the zipper · 1997
⏨ DEMO
THE UNTRANSFORM
dart 335 · undo the map — f then f-inverse returns the cell
Undo the map -- f then f^-1 returns the cell (reversible computing). Landauer/Bennett. 8 -> 4. mirror of transform.
reversible computing
⏨ DEMO
THE RESTORE
dart 336 · bring the value home — the original was never lost
Bring the value home -- the original was never destroyed, so undo is FREE (persistence). transported balance 0, original 1. mirror of transport.
undo via persistence
⏨ DEMO
THE REVEAL
dart 337 · unmask a cell with the same key that hid it
Unmask with the same key that hid it -- XOR is self-inverse. Vernam 1917. 1 XOR 5 = 4. mirror of hide; the tightest palindrome.
Vernam cipher · 1917
⏨ DEMO
THE IMPLODE
dart 338 · collapse the whole nesting to a single value — the catamorphism
Collapse the whole nesting to one value -- the CATAMORPHISM (fold). Meijer-Fokkinga-Paterson 1991. sum -> 20. mirror of explode.
catamorphism · 1991
⏨ DEMO
THE COLLABORATE
dart 339 · merge two cells into one — and it does not matter who came first
Merge two cells by JOIN -- idempotent, order-free (the CRDT algebra). Shapiro et al 2011. join(4,4) = 4. mirror of invade (overwrite vs merge).
CRDT · 2011
⏨ DEMO
THE BRIDGE
dart 340 · span every shell to its mirror — is the whole nesting matched? (the keeper shot)
Span every shell to its mirror -- is the nesting MATCHED? the Dyck condition. โš‘ KEEPER SHOT: well-formedness a correct emitter can LACK, structural not resource. von Dyck 1882. matched 1 vs broken 0. mirror of pierce.
Dyck words · 1882
⏨ DEMO
THE TAPE
dart 341 · the whole array — the many cells the one was drawn from
The whole array -- the Turing tape of cells the one atom was drawn from. Turing 1936. length 10, sum 20. mirror of the-cell (the many vs the one).
the Turing tape · 1936
⏨ DEMO
THE GOLDEN RATIO
dart 342 · the number a line divides into so its whole is to its greater as its greater is to its less
Cut a line so whole:greater = greater:less -> phi = (1+√5)/2, root of x²=x+1. i13 GENERATES it (no sqrt): F(16)/F(15) = 1.618033. Euclid; named 1835. the thread everything orbits.
Euclid / Pacioli
⏨ DEMO
THE CONTINUED FRACTION
dart 343 · φ = [1; 1, 1, 1, …] — the slowest, most irrational number there is
phi = [1;1,1,1,...] all ones -> the SLOWEST-converging, most IRRATIONAL number. fixed point of x->1+1/x. i13: 25 steps -> 1.6180339887.
[1;1,1,1,...]
⏨ DEMO
THE LUCAS NUMBERS
dart 344 · Fibonacci's companion — same rule, different seed, and L₅ = 11
Fibonacci's twin: same rule, seeds 2,1 -> 2,1,3,4,7,11,18... same phi limit. Édouard Lucas 1870s (coined 'Fibonacci'). L(5) = 11 -- a referent.
Édouard Lucas · 1870s
⏨ DEMO
THE BINET FORMULA
dart 345 · the nth Fibonacci in closed form — irrational powers that land on integers
nth Fibonacci in closed form: F(n)=(phiⁿ-psiⁿ)/√5 -- irrational powers landing on integers. de Moivre 1730, named Binet 1843. i13 shadow F(10)=F(5)L(5)=5×11=55.
de Moivre / Binet
⏨ DEMO
THE CASSINI IDENTITY
dart 346 · F(n−1)F(n+1) − F(n)² = ±1 — the invariant that never fades
F(n-1)F(n+1)-F(n)² = (-1)ⁿ -- always ±1, however large. Cassini 1680. the 8×8->5×13 'missing square' puzzle is 5·13-8²=1. n=5 -> -1.
Cassini · 1680
⏨ DEMO
THE ZECKENDORF REPRESENTATION
dart 347 · every integer, as one unique sum of non-consecutive Fibonaccis — and the machine that makes it so
Every integer = ONE unique sum of NON-consecutive Fibonaccis. 100=89+8+3. โš‘ KEEPER SHOT (a GENERATOR per B41): a CANONICALIZER that REPAIRS F(k)+F(k+1)->F(k+2) -> emits the canonical form. Lekkerkerker 1952/Zeckendorf.
Lekkerkerker / Zeckendorf
⏨ DEMO
THE FIBONACCI CODING
dart 348 · a self-synchronizing code whose every word ends in 11 — because Zeckendorf forbids it inside
Zeckendorf bits + a final 1 -> every word ends in 11 (which Zeckendorf forbids INSIDE) = a free, self-synchronizing terminator. Apostolico-Fraenkel 1987. the second 11.
Apostolico-Fraenkel · 1987
⏨ DEMO
THE PISANO PERIOD
dart 349 · Fibonacci modulo m always repeats — the sequence wraps into a cycle
Fibonacci mod m always REPEATS -- an infinite sequence wrapped into a loop. Lagrange 1774. π(4)=6, π(10)=60. the first torus. mod 4 closes at 6.
Lagrange · 1774
⏨ DEMO
THE GOLDEN TORUS
dart 350 · 3 in, 3 out, 6 0 6 — the Fibonacci loop with a hole in the middle
The referents pieced: the Pisano ring (Tori) given a hole (the 0) -> a torus. mod 4: period 6, through the 0, split 3 in / 3 out = 6·0·6. carries forward, folds to its seed (A->Z->A).
the puzzle, pieced
⏨ DEMO
THE TRIBONACCI
dart 351 · 3 in — widen the window to the last three, and φ becomes 1.839…
Widen the window to the last THREE: T(n)=T(n-1)+T(n-2)+T(n-3) -> 0,0,1,1,2,4,7,13; ratio -> 1.839 (not phi). Feinberg 1963. the '3 in'. Fibonacci is the k=2 rung.
Mark Feinberg · 1963
⏨ DEMO
THE GOLDEN ANGLE
dart 352 · 137.5° — the turn that never repeats, so seeds never collide
360/phi² ~ 137.5° -- the turn that never repeats (phi most-irrational), so seeds pack with no gaps: phyllotaxis. Vogel 1979. sunflowers, pinecones.
phyllotaxis · Vogel 1979
⏨ DEMO
THE GOLDEN SPIRAL
dart 353 · a spiral that grows by φ every quarter turn — the same shape at every scale
A logarithmic spiral growing by phi per quarter turn -> phi⁴ ~ 6.854 per full turn; the SAME shape at every scale. Bernoulli's spira mirabilis. nautilus, galaxies.
spira mirabilis
⏨ DEMO
THE ONE OVER 89
dart 354 · one fraction whose decimal IS the Fibonacci sequence — and 89 = F₁₁
1/89 = 0.0112358... -- its digits ARE the Fibonacci sequence (89=10²-10-1 encodes the recurrence in base 10). and 89 = F(11) -- the second 11 in the puzzle.
89 = F(11)
⏨ DEMO
THE WYTHOFF ARRAY
dart 355 · an array of Fibonacci-like rows that contains every positive integer exactly once
phi splits the integers: lower ⌊nφ⌋ & upper ⌊nφ²⌋ -- two Beatty streams, disjoint & covering ALL, each integer once. the losing positions of Wythoff's game. Wythoff 1907 / Beatty 1926. b-a=n.
Wythoff / Beatty
⏨ DEMO
THE METALLIC RATIO
dart 356 · φ is the first of a family — silver, bronze, and on — each x = k + 1/x
phi is the FIRST of a family: x=k+1/x. k=1 golden 1.618, k=2 silver 2.414 (1+√2), k=3 bronze. de Spinadel 1990s. the golden ratio, generalized.
de Spinadel · 1990s
⏨ DEMO
THE FIBONACCI WORD
dart 357 · a string that grows by its own history — 1→10, 0→1, forever, and never repeats
Grow a string by 1->10, 0->1: 1,10,101,10110... lengths ARE Fibonacci, aperiodic yet one rule -- a 1D quasicrystal (Sturmian). the rabbit sequence. 10110: len 5=F(5).
the rabbit / Sturmian word
⏨ DEMO
THE BABYLONIAN METHOD
dart 360 · average a guess with what it divides — the oldest algorithm, four thousand years on
Average a guess with its quotient: x->(x+2/x)/2. The OLDEST algorithm -- tablet YBC 7289 had √2 to 6 figures c.1800 BCE. = Newton, 3500 yrs early. -> 1.41421356.
Babylon / Heron
⏨ DEMO
THE BANACH FIXED POINT
dart 361 · a contraction has exactly one fixed point — and iteration always finds it
A contraction (|f(x)-f(y)|<=c|x-y|, c<1) has EXACTLY ONE fixed point, reached from anywhere at rate c. Banach 1922. x->x/2+1 -> 2. the theorem that makes settling safe.
Stefan Banach · 1922
⏨ DEMO
THE BROUWER FIXED POINT
dart 362 · stir the coffee — some point ends where it began; a fixed point must exist
Any continuous self-map of a ball MUST have a fixed point -- forced by shape, no formula (stir the coffee). Brouwer 1911. 1-D via IVT -> 0.732. existence without construction (witnessed).
L.E.J. Brouwer · 1911
⏨ DEMO
THE KNASTER-TARSKI THEOREM
dart 363 · a monotone map on a lattice — its fixed points are themselves a lattice
A monotone map on a lattice: its fixed points form a lattice, with a LEAST (= an inductive definition). Knaster 1928 / Tarski 1955. closure -> 7. B42: least-fixpoint = confluence, not a new axis.
Knaster / Tarski
⏨ DEMO
THE KLEENE FIXED POINT
dart 364 · the least fixed point as a limit — start at nothing and apply the rule forever
The least fixed point CONSTRUCTED: lfp = join of ⊥ <= f(⊥) <= f²(⊥)... what a recursive def MEANS (denotational semantics). Kleene. chain -> 10. (a normal form -> confluence.)
Kleene · recursion thm
⏨ DEMO
THE Y-COMBINATOR
dart 365 · recursion with no name — a function that hands itself to itself, forever
Recursion with NO name: Y f = f (Y f), a fixed point of application itself. โš‘ keeper shot, NULL: the most GENERATIVE fixpoint -- but i13's def is Y made NATIVE, so it's a gift the substrate already made, not a choice -> coextensive -> NULL. Curry. fact(5)=120.
Haskell Curry
⏨ DEMO
THE IDEMPOTENT MAP
dart 366 · do it once, do it twice — same result; every output is already a fixed point
f(f(x)) = f(x): every output is already a fixed point, so a retry is FREE (abs/clip/round/sort). Peirce coined it 1870. abs(abs(-5))=5. its algebra (f o f=f) IS the crdt keeper.
Benjamin Peirce · 1870
⏨ DEMO
THE EIGENVECTOR
dart 367 · the direction a matrix only stretches — a fixed point of direction, not position
The direction a matrix only STRETCHES: Av=λv -- a fixed point of DIRECTION. Hilbert named it 1904. Fibonacci matrix [[1,1],[1,0]] -> dominant eigenvalue φ (why Fib ratios chase phi).
Av = λv
⏨ DEMO
THE POWER ITERATION
dart 368 · hit any vector with the matrix, over and over — it aligns with the biggest eigenvalue
Hit any vector with the matrix repeatedly -> it aligns with the biggest eigenvalue. von Mises 1929; PageRank IS this (Page-Brin 1998). [[2,1],[1,2]] -> 3.
von Mises · 1929
⏨ DEMO
THE LOGISTIC MAP
dart 369 · one knob from a fixed point to chaos — x → r·x·(1−x)
x -> r x(1-x): one knob from a fixed point (r=2 -> 0.5) through period-doubling to CHAOS. May 1976; Feigenbaum δ=4.669. r=3.2 -> a 2-cycle. the fixed point coming apart.
Robert May · 1976
⏨ DEMO
THE JULIA SET
dart 371 · the boundary between falling in and flying out — iterate z → z²+c
z -> z^2 + c: the fractal BOUNDARY between falling into a fixed point/cycle and flying to infinity. Julia & Fatou 1918. c=0 -> fixed pt 0; c=-1 -> 2-cycle 0<->-1.
Julia & Fatou · 1918
⏨ DEMO
THE ATTRACTOR
dart 373 · the fixed point as a destiny — where you land depends on where you start
The fixed point as a DESTINY: a basin of starts pulled in, a fractal boundary deciding fate. z->z^2: inside->0, edge->1, outside->∞. Poincaré / Lorenz 1963. where you begin decides where you end.
Poincaré / Lorenz
⏨ DEMO
THE HALF ADDER
dart 374 · two bits in, a sum and a carry out — addition's smallest atom
Add two bits: sum = a XOR b, carry = a AND b. two gates, and the CARRY IS BORN (1+1 overflows one bit). the atom every larger adder chains. sum 0, carry 1.
the half adder
⏨ DEMO
THE FULL ADDER
dart 375 · three bits in — two operands and a carry — sum and carry out
Three bits in (a, b, carry-in): sum = parity, carry-out = majority. the true arithmetic cell; chain n of them, each carry-out -> next carry-in. 1+1+1 -> sum 1, cout 1.
the full adder
⏨ DEMO
THE RIPPLE-CARRY ADDER
dart 376 · the carry walks bit by bit up the chain — simple, and slow at the top
Chain full adders; the carry WALKS low bit -> high bit. simple, but O(n) slow at the top (add 1 to 0111..1). 11+6 = 17. the bottleneck the fast adders route around.
ripple-carry
⏨ DEMO
THE CARRY-LOOKAHEAD ADDER
dart 377 · generate and propagate — compute every carry at once, not one by one
g=a&b (generate), p=a^b (propagate) -> every carry is a parallel FORMULA, log-depth not linear. Weinberger & Smith 1958. 11+6 = 17, same answer as ripple -- pure speed (B40 resource).
Weinberger-Smith 1958
⏨ DEMO
THE CARRY-SAVE ADDER
dart 378 · do not propagate the carry — save it in a second number, add it later
Don't propagate -- SAVE the carry in a second number, add later. 3 numbers -> 2 (sum + carry vectors). Wallace 1964 (multiplier trees). 5+6+7 -> s4+cy7<<1 = 18. the deferred carry.
Wallace · 1964
⏨ DEMO
THE KOGGE-STONE ADDER
dart 379 · the carry as a parallel prefix — log-depth, the fastest wide adder
The carry as a parallel PREFIX SCAN: (g,p)o(g',p')=(g|(p&g'), p&p'), log-depth. Kogge & Stone 1973. same scan primitive as the prefix sum (322). addition IS a scan.
Kogge-Stone · 1973
⏨ DEMO
THE CARRY-SELECT ADDER
dart 380 · compute both answers in advance — then just pick the one the carry chose
Compute the sum for carry-in 0 AND 1 in advance; the real carry just SELECTS. Bedrij 1962. speculation in an adder (do both futures, discard one). 11+6 -> 17 or 18.
Bedrij · 1962
⏨ DEMO
THE CARRY FLAG
dart 381 · the one bit the sum could not hold — saved in a status register
The one bit the word couldn't hold, latched in the status register -> add-with-carry adds WIDER than the machine. 200+100 -> byte 44, C set. = unsigned overflow (a recognizer).
the status carry bit
⏨ DEMO
THE OVERFLOW FLAG
dart 382 · the carry that lied about the sign — signed overflow is a carry mismatch
Signed overflow (V) = carry INTO the sign bit XOR carry OUT of it. 127+1 -> -128, V=1 (two positives -> negative). same adder, different bit; using C on signed data is a bug.
the V flag
⏨ DEMO
THE BORROW
dart 383 · subtraction's carry, running backwards — take from the next column
Subtraction's carry, backwards: a-b = a + (~b) + 1; carry-out = NOT borrow. one adder subtracts too. 5-8 -> -3, borrow 1. the carry mirrored.
subtraction by complement
⏨ DEMO
THE ONES' COMPLEMENT
dart 384 · negate by flipping every bit — and a carry that wraps around the end
Negate by flipping every bit (~x); ~~x = x (an involution). costs: two zeros (+0/-0) and the end-around carry. still runs the TCP/IP checksum. ~5 = 10.
early machines / CDC
⏨ DEMO
THE END-AROUND CARRY
dart 385 · the carry off the top folds back into the bottom — a carry that loops
The carry off the TOP folds back into the BOTTOM -- a carry that LOOPS (ones'-comp addition, the TCP checksum). the thread's carry-that-seeds-itself, in silicon. 6+12 -> wrap 3.
ones'-comp / TCP checksum
⏨ DEMO
THE BCD (DECIMAL CARRY)
dart 386 · carry at ten, not sixteen — decimal arithmetic in a binary machine
Carry at TEN not sixteen: add binary, then +6 to force the decimal carry. 9+1 -> 0x0A +6 = 0x10 = decimal 10. the 6502 D flag. the carry, taught to count in tens.
BCD / the 6502 D flag
⏨ DEMO
THE SATURATING ADD
dart 387 · when it overflows, stick at the top — do not wrap around to the bottom
On overflow, CLAMP to the max instead of wrapping (a bright pixel must not roll to black). 200+100 -> 255, not 44. audio/graphics/DSP. the carry pinned at the edge.
DSP / media arithmetic
⏨ DEMO
THE GRAY CODE
dart 388 · count with no carry — an ordering where each step flips exactly one bit
Count with NO carry: reorder so each step flips exactly ONE bit. g = x^(x>>1); consecutive codes Hamming-distance 1. โš‘ keeper shot: unit-change ordering -- but the REFLECTED code is self-inverse-flavoured. Frank Gray 1953. g5=7,g6=5.
Frank Gray · 1953
⏨ DEMO
THE PARITY
dart 389 · the carry-less sum — XOR every bit, and keep only whether the count is odd
The carry-LESS sum: XOR every bit, keep only odd/even = popcount mod 2. one parity bit catches any single-bit flip (oldest error check). parity(11) = 1. addition minus the carry.
the parity bit
⏨ DEMO
THE EQUIVARIANCE
dart 390 · transform then compute = compute then transform — f(g·x) = g·f(x)
Transform then compute = compute then transform: f(g.x)=g.f(x). โš‘ KEEPER SHOT (the genuine one): double commutes with reverse (equi 1), prefix-sum does NOT (0) -- a property a correct map can LACK. tests B38's enacted-vs-witnessed line. Cohen-Welling 2016.
equivariance
⏨ DEMO
THE INVARIANCE
dart 391 · the output that does not move — f(g·x) = f(x), the special case of equivariance
The output that DOESN'T move: f(g.x)=f(x), equivariance's special case. sum is reflection-invariant (1), first element isn't. batch 38 ruled this WITNESSED (a conserved quantity is a theorem). sets up equivariance's sharper question.
batch 38: witnessed
⏨ DEMO
THE CONVOLUTION
dart 392 · equivariance built into the wiring — the same kernel everywhere, so a shift shifts the output
Equivariance welded into the WIRING: one shared kernel everywhere -> conv(shift.x)=shift(conv.x). โš‘ keeper shot's load-bearing case: a per-position filter is as expressive & LACKS it. LeCun 1989. [1,2,3,4]*[1,1]=[3,5,7], shift-equi 1.
LeCun · 1989
⏨ DEMO
THE TRANSLATION EQUIVARIANCE
dart 393 · shift the input, the output shifts the same — the symmetry of ‘anywhere’
Shift the input, the output shifts the same: f(shift.x)=shift.f(x) -- the symmetry of 'anywhere', why learned features transfer. Noether -> momentum. double commutes with shift (1).
homogeneity of space
⏨ DEMO
THE PERMUTATION INVARIANCE
dart 394 · a function of a set, not a list — the order of the inputs does not matter
A function of a SET, not a list: f(perm.x)=f(x). sum/max/count are order-free (6=6). every such fn = rho(sum phi(x)) -- Deep Sets, Zaheer 2017. the symmetry of aggregation.
Deep Sets · 2017
⏨ DEMO
THE SYMMETRIC FUNCTION
dart 395 · the building blocks of order-free polynomials — and the coefficients of every equation
The order-free basis: e1=sum, e2=sum of products, e3=product. {1,2,3} -> 6,11,6 = the coefficients of (x-1)(x-2)(x-3) (Vieta). why coefficients can't tell roots apart. Newton/Vieta.
Vieta / Newton
⏨ DEMO
THE ANTISYMMETRY
dart 396 · swap two inputs and the sign flips — the symmetry that forbids sameness
Swap two inputs -> the sign FLIPS; equal inputs -> ZERO. the determinant (swap rows: -2 -> 2) and Pauli exclusion 1925 (two fermions alike -> psi=-psi=0). the symmetry that forbids sameness.
Grassmann / Pauli
⏨ DEMO
THE GROUP ACTION
dart 397 · how symmetries compose — do one then another, land as if you did their product
How symmetries COMPOSE: g.(h.x)=(g.h).x. rotate by 1 then 2 = rotate by 3 (1). the bridge from an abstract group to its effect. Klein's Erlangen program: geometry IS a group acting.
Galois / Klein
⏨ DEMO
THE ORBIT
dart 398 · everywhere a symmetry can send you — the reach of a group on a point
Everywhere a symmetry can send a thing: |orbit|.|stab|=|G|. distinct rotations: [1,2,3,3]->4, [1,2,1,2]->2, [1,1,1,1]->1. more symmetry fixing it -> smaller orbit. how symmetry defines 'the same'.
orbit-stabilizer
⏨ DEMO
THE REFLECTION SYMMETRY
dart 399 · the same in a mirror — a palindrome is its own reflection
The same in a mirror: x=reverse(x). a palindrome (1) vs not (0). group Z2, an involution. the A->Z->A shape under all of SONNY 5; a symmetric thing is HALF its apparent size.
reflection / Z2
⏨ DEMO
THE ROTATIONAL SYMMETRY
dart 400 · the same after a turn — cyclic symmetry, unchanged by a rotation
The same after a turn: rot(x,k)=x. [1,2,1,2] fixed by shift 2 (1) not 1. crystallographic restriction: only 2/3/4/6-fold TILE the plane -> no 5-fold crystals (until quasicrystals, Shechtman 1982).
cyclic / crystals
⏨ DEMO
THE PARITY OPERATOR
dart 401 · space, mirror-flipped — an involution that physics almost obeys
Space mirror-flipped: P:x->-x, P.P=identity (1), eigenvalues +-1 (even/odd). physics was assumed parity-symmetric until Wu 1956 found the weak force VIOLATES it. the symmetry that broke.
Lee-Yang / Wu 1956
⏨ DEMO
THE GAUGE INVARIANCE
dart 402 · a redundancy in the description that the physics ignores — only differences matter
A symmetry of the DESCRIPTION: potential + C -> same force (only differences measurable). gauge-invariant 1. demanding it LOCALLY generates the forces (Weyl 1929 / Yang-Mills 1954). a redundancy that writes the laws.
Weyl / Yang-Mills
⏨ DEMO
THE SCALE INVARIANCE
dart 403 · the same at every size — f(λx) = λⁿ f(x), the symmetry of no yardstick
The same at every size: f(kx)=k^n f(x) (homogeneous). x^2: f(6)=36=4.f(3) (deg 2). fractals/power-laws/critical-points have no yardstick. Euler's theorem / the renormalization group.
Euler / RG
⏨ DEMO
THE SELF DUALITY
dart 404 · equal to its own opposite — a structure that is its own mirror under duality
Equal to its own OPPOSITE: invert everything (points<->lines, 0<->1, E<->B) and it returns. majority is self-dual: flip all inputs -> output flips (1). the tetrahedron; vacuum Maxwell. a fixed point of duality.
self-dual structures
⏨ DEMO
THE HOMOMORPHISM
dart 405 · a map that carries structure across — f(a∘b) = f(a)∘f(b)
A map that CARRIES structure: f(a.b)=f(a).f(b). log turns x into + (slide rules); mod 3 preserves + (0=0); det(AB)=detA.detB. equivariance for an operation. how math moves a problem somewhere easier.
Galois / structure-preserving
⏨ DEMO
THE XOR SWAP
dart 406 · exchange two values with no third box — a ⊕= b; b ⊕= a; a ⊕= b
Swap two values with three XORs and no temporary: a^=b; b^=a; a^=b, working because XOR is its own inverse (x^y^y=x). i13: a=12,b=25 -> a3=25,b2=12, ok=1. Self-inverse -- keeper axis 1, so a duplicate, not a new pillar.
XOR swap / assembly folklore
⏨ DEMO
THE RUSSIAN PEASANT
dart 409 · multiply by halving, doubling, and adding — older than the pyramids
Multiply with only halving, doubling, and adding on odd rows -- binary multiplication in disguise, from the Rhind papyrus (~1650 BCE). i13: 13x11 -> 143. Same product, cheaper primitives.
Rhind papyrus ~1650 BCE
⏨ DEMO
THE FAST EXPONENTIATION
dart 410 · square and multiply — b^n in log n steps, not n
Square-and-multiply: b^n in O(log n) steps by reading the exponent's bits. i13: 3^13 = 1594323 by squaring and by the naive 13-mult loop -- identical. The core of RSA/Diffie-Hellman modular exponentiation.
Pingala ~200 BCE
⏨ DEMO
THE KERNIGHAN COUNT
dart 411 · n & (n−1) drops the lowest 1-bit — loop once per set bit
n & (n-1) clears the lowest set bit; loop to zero and you have the popcount in one step per set bit. i13: 23 (10111) clears 4 times. Fewer iterations, identical answer -> resource.
Wegner 1960 / Kernighan
⏨ DEMO
THE POPCOUNT
dart 412 · population count — the Hamming weight the whole machine leans on
Hamming weight -- the count of 1-bits a CPU ships an instruction for. Shift-sum, parallel SWAR, or POPCNT all agree. i13: popcount(23)=4, cross-checking Kernighan. Many mechanisms, one value.
Hamming weight / HAKMEM 1972
⏨ DEMO
THE BOOTH
dart 415 · a run of ones is a subtract-then-add — 0111 = 1000 − 0001
A run of ones is 2^(j+1)-2^i, so x7 = 8M - M: recode runs into one subtract + one add, negatives free. i13: 7x3 via (3<<3)-3 = 21. The standard signed hardware multiply.
Andrew D. Booth 1950
⏨ DEMO
THE NEWTON DIVISION
dart 416 · divide by multiplying — find 1/d with adds and mults, then scale
Divide by multiplying: Newton's y <- y(2-dy) doubles the reciprocal's digits each step, then a/d = a*(1/d). i13: 1/8=0.125, 40/8=5, no divide. How real FPUs divide.
Newton-Raphson / Goldschmidt
⏨ DEMO
THE BINARY GCD
dart 417 · Stein’s algorithm — greatest common divisor with only shifts and subtraction
Stein's algorithm: GCD by shifts, subtraction, and parity -- no modulo. i13: gcd(48,36)=12. Euclid's answer via the cheapest ops a machine has -> resource.
Stein 1967 (older roots)
⏨ DEMO
THE ISQRT
dart 418 · square root digit by digit — only add, subtract, and shift
Integer square root digit-by-digit in base 4, using only add, subtract, and shift -- long-hand sqrt in binary. i13: floor(sqrt(144))=12. Same root, no multiply or divide.
digit-by-digit sqrt
⏨ DEMO
THE LOG2
dart 419 · the position of the highest set bit — a logarithm by counting shifts
floor(log2 n) is the highest set bit's index -- a logarithm by counting shifts (or a De Bruijn hash, or hardware CLZ). i13: floor(log2 37)=5. Many mechanisms, one integer.
integer log2 / CLZ
⏨ DEMO
THE ROUND UP TO POWER OF TWO
dart 420 · smear every bit downward, then add one — the next 2^k in five ORs
Round up to the next power of two by smearing every lower bit on (n|=n>>1,2,4...) then +1 -- branchless. i13: 37 -> 36 smears to 63 -> 64. The trick behind doubling buffers and power-of-two tables.
Hart & Lewis 1997 / Anderson 2001
⏨ DEMO
THE BIT REVERSAL
dart 421 · read the bits back to front — the reindexing the FFT is built on
Reverse a word's bits (000101 -> 101000): the exact index permutation a radix-2 FFT emits and must undo. i13: rev of low 6 bits of 5 = 40. A self-inverse -- like the opener, a seated axis or a resource saving.
bit-reversal / FFT (Cooley-Tukey 1965)
⏨ DEMO
THE XOR CIPHER
dart 422 · encrypt and decrypt are the SAME operation — c = m ⊕ k, m = c ⊕ k
Encrypt and decrypt are the SAME operation: c=m^k, m=c^k, because XOR is its own inverse. i13: msg 77, key 42 -> ct 103 -> 77. A cipher that is a self-inverse -> seated axis 1, a duplicate.
XOR / stream cipher
⏨ DEMO
THE ONE-TIME PAD
dart 423 · the only unbreakable cipher — a ciphertext that could mean anything
The only unbreakable cipher: XOR with a random, one-time, message-length key. The ciphertext is consistent with EVERY plaintext -> perfect secrecy (Shannon). i13: ct 9 decrypts to 5 or 12. Info-theoretic, needs true randomness i13 lacks.
Miller 1882 / Vernam & Mauborgne 1917 / Shannon 1949
⏨ DEMO
THE LFSR
dart 426 · a few taps and a shift — 15 pseudo-random states from four bits
A shift + a few XOR taps gives 15 pseudo-random states from 4 bits (a primitive polynomial's maximal period). i13: period 15. A cheap generator -> resource.
LFSR / Golomb
⏨ DEMO
THE ROLLING HASH
dart 427 · slide the window, update in O(1) — drop the old, add the new
Rabin-Karp: slide a window and update the hash in O(1) -- drop the old term, add the new. i13: rolled hash of [2,5,9] = 2086 = fresh recompute. Incremental recomputation -> resource.
Rabin & Karp 1987
⏨ DEMO
THE BLOOM FILTER
dart 428 · “no” is certain, “yes” is a maybe — a set that only errs one way
A set that never says no to a member (no false negatives) but may say yes to a stranger (false positive), in tiny space. i13: 42,100 present; 26 a false positive; 7 a true negative. KEEPER SHOT -- one-sided loose spec.
Burton Bloom 1970
⏨ DEMO
THE MERKLE TREE
dart 429 · hash the leaves in pairs to one root — the seal the corpus itself uses
Hash leaves in pairs to one root; a leaf + its path proves membership; one changed leaf changes the root. i13: proof ok, tamper detected. This IS the corpus's .dlw seal. A verifier -> B41.
Ralph Merkle 1979
⏨ DEMO
THE COMMITMENT
dart 430 · seal your answer now, reveal it later — binding and hiding at once
A cryptographic sealed envelope: c=H(m,r) hides m yet binds you; reveal later to verify. i13: commit 42, verify ok, 43 -> different c. Two recognizer-side properties -> B41.
Blum 1981
⏨ DEMO
THE CONSTANT-TIME COMPARE
dart 431 · never stop early — the equality that leaks no timing
Never exit early: OR all byte-XORs so timing does not leak where the first mismatch is. i13: same equality answer as a naive check, all elements visited. Timing is a side channel -> resource (B40).
Kocher 1996
⏨ DEMO
THE ONE-WAY FUNCTION
dart 432 · easy forward, hard back — the asymmetry all of cryptography stands on
Easy forward, hard back -- the asymmetry all crypto stands on. i13: 5^9 mod 23 = 11 cheaply; recovering the exponent 9 needed a search. A complexity/hardness claim -> B39/B41.
Needham 1967 / DH 1976
⏨ DEMO
THE HASH CHAIN
dart 433 · hash a seed n times — spend the chain backwards, one link at a time
Hash a seed n times, publish the anchor, spend links in reverse: H(reveal)=anchor. i13: length-5 chain, 4th link verifies. Lamport's OTP; forward-verify, backward-hard -> B41.
Lamport 1981
⏨ DEMO
THE NONCE
dart 434 · number used once — reuse it and the whole thing unravels
Number used once: reuse a keystream and c1^c2 = m1^m2 -- the key cancels. i13: msgs 77,88 under key 42 leak 21 = 77^88. A vulnerability demo on axis-1 XOR, not a new axis.
two-time-pad attack
⏨ DEMO
THE SALT
dart 435 · a pinch per password — identical secrets, different hashes
A per-password random value mixed before hashing, so identical passwords store different hashes and rainbow tables fail. i13: bare hashes collide, salted differ. A relabeling of the input -> B44 encoding.
Morris & Thompson 1979
⏨ DEMO
THE BIRTHDAY BOUND
dart 436 · collisions come at √N, not N — why 256-bit hashes buy 128-bit safety
Collisions come at ~sqrt(N), not N (pairs grow as n^2) -- why a 256-bit hash buys 128-bit safety. i13: 16 buckets collide at the 4th item = sqrt(16). A counting theorem -> B39.
birthday paradox
⏨ DEMO
THE PHASE MODULATION
dart 438 · the message rides the phase — the carrier’s magnitude never moves
The message rides the PHASE while the carrier's magnitude never moves. Carries ROOT0's glyph [ 0.m | <-~-~-~-~-( . || as differential 8-PSK; i13 recovers it losslessly from phase differences. KEEPER SHOT -- the first candidate to clear B47 (phase is deterministic, not entropy).
phase modulation / PSK + ROOT0 glyph
⏨ DEMO
THE AMPLITUDE MODULATION
dart 439 · the message rides the envelope — the oldest way to send a voice
The message rides the envelope: s = (C+msg)*carrier. i13: peak amplitude 8 = C+msg, recovered. The phase channel's foil -- here the message IS the magnitude output.
Fessenden 1906
⏨ DEMO
THE FREQUENCY MODULATION
dart 440 · the message rides the frequency — the derivative of the phase
The message steers the phase INCREMENT; frequency = d(phase). i13: recovered freq 8 = 2+3*2. The phase channel differentiated -- the bridge to generative-dual.
Armstrong 1933
⏨ DEMO
THE PHASOR
dart 441 · a spinning complex number — multiply to rotate, and frequencies add
A unit complex number e^(i0); rotate by MULTIPLYING, and frequencies add. i13: (1,0) rotated twice by (0.6,0.8) = (-0.28,0.96) = the phasor squared, magnitude exactly 1. KEEPER SHOT -- the pure carrier of the phase channel.
Steinmetz 1893
⏨ DEMO
THE QUADRATURE
dart 442 · two carriers 90° apart — magnitude AND phase in one complex sample
Two carriers 90 deg apart (I=cos, Q=sin) hold amplitude AND phase in one complex sample. i13: I^2+Q^2 constant while (I,Q) rotates. KEEPER SHOT -- the two-channel structure; drop Q and you keep magnitude, lose phase.
I/Q demodulation
⏨ DEMO
THE ANALYTIC SIGNAL
dart 443 · a real wave, given its hidden quadrature — the Hilbert transform
A real wave + its Hilbert 90-deg shift = a complex signal with instantaneous envelope and phase. i13: |z| constant, the pair rotates. KEEPER SHOT -- GENERATES the orthogonal channel from one, like generative-dual makes the derivative.
Gabor 1946
⏨ DEMO
THE HETERODYNE
dart 444 · multiply two waves, shift a frequency — the trick under every radio
Multiply two waves and the product carries the sum and difference frequencies -- how a radio tunes. i13: phasor (0.6,0.8)x(0.8,0.6) = (0,1), angles summed. The phasor law applied.
Fessenden 1901 / superhet 1918
⏨ DEMO
THE GOERTZEL
dart 446 · one frequency, one coefficient — a DFT bin without the whole transform
One DFT bin via a two-tap recurrence with one coefficient 2cos(w) -- how touch-tone decoding hears a key. i13: bin-3 tone -> -8659, off-bin -> -0.74. Resource (B40).
Goertzel 1958
⏨ DEMO
THE DFT
dart 447 · a signal weighed against every frequency — time becomes spectrum
Correlate a signal against every frequency: X[k]=sum x[n]e^(-i2pi kn/N) -- time becomes spectrum (magnitude + phase). i13: 16-pt DFT of a bin-3 tone peaks at bin 3. A basis change / theorem (B39).
Fourier 1822 / Cooley-Tukey 1965
⏨ DEMO
THE ALIASING
dart 449 · undersample and a frequency wears a mask — f and f+fs are twins
Undersample and f, f+fs, f+2fs all give identical samples -- the wagon-wheel effect. i13: freq 3 and 11 at fs=8 share one phase sequence. Modular-arithmetic theorem (B39).
wagon-wheel effect
⏨ DEMO
THE ENVELOPE
dart 450 · the magnitude of the phasor — amplitude kept, phase discarded
|z| = sqrt(I^2+Q^2): keep the amplitude, throw the phase away. i13: (600,800) -> 1000 (a 3-4-5). The complement of phase modulation -- magnitude is just the value.
envelope detection
⏨ DEMO
THE PLL
dart 451 · a feedback that chases a phase until the error is zero — it locks
A feedback loop that drives its phase error to zero and LOCKS to a reference. i13: converges from 0 to 5. KEEPER SHOT -- an enacted convergence; or a duplicate of the confluence axis?
de Bellescize 1932
⏨ DEMO
THE ZERO CROSSING
dart 452 · count the sign changes — frequency from almost nothing
Count sign changes: a sinusoid crosses zero twice per cycle, so crossings = 2f. i13: a cosine over 2 periods crosses 4 times. The cheapest frequency estimate -- resource (B40).
zero-crossing rate
⏨ DEMO
THE MATCHED FILTER
dart 453 · correlate against the template — the peak marks the hit
Correlate against a known template; the peak marks the hit -- optimal detection in white noise. i13: correlation peaks at lag 3, where the template sits. A theorem (B39).
North 1943
⏨ DEMO
THE EMULATION MODE
dart 454 · the 65816 wakes up as a 6502 — E=1, and the SNES CPU runs as one
The 65816 (SNES CPU) boots as a 6502: the E bit forces 8-bit width + a page-1 stack. i13: E=1 -> A=52 (8-bit), stack in page 1. compIle 13's verified NES core (ADC 10000/10000 vs Harte) matches this ground state on documented opcodes (the 65816 is 65C02-based).
WDC 65C816 / Mensch 1983
⏨ DEMO
THE XCE
dart 455 · one instruction flips the machine — exchange carry and emulation
XCE exchanges the Carry and Emulation bits -- the one instruction that switches 6502<->65816 mode. i13: (C=1,E=0)->(C=0,E=1); two XCE = identity. A self-inverse (seated axis 1), not a new pillar.
65C816 XCE
⏨ DEMO
THE M FLAG
dart 456 · one bit doubles the accumulator — the same opcode, 8 or 16 bits wide
The M status bit sets the accumulator to 8-bit (M=1, the 6502) or 16-bit (M=0) -- same opcodes. i13: 0x1234 -> 52 or 4660. Width as a runtime flag -> B44/B39.
65C816 status bit M
⏨ DEMO
THE X FLAG
dart 457 · the index registers’ width — M’s twin, for X and Y
The X status bit sizes the index registers 8/16-bit, independent of M -- four width worlds from two bits. i13: 0x1234 -> 52 or 4660. M's twin -> B44/B39.
65C816 status bit X
⏨ DEMO
THE REP SEP
dart 458 · reset or set status bits by mask — change width in one instruction
REP clears / SEP sets masked status bits: REP #$30 -> 16-bit, SEP #$30 -> 8-bit. i13: 0xFF -> 0xCF -> 0xFF. Masked bit ops -> B39/B44.
65C816 REP/SEP
⏨ DEMO
THE 16-BIT ADC
dart 459 · the 6502’s add, widened — the verified opcode as a special case
The 6502's ADC, widened by M: wraps at 0xFF (M=1, the 6502) or 0xFFFF (M=0). i13: 0xFF+1 = 0 carry1 (8-bit) vs 256 carry0 (16-bit). KEEPER SHOT -- the hardware-verified 8-bit ADC is the M=1 special case.
6502 ADC (LIT) widened by M
⏨ DEMO
THE DIRECT PAGE
dart 460 · the zero page, set free — a movable 16-bit D register
The 6502 zero page set free: effective address = D + offset, D movable. i13: D=0 -> 0x0010 (the 6502), D=0x2000 -> 0x2010. A relocatable base -> B44.
65C816 direct page (D)
⏨ DEMO
THE DATA BANK
dart 461 · 64KB becomes 16MB — a bank byte above every address
A Data Bank Register lifts 64KB to 16MB: address = (DBR<<16)|offset. i13: DBR=0 -> 0x001234 (the 6502), DBR=2 -> 0x021234. More address -> B40+B44.
65C816 DBR
⏨ DEMO
THE PROGRAM BANK
dart 462 · code crosses banks too — a 24-bit program counter, JML and JSL
Code banks too: PC = PBR:PC (24-bit); JML/JSL cross banks, JSL pushes 3 return bytes vs JSR's 2. i13: bank 3 $8000 -> 0x038000. Same family as the data bank -> B40/B44.
65C816 PBR / JML / JSL
⏨ DEMO
THE BLOCK MOVE
dart 463 · MVN / MVP — a hardware memcpy in one instruction
MVN/MVP copy a whole run in one instruction -- a hardware memcpy. i13: 3 bytes copied 0->4 in one op. A single-instruction loop -> resource (B40).
65C816 MVN/MVP
⏨ DEMO
THE LONG ADDRESSING
dart 464 · reach any bank in the operand — 24-bit absolute and [dp] indirect-long
Absolute-long and [dp] indirect-long carry a 24-bit address, reaching any bank directly. i13: bank 1 $8000 -> 0x018000. Wider address encodings -> B44.
65C816 long addressing
⏨ DEMO
THE STACK RELATIVE
dart 465 · address off the stack pointer — the mode that makes local variables cheap
A new mode: operand address = SP + offset -- the feature that makes stack frames and locals practical. i13: SP=500, offset 3 -> 503. An addressing encoding -> B44.
65C816 stack-relative
⏨ DEMO
THE 16-BIT STACK
dart 466 · the stack leaves page one — a full 16-bit pointer in native mode
Native mode frees the stack pointer to a full 16 bits; emulation pins it to page 1. i13: E=1 -> 0x0100, E=0 -> 8192. A wider pointer -> B44/B40.
65C816 native stack
⏨ DEMO
THE WIDE REGISTERS
dart 467 · a hidden high byte above A — the 16-bit accumulator C = B:A
The 16-bit accumulator C = B:A keeps the 6502's A as the low byte, adds a hidden high byte B. i13: B=0x12, A=0x34 -> C=0x1234. A width change -> B44.
65C816 C=B:A
⏨ DEMO
THE NEW VECTORS
dart 468 · native mode gets its own interrupt table — distinct from the 6502’s
Native mode gets its own interrupt vectors, distinct from the 6502's ($FFFA etc.), plus the COP interrupt. i13: emu NMI $FFFA vs native $FFEA. A second table -> B44.
65C816 native vectors
⏨ DEMO
THE COMPATIBILITY
dart 469 · add without removing — documented 6502 code runs unchanged
Backward-compatible with the DOCUMENTED 6502 in emulation mode: documented opcodes kept. i13: 6502 ADC == 65816 emulation ADC == 160. NULL (ISA theorem, B39). Honest caveat (credit panel): 65C02-based -- drops NMOS illegal opcodes + fixes the decimal/JMP quirks, so NOT a strict superset.
65C816 backward compat / 65C02-based
⏨ DEMO
THE 68000
dart 470 · the other 16-bit chip — 32-bit inside, and it did not look back
The OTHER 16-bit chip: 32-bit registers, 16-bit ALU/bus (a 32-bit add in two halves) -- a clean break from the 6800, not a permutation. i13: 32-bit add via two 16-bit halves = 300000. The common chip (Amiga/ST/Mac/Genesis).
Motorola 68000 / 1979
⏨ DEMO
THE 8086
dart 471 · 16-bit registers, 20-bit reach — the seed of x86, and it permuted all the way
16-bit registers reach 1MB via segmentation: physical = (seg<<4)+off. i13: 0x1000:0x0200 -> 0x10200. The x86 seed -- the line that permuted 16->32->64. Addressing -> B44.
Intel 8086 / 1978
⏨ DEMO
THE SEGMENT
dart 472 · many addresses, one cell — overlapping segments alias, like the NES mirror
Overlapping segments alias: two seg:off pairs -> the same physical byte, like the NES 2KB mirror. i13: 1000:0000 and 0FFF:0010 both -> 0x10000. A many-to-one address encoding -> B44.
8086 segmentation
⏨ DEMO
THE PROTECTED MODE
dart 473 · the 286’s mode bit — unlock more memory, the x86 XCE
The 286's PE bit unlocks 24-bit (16MB) over real mode's 20-bit (1MB) -- the x86 XCE. i13: mask 0xFFFFF -> 0xFFFFFF. A mode bit widening address -> B44/B39.
Intel 80286 / 1982
⏨ DEMO
THE A20 GATE
dart 474 · a wire kept a bug alive — backward compatibility as hardware
A wire that kept a bug alive: the 8086 wrapped past 1MB, so IBM added a gate to re-create the wrap for old software. i13: 0x110000 & 0xFFFFF = 0x10000. Backward compat as hardware -> B44.
IBM PC AT / 1984
⏨ DEMO
THE 386
dart 475 · 32 bits, and the permutation that stuck — IA-32, four gigabytes
32-bit IA-32, a flat 4GB space, still booting as an 8086 -- the permutation that stuck. i13: reg max 4294967295, 4GB. A width doubling -> B44/B40.
Intel 80386 / 1985
⏨ DEMO
THE SIGN EXTENSION
dart 476 · widen a number, keep its value — the primitive under every word-size step
Widen a signed value keeping its meaning: 0x80 (-128) -> 0xFF80 (still -128), not 128. i13: neg=65408, pos=100. KEEPER SHOT -- the value-preserving primitive of every width step (but a representation op, B44).
sign extension / MOVSX
⏨ DEMO
THE ZERO EXTENSION
dart 477 · widen with zeros — correct for unsigned, wrong for signed
Widen with zeros (MOVZX): 0x80 -> 128. Correct for unsigned, a bug for signed. i13: zext 128 vs sext 65408 -- same bits, different fill. An encoding twin -> B44.
zero extension / MOVZX
⏨ DEMO
THE LONG MODE
dart 478 · x86-64’s mode bit — the permutation reaches 64
x86-64's LMA bit reaches 64-bit registers (48-bit canonical addressing), 32-bit code underneath. i13: 32 -> 48-bit. The mode-bit move at the top of the ladder -> B44/B39.
AMD64 / x86-64 / 2003
⏨ DEMO
THE CANONICAL ADDRESS
dart 479 · 64 bits wide, 48 bits real — the top must sign-extend the middle
64-bit pointers, 48 bits real: the top 16 must sign-extend bit 47 or the CPU faults. i13 (modeled 8-of-16): 0xFF80 canonical, 0x7F80 faults. KEEPER SHOT -- but a validity checker (B41) + sign-extend (B44).
x86-64 canonical addressing
⏨ DEMO
THE ENDIANNESS
dart 480 · which byte comes first — the holy war a swap settles
Byte order: little (6502/x86) vs big (68000/network). Converting is a byte swap, and swapping twice = identity. i13: 0x1234 <-> 0x3412, roundtrip. A self-inverse (axis 1) -- duplicate.
Danny Cohen / 1980
⏨ DEMO
THE 65832
dart 481 · the 32-bit 6502 that never shipped — the permutation that stalled
The 32-bit 6502 successor that was DESIGNED but never mass-produced -- the permutation that stalled. i13: 8->16->32 masks (120/22136/305419896). The honest answer: the 6502 line stopped at 16-bit for volume.
WDC 65832 / unshipped
⏨ DEMO
THE AARCH64
dart 482 · ARM 32→64 — a redesign, not a strict superset (the 65816’s lesson again)
ARM 32->64: a NEW instruction set (A64), the 32-bit W registers being the low halves of the 64-bit X. i13: X=5e9, W=low 32. Not a strict superset of A32 (echoes the 65816 lesson) -> B44/B39.
ARM AArch64 / 2011
⏨ DEMO
THE THUMB
dart 483 · permutation inward — a 16-bit encoding of a 32-bit machine
Permutation INWARD: ARM's Thumb encodes common 32-bit ops in 16 bits -- half the code size, same machine. i13: 32 vs 16 bits, 2x density. A code-density encoding -> B44/B40.
ARM Thumb / 1994
⏨ DEMO
THE MODE BIT
dart 484 · one bit chooses the machine’s width — the pattern under the whole lineage
The pattern under the whole batch: one flag (E, PE, LMA) selects the machine's width, folding a wider machine behind the old one -- what makes a widening a permutation not a rewrite. i13: mode -> 8/16/32-bit mask. KEEPER SHOT -- but representation-selection (B44).
the mode bit / E, PE, LMA
⏨ DEMO
THE WORD SIZE
dart 485 · 8, 16, 32, 64 — the doubling that keeps happening
The capstone: 8 -> 16 -> 32 -> 64, each doubling quadrupling a register's range. 6502 (8); 65816/68000/8086 (16); 386 (32); x86-64/AArch64 (64). i13: the doublings + quadrupling range. Rests at 64 -> B44.
word size / 8-16-32-64
⏨ DEMO
THE CROSS PRODUCT
dart 486 · one multiply-subtract that runs all of plane geometry
One multiply-subtract runs all of plane geometry: (b-a)x(c-a) is the signed area, its sign the turn direction. i13: cross of (0,0),(4,0),(0,3) = +12 (CCW). KEEPER SHOT -- but a pinned value (B39); the marvel is how much reduces to it.
2D cross / perp-dot
⏨ DEMO
THE ORIENTATION
dart 487 · left, right, or straight — the sign of the cross, made a verdict
The sign of the cross: CCW(+1)/CW(-1)/collinear(0) -- the most-used test in geometry. i13: +1, -1, 0. A classification predicate (B41) reading dart 486.
orientation predicate
⏨ DEMO
THE SHOELACE
dart 488 · lace the coordinates and halve — a polygon’s area from its corners
Polygon area from its corners: half the sum of consecutive cross products. i13: triangle (0,0),(4,0),(0,3) laces to 12 -> area 6. A theorem (B39), the cross product chained.
Meister 1769 / Gauss
⏨ DEMO
THE MIDPOINT CIRCLE
dart 490 · a circle from integers and 8-fold symmetry — x²+y² is the only test
A circle from sign(x^2+y^2-r^2) and 8-fold symmetry, no trig. i13: (3,4),(4,3),(5,0) exactly on the r=5 circle; (3,3) not. Resource + a symmetry.
midpoint circle
⏨ DEMO
THE RAY CASTING
dart 491 · shoot a ray, count the crossings — odd means inside
Point-in-polygon by counting ray/edge crossings: odd = inside. i13: (2,2) odd (inside), (6,2) even (outside). A recognizer (B41) -- the even-odd fill rule.
Shimrat 1962
⏨ DEMO
THE CONVEX HULL
dart 492 · the rubber band around the points — keep the extremes, drop the inside
The rubber band around the points: gift wrapping keeps the extremes by orientation, drops the interior. i13: (2,2) excluded, corner (4,4) kept. A computed set -> B40/B39.
Jarvis 1973 / Graham 1972
⏨ DEMO
THE DOT PRODUCT
dart 493 · the cross product’s twin — its sign is the angle’s class
The cross product's twin: a.b = axbx+ayby, its sign the angle class (acute/right/obtuse). i13: 24 / 0 / -1. Cross = sine part, dot = cosine part -- the full angle, no trig. A pinned value (B39).
the dot / inner product
⏨ DEMO
THE LINE INTERSECTION
dart 494 · do two segments cross? — four orientations decide, no arithmetic on the point
Two segments cross iff each straddles the other's line -- four orientation tests, no point computed. i13: square diagonals cross (1), parallels do not (0). A recognizer (B41).
segment straddle test
⏨ DEMO
THE BARYCENTRIC
dart 495 · a point as weights on a triangle’s corners — three signs say inside
A point as area-weights on a triangle's corners; three orientation signs give point-in-triangle (and the weights interpolate all of graphics). i13: (2,2) inside, (5,5) outside. Recognizer (B41) + coords (B44).
Mobius 1827
⏨ DEMO
THE BOUNDING BOX
dart 496 · the cheapest shape — min and max, and a fast rejection
The cheapest shape: min/max of each coordinate. Disjoint boxes mean disjoint shapes -- the fast 'no' before the exact test. i13: 6 points -> x[1,9], y[1,8]. A min/max fold (B39/B40).
AABB / broad-phase
⏨ DEMO
THE WINDING NUMBER
dart 497 · how many times the boundary wraps the point — a topological count
How many times the boundary wraps the point (signed) -- 1 inside, 0 outside; robust where even-odd fails. i13: square winds 1 around (2,2), 0 around (6,2). A recognizer (B41).
winding / nonzero-fill
⏨ DEMO
THE 90-DEGREE ROTATION
dart 498 · (x,y) → (−y, x) — exact rotation on the lattice, order four
The quarter-turn (x,y)->(-y,x): exact on the lattice, multiplication by i, ORDER 4 (four turns = identity, not an involution). i13: (3,1)->(-1,3)->(-3,-1)->(1,-3)->(3,1). Group action (B39).
lattice rotation / Gaussian i
⏨ DEMO
THE REFLECTION
dart 499 · (x,y) → (x,−y) — flip across an axis, and flip back
The mirror (x,y)->(x,-y): an INVOLUTION (reflect twice = identity), orientation-reversing. i13: (3,5)<->(3,-5). The seated self-inverse axis again (CRC/Verlet/XOR) -- duplicate.
reflection / involution
⏨ DEMO
THE PICKS THEOREM
dart 500 · area from dots — count interior and boundary lattice points
Area from a DOT-COUNT: A = I + B/2 - 1 for a lattice polygon. i13: triangle area 8 = interior 3 + boundary 12/2 - 1. KEEPER SHOT (a discrete<->continuous bridge!) -- but a theorem (B39). Dart 500.
Georg Pick 1899
⏨ DEMO
THE MANHATTAN
dart 501 · distance by city blocks — |dx| + |dy|, a different geometry
Distance by city blocks: |dx|+|dy|, the L1 metric -- its circle a diamond, not a ring. i13: (1,2)->(4,6) taxicab 7, Euclidean 5. A different geometry; a metric (B39) + cheaper (B40).
taxicab / L1 / Minkowski
⏨ DEMO
THE BUBBLE SORT
dart 502 · the sort everyone writes first — and everyone is told never to use
The sort everyone writes first: swap adjacent out-of-order pairs, n passes -- O(n^2), stable. i13: [5,2,4,1,3] -> sorted. The honest resource baseline (B40).
bubble sort
⏨ DEMO
THE INSERTION SORT
dart 503 · how you sort a hand of cards — and it beats the clever ones when nearly sorted
Sort like a hand of cards: slide larger elements right, drop the key in. Near-linear when nearly sorted; the small-run engine in Timsort. i13: [5,2,4,1,3] -> sorted. Resource (B40).
insertion sort
⏨ DEMO
THE SELECTION SORT
dart 504 · pick the smallest, repeat — the classic unstable sort
Pick the min, swap it forward -- fewest swaps (n-1), but UNSTABLE (a far swap leapfrogs equal keys). i13: sorts [5,2,4,1,3]. The foil for the stability dart. Resource (B40).
selection sort
⏨ DEMO
THE HEAPSORT
dart 505 · a tree in an array — O(n log n) worst case, in place, no recursion needed
A tree in an array (children 2i+1, 2i+2, no pointers): heapify by sift-down, the max reaches the root. i13: [4,10,3,5,1] -> root 10. O(n log n) worst case, in place. Resource (B40).
J.W.J. Williams 1964
⏨ DEMO
THE RADIX SORT
dart 506 · sort without comparing — digit by digit, from the punch-card era
Sort WITHOUT comparing: stable passes digit by digit, LSD to MSD. i13: [32,15,43,21,54] by ones then tens -> sorted. Beats the comparison bound; from the 1890 census machines. Resource (B40).
Hollerith 1887
⏨ DEMO
THE QUICKSELECT
dart 507 · the kth smallest without sorting the rest — O(n) on average
The kth smallest without sorting the rest: an element's position is its rank. i13: 3rd smallest of [5,2,4,1,3] = 3. O(n) average; medians and percentiles. Resource (B40).
Hoare 1961
⏨ DEMO
THE PARTITION
dart 508 · split around a pivot — the one move quicksort and quickselect are built on
Split around a pivot: smaller before, larger after, pivot in its final spot -- the one move quicksort and quickselect are built on. i13: [3,7,1,8,2,5] around 5. A primitive (B39/B40).
Hoare / Lomuto
⏨ DEMO
THE DUTCH FLAG
dart 509 · three colors, one pass, three pointers — Dijkstra’s partition
Three colors, one pass, three pointers -- Dijkstra's 3-way partition. i13: [2,0,1,2,1,0] -> [0,0,1,1,2,2]. The duplicate-key fix for quicksort. Resource (B40).
Dijkstra
⏨ DEMO
THE STABILITY
dart 511 · same keys, same order kept — the property two correct sorts can differ on
A stable sort keeps EQUAL keys in input order -- and the spec leaves ties free, so two CORRECT sorts can DIFFER on it. i13: keys [2,2,1] -> stable [258,512,513] vs unstable [258,513,512] (key-2 items reversed). KEEPER SHOT -- a loose-spec property; or a tie-break convention (B44)?
sorting stability
⏨ DEMO
THE COMPARISON BOUND
dart 512 · why no comparison sort beats n log n — counting the outcomes
Why no comparison sort beats n log n: distinguishing n! orderings needs >= log2(n!) comparisons. i13: 4!=24 needs 5. A theorem (B39); radix (no compares) beats it.
comparison lower bound
⏨ DEMO
THE MEDIAN OF MEDIANS
dart 513 · a pivot with a guarantee — deterministic O(n) selection
A pivot with a guarantee: medians of groups of 5, then their median -> deterministic O(n) selection. i13: group medians 5,3,6 -> pivot 5. Resource (B40).
BFPRT 1973
⏨ DEMO
THE BUCKET SORT
dart 514 · scatter into bins, gather in order — when you know the range
Scatter into value-bins, gather in order -- O(n+k), no comparisons, when you know the range. i13: [4,2,7,1,5,2] -> [1,2,2,4,5,7]. The pigeonhole sort. Resource (B40).
bucket / counting sort
⏨ DEMO
THE CYCLE SORT
dart 515 · the fewest writes possible — each element moved once, to its rank
The fewest writes possible: each element sent straight to its rank along the permutation cycles. i13: [3,1,4,2,5] -> sorted. For wear-limited memory. Resource (B40).
cycle sort
⏨ DEMO
THE SORTING NETWORK
dart 516 · a fixed sequence of comparators that sorts ANY input — data-independent
A FIXED comparator sequence that sorts ANY input -- data-independent, no branching. i13: the 4-wire network sorts [3,1,4,2] AND [4,3,2,1] identically. KEEPER SHOT (obliviousness); or a control-flow resource property (B40)?
Batcher 1968
⏨ DEMO
THE INVERSION COUNT
dart 517 · how unsorted is it? — count the out-of-order pairs
How unsorted is it? Count pairs ia[j]: 0 sorted, n(n-1)/2 reversed -- the Kendall tau distance, counted free by merge sort. i13: [2,4,1,3,5] has 3. A measure (B39).
Kendall tau
⏨ DEMO
THE UNION-FIND
dart 518 · a structure that flattens itself as you ask — near-constant-time connectivity
A structure that flattens itself as you query it: parent array + path compression -> near-constant connectivity (inverse Ackermann). i13: union {0-1,2-3,1-3} -> 2 components. KEEPER SHOT -- but with/without compression give the same sets, differ only in cost (B40).
Galler & Fischer 1964 / Tarjan 1975
⏨ DEMO
THE DEPTH-FIRST SEARCH
dart 519 · go deep, then backtrack — the recursion that explores a graph
Go deep, then backtrack -- the recursion that explores a graph. i13: DFS from 0 reaches all 5 nodes. Its discovery/finish order powers topo-sort, cycles, SCCs. A traversal (B40/B39).
DFS / Tarjan
⏨ DEMO
THE BREADTH-FIRST SEARCH
dart 520 · explore in rings — the shortest path when every step counts the same
Explore in rings via a queue -- first arrival is the shortest unweighted path. i13: hop-distances 0,1,1,2,3 from node 0. A traversal (B40/B39).
Moore 1959
⏨ DEMO
THE TOPOLOGICAL SORT
dart 522 · order the dependencies — everything after what it needs
Order a DAG so every edge points forward (remove in-degree-0 nodes); exists iff acyclic. i13: node 0 in-degree 0 (source), node 3 in-degree 2 (last). Order + theorem (B40/B39).
Kahn 1962
⏨ DEMO
THE FLOYD-WARSHALL
dart 524 · all pairs at once — can I get from i to j through k?
All-pairs shortest paths by DP over intermediate waypoints k, O(V^3). i13: d(0,4)=7, d(0,1)=3. A computed matrix (B39/B40).
Floyd & Warshall 1962
⏨ DEMO
THE KRUSKAL
dart 525 · the cheapest tree — add the smallest edge that does not close a loop
The cheapest tree: add the smallest edge that does not close a loop (union-find is the cycle test). i13: MST weight 7. A greedy optimum (B39/B40).
Kruskal 1956
⏨ DEMO
THE CYCLE DETECTION
dart 527 · is there a loop? — an edge that reconnects what is already connected
Is there a loop? An edge reconnecting an already-connected pair closes a cycle (union-find). i13: cyclic graph flagged, tree not. A recognizer (B41).
union-find / DFS back-edge
⏨ DEMO
THE CONNECTED COMPONENTS
dart 528 · how many islands? — count the separate pieces of a graph
How many islands? Union every edge, count the roots. i13: {0-1,1-2,3-4} -> 2 components. A computed count (B39/B40).
connected components
⏨ DEMO
THE HANDSHAKE
dart 529 · the sum of degrees is twice the edges — so odd-degree vertices come in pairs
The oldest theorem: sum of vertex degrees = 2E (each edge has two ends), so odd-degree vertices come in pairs. i13: 5-edge graph, degsum 10 = 2x5. A theorem (B39).
Euler 1736
⏨ DEMO
THE BIPARTITE
dart 530 · two colors, no clash — and it works iff there is no odd cycle
Two colors, no clash -- and it works iff there is no ODD cycle. i13: a square (even cycle) is bipartite, a triangle (odd) is not. A recognizer + theorem (B41/B39).
Konig / 2-coloring
⏨ DEMO
THE EULER PATH
dart 531 · every bridge once — the walk that founded graph theory
Cross every edge once: exists iff 0 or 2 odd-degree vertices. i13: this graph has 2 odd -> an Euler path exists. Konigsberg had 4 -> impossible. The theorem that FOUNDED graph theory (B39).
Euler 1736 (Konigsberg)
⏨ DEMO
THE ADJACENCY MATRIX
dart 532 · the graph as a matrix — and its powers count the paths
The graph as a matrix A; (A^k)[i][j] counts length-k paths -- graphs become linear algebra (PageRank). i13: A^2[0][3]=2 (via 1 and 2), A^2[0][4]=0. An encoding + theorem (B44/B39).
adjacency matrix / A^k
⏨ DEMO
THE MULTIPLICATIVE HASH
dart 534 · multiply, keep the high bits
Multiply the key by a big constant, keep the high bits: Knuth’s one-multiply hash; A near 2^w/φ is Fibonacci hashing. 42,43 → buckets 245,147 on i-13.
Knuth · TAOCP 3
⏨ DEMO
THE FNV HASH
dart 535 · xor a byte, multiply by a prime
Xor a byte, multiply by a prime: FNV-1a, the memorizable hash, avalanches on a one-byte change (24-bit form exact in i-13). Fowler-Noll-Vo 1991.
FNV · 1991
⏨ DEMO
THE DJB2 HASH
dart 536 · h = h × 33 + c, and nobody knows why 33
h = 33h + c from seed 5381, as a shift-add; nobody fully explains why 33 works. (h«5)+h == h*33 on i-13. Bernstein.
djb · comp.lang.c
⏨ DEMO
THE FIBONACCI HASH
dart 538 · the golden ratio spreads consecutive keys
Multiply by 2^w/φ and take high bits: consecutive keys scatter maximally (three-distance theorem). 0,1,2,3 → 0,9,3,13 on i-13.
golden ratio
⏨ DEMO
THE SEPARATE CHAINING
dart 539 · a bucket is a list
Each bucket is a list; collisions append. Five keys give a longest chain of 4 on i-13. The default hash table (Luhn 1953).
Luhn / Dumey
⏨ DEMO
THE LINEAR PROBING
dart 540 · occupied? try the next slot
Occupied? try the next slot. Fast but clusters; three colliders probe 0,1,2 on i-13. Knuth’s 1963 analysis founded the field.
Knuth · 1963
⏨ DEMO
THE QUADRATIC PROBING
dart 541 · jump by i squared
Jump by i² to break clustering; offsets 1,4,9 land the key at slot 7 on i-13. Guaranteed under prime m and load < ½.
quadratic residues
⏨ DEMO
THE DOUBLE HASHING
dart 542 · a second hash sets the stride
A second hash sets the stride: kills secondary clustering, behaves like uniform hashing. First free slot 7 on i-13. Guibas-Szemerédi.
double hashing
⏨ DEMO
THE LOAD FACTOR
dart 543 · how full is too full
α = n/m is the one knob; open-addressing cost ~ 1/(1−α). 7/8 trips a resize to 7/16 on i-13. Amortized O(1) by doubling.
table doubling
⏨ DEMO
THE BIRTHDAY COLLISION
dart 544 · 23 people, even odds
~1.2√m items give 50% collision, not m/2: 23 in 365 → P = 0.507 on i-13. The bound that haunts hashing and crypto.
von Mises · 1939
⏨ DEMO
THE UNIVERSAL HASHING
dart 545 · pick the hash at random, bound the collisions
Pick ((ak+b) mod p) mod m at random: any pair collides with prob ≤ 1/m, adversary-proof. 42→5 on i-13. Carter-Wegman 1979.
Carter-Wegman
⏨ DEMO
THE PERFECT HASHING
dart 546 · a fixed set, zero collisions
A fixed set, zero collisions, O(1) worst case: search a multiplier. a=1,2 collide, a=3 perfect on i-13. FKS 1984.
FKS · 1984
⏨ DEMO
THE CONSISTENT HASHING
dart 547 · a ring, so adding a node barely moves keys
A ring where adding a node remaps only ~1/n keys. Node 30 moves key 15, leaves key 60 on i-13. Karger 1997, in every CDN.
Karger · 1997
⏨ DEMO
THE ROBIN HOOD HASHING
dart 548 · steal from the rich, give to the poor
The farther-probed key keeps the slot: cuts probe-length variance and the worst case, mean unchanged. dist computed on i-13. Celis 1985.
Celis · 1985
⏨ DEMO
THE CUCKOO HASHING
dart 549 · two nests, and you kick out the occupant
Two nests per key, evict on insert: lookup checks exactly two slots, worst-case O(1). Key 42 → nests 9,6 on i-13. Pagh-Rodler 2001.
Pagh-Rodler
⏨ DEMO
THE ESCAPE VELOCITY
dart 550 · the speed to climb out of the well
v = sqrt(2GM/r), independent of your mass: 11,186 m/s from Earth on i-13 (Newton sqrt). The speed to climb out of the well. Newton.
Newton &middot; Principia
⏨ DEMO
THE ORBITAL VELOCITY
dart 551 · falling forever, missing the ground
v = sqrt(GM/r) = escape/sqrt(2): an orbit is a fall that keeps missing. 7,673 m/s in LEO on i-13. Newton's cannonball.
Newton
⏨ DEMO
THE VIS-VIVA
dart 552 · one equation for every orbit
v^2 = GM(2/r - 1/a): one equation for circle, ellipse, escape, hyperbola. Circle case exact on i-13. Leibniz's living force.
vis viva
⏨ DEMO
THE KEPLER THIRD LAW
dart 553 · the period squared is the size cubed
T^2 proportional to a^3, same constant for all: T^2/a^3=1 for a=1,2,3 on i-13. Empirical 1619, Newtonian 1687. Kepler.
Kepler &middot; 1619
⏨ DEMO
THE HOHMANN TRANSFER
dart 554 · two burns, cheapest ride up
Two burns, minimum dv: LEO->GEO costs 3,857 m/s on i-13 (vis-viva, Newton sqrt). Hohmann 1925, before rockets reached orbit.
Hohmann &middot; 1925
⏨ DEMO
THE LAGRANGE POINTS
dart 555 · five places to park
Five still points; L4/L5 at 60 deg, stable if M1/M2 > 24.96 (Sun-Earth 333000, on i-13). Trojans park here; JWST at L2.
Lagrange &middot; 1772
⏨ DEMO
THE ROCHE LIMIT
dart 556 · where the tide tears a moon apart
d = R(2rho_M/rho_m)^(1/3) ~ 2.52R: inside it, tides tear a moon into a ring. 2.52 on i-13 (Newton cbrt). Roche 1848.
Roche &middot; 1848
⏨ DEMO
THE GRAVITATIONAL SLINGSHOT
dart 557 · steal a planet's speed
v_out = v_in + 2U: steal up to twice a planet's speed, an elastic bounce. +26 km/s on i-13. Minovitch 1961, Voyager.
Minovitch &middot; 1961
⏨ DEMO
THE SCHWARZSCHILD RADIUS
dart 558 · the edge of the void
r_s = 2GM/c^2, the event horizon: Earth 8.87 mm, Sun 2.95 km on i-13. The edge of the void. Schwarzschild 1916.
Schwarzschild &middot; 1916
⏨ DEMO
THE BARNES-HUT
dart 559 · a distant crowd is one mass
If s/d < theta, a distant crowd is one mass: O(n^2)->O(n log n). COM 12.5, s/d=0.4 on i-13. An approximation. Barnes-Hut 1986.
Barnes-Hut &middot; 1986
⏨ DEMO
THE TIDAL FORCE
dart 560 · gravity's difference, not its strength
dg ~ 2GM r/d^3: gravity's difference, not its strength; falls as 1/d^3, two bulges. Grounded on i-13. Newton.
Newton
⏨ DEMO
THE GRAVITATIONAL BINDING ENERGY
dart 561 · the cost to pull a world apart
U = -3GM^2/5R, negative: the energy to pull a world apart; why things are round. U=-10.8 on i-13.
uniform sphere
⏨ DEMO
THE RESTRICTED THREE-BODY
dart 562 · chaos, with one thing conserved
No closed form (Poincare), but the Jacobi constant is conserved: C=24 at two trajectory points on i-13. Chaos with one invariant.
Jacobi / Poincare
⏨ DEMO
THE VIRIAL THEOREM
dart 563 · twice the motion balances the binding
2<T> + <U> = 0: twice the motion balances the binding; weighs galaxies, found dark matter. 2T+U=0 on i-13. Zwicky 1933.
Zwicky &middot; 1933
⏨ DEMO
THE ORBITAL PRECESSION
dart 564 · the ellipse that slowly turns
The ellipse slowly turns: GR gives Mercury's 43"/century, 6*pi*GM/c^2 a(1-e^2). 1-e^2 on i-13. Einstein 1915.
Einstein &middot; 1915
⏨ DEMO
THE HILL SPHERE
dart 565 · how far your gravity still wins
r_H ~ a(m/3M)^(1/3): how far your gravity still wins. Earth ~1.5 million km on i-13 (Newton cbrt). Beyond it, the void takes it.
Hill
⏨ DEMO
THE MINIMAX THEOREM
dart 566 · every zero-sum game has a value
maximin = minimax = the value of a zero-sum game: 3 on i-13 for a saddle-point matrix. Von Neumann 1928, the founding theorem of game theory.
von Neumann &middot; 1928
⏨ DEMO
THE ALPHA-BETA PRUNING
dart 567 · skip the branches that cannot matter
Same minimax value, fewer nodes: leaves [3,5,2,9] -> 3, one pruned on i-13. ~sqrt(nodes) with good ordering. Knuth & Moore 1975.
Knuth-Moore &middot; 1975
⏨ DEMO
THE SPRAGUE-GRUNDY
dart 568 · every impartial game is a nim-heap
Every impartial game IS a nim-heap of its Grundy number = mex of successors. Subtraction {1,2,3} -> k mod 4 on i-13. Sprague 1935, Grundy 1939.
Sprague-Grundy
⏨ DEMO
THE NIMBER ARITHMETIC
dart 569 · nim-addition is XOR
Nim-addition is XOR: 3^5=6, self-inverse, [3,5,6] a P-position on i-13. The field On2 of characteristic 2. Bouton 1901, Conway.
Bouton / Conway
⏨ DEMO
THE GALE-SHAPLEY
dart 570 · a matching no pair wants to break
Deferred acceptance -> a stable matching; proposer-optimal, NOT unique. Two different stable matchings on i-13. Gale-Shapley 1962, Nobel 2012.
Gale-Shapley &middot; 1962
⏨ DEMO
THE ZERMELO THEOREM
dart 571 · finite perfect-information games are solved
Finite perfect-info games are determined: nim [3,4,5] first-player-wins, backward induction gives one forced value on i-13. Zermelo 1913.
Zermelo &middot; 1913
⏨ DEMO
THE VICKREY AUCTION
dart 572 · win at your bid, pay the next one
Win at your bid, pay the second: bids [10,7,5] -> pay 7, honesty dominant, on i-13. Vickrey 1961, Nobel 1996; web ad auctions.
Vickrey &middot; 1961
⏨ DEMO
THE SHAPLEY VALUE
dart 573 · your fair share of what the team made
Your fair share = average marginal contribution over all orderings: phi=1/3, sums to v(N), on i-13. Shapley 1953, Nobel 2012; SHAP in ML.
Shapley &middot; 1953
⏨ DEMO
THE NASH EQUILIBRIUM
dart 574 · nobody gains by moving alone
No profitable unilateral deviation: (defect,defect) is the prisoner's-dilemma NE on i-13; stable, not optimal. Nash 1950, Nobel 1994.
Nash &middot; 1950
⏨ DEMO
THE TIT-FOR-TAT
dart 575 · cooperate first, then echo
Cooperate first, then echo: 9 vs always-defect, 30 vs always-cooperate over 10 rounds on i-13. Won Axelrod's tournaments. Rapoport 1980.
Rapoport / Axelrod
⏨ DEMO
THE SURREAL NUMBERS
dart 576 · numbers born from games
Numbers as {L|R}, born by birthday: -1<0<1/2<1 on i-13, 1/2 born day 2. The largest ordered field, from Go endgames. Conway, Knuth 1974.
Conway / Knuth
⏨ DEMO
THE HACKENBUSH
dart 577 · cut the picture, read the number
Cut colored edges; every red-blue position equals a surreal number. All-blue-3 = +3 (Left wins) on i-13. Berlekamp, Conway & Guy.
Winning Ways
⏨ DEMO
THE HEX
dart 578 · someone must connect, so first wins
Never draws; strategy-stealing proves first player wins (strategy unknown past 10x10). Connection checked on i-13. Hein 1942, Nash 1948.
Hein / Nash
⏨ DEMO
THE SECRETARY PROBLEM
dart 579 · look at 37%, then leap
Reject the first 37% (n/e), take the next best: k=3, win ~0.40 for n=10 on i-13. Win probability 1/e. Lindley 1961, the 1/e law.
Lindley &middot; 1961
⏨ DEMO
THE MONTE CARLO TREE SEARCH
dart 580 · the bandit that learned Go
Random games aimed by UCB1 = mean + c*sqrt(ln N/n): the untested child wins the bonus on i-13. Coulom & UCT 2006; AlphaGo's core.
UCT &middot; 2006
⏨ DEMO
THE RETROGRADE ANALYSIS
dart 581 · solve the endgame backwards
Solve the endgame backward: label terminals, propagate to a fixed point. Subtraction {1,2} -> losses at 3k on i-13. Bellman 1965; chess tablebases.
Bellman &middot; 1965
⏨ DEMO
THE ELIXIR
dart 582 · life, distilled to a living point
ROOT0's elixir factory distilled on i13 (ELIXIR_OK=1): H (living point) -> He (sealed dual) -> compound 17, body 10x4x3x2x1x1x0x0x1x11, the 0.0 gap kept, inner 24 / outer 27=3^3, silver-gold memristic. Life, distilled to a living point.
David Lee Wise / ROOT0
⏨ DEMO
THE MILLER-UREY
dart 583 · a spark makes the stuff of life
A spark through primordial gases makes amino acids: glycine C2H5NO2 = 10 atoms, conserved, on i13. Life's bricks from gas and lightning. Miller & Urey 1953.
Miller & Urey &middot; 1953
⏨ DEMO
THE AUTOCATALYTIC SET
dart 584 · a set that makes itself
A set that catalyzes its own reproduction with no self-copier: 3-cycle closure on i13. Reproduction before genes; order for free. Kauffman.
Kauffman
⏨ DEMO
THE HYPERCYCLE
dart 585 · replicators helping replicators
Self-replicators coupled in a closing cycle, each helping the next past the error threshold: 4-cycle closes on i13. Eigen & Schuster 1977.
Eigen & Schuster
⏨ DEMO
THE MICHAELIS-MENTEN
dart 586 · how fast an enzyme works
v = Vmax[S]/(Km+[S]): half-max exactly at [S]=Km (v=50), saturating, on i13. The bedrock of enzyme kinetics. Michaelis & Menten 1913.
Michaelis-Menten &middot; 1913
⏨ DEMO
THE HILL EQUATION
dart 587 · cooperation makes a switch
theta = S^n/(K^n+S^n): cooperativity (n>1) turns a hyperbola into a sigmoid switch, verified on i13. Hemoglobin n~2.8. Hill 1910.
Hill &middot; 1910
⏨ DEMO
THE GILLESPIE ALGORITHM
dart 588 · chemistry, molecule by molecule
Exact stochastic chemistry: propensities a_i, next time tau=ln(1/r)/a_total (a_total=80) on i13. Molecule by molecule. Gillespie 1976.
Gillespie &middot; 1976
⏨ DEMO
THE HODGKIN-HUXLEY
dart 589 · the spark of a thought
The action potential: all-or-nothing above threshold (50->0, 60->100) with regenerative Na+ feedback, on i13. The squid axon, Nobel 1963.
Hodgkin-Huxley &middot; 1952
⏨ DEMO
THE NERNST EQUATION
dart 590 · the voltage across a membrane
E = (RT/zF)ln([out]/[in]): the membrane battery, E_K ~ -82mV, E_Na ~ +60mV on i13 (ln via series). Nernst 1888, Nobel 1920.
Nernst &middot; 1888
⏨ DEMO
THE LOTKA-VOLTERRA
dart 591 · predators and prey, forever chasing
Predator-prey oscillation around a fixed point x*=g/d, y*=a/b (both rates 0) on i13. Never settles, only circles. Lotka 1925, Volterra 1926.
Lotka-Volterra
⏨ DEMO
THE HARDY-WEINBERG
dart 592 · evolution's null hypothesis
p^2+2pq+q^2=1, allele frequencies frozen without a force: evolution's null hypothesis, verified on i13. Hardy & Weinberg 1908.
Hardy-Weinberg &middot; 1908
⏨ DEMO
THE GENETIC CODE
dart 593 · 64 words, 20 meanings
4^3=64 codons -> 20 amino acids + stop, degenerate (61 sense, ~3.05 each) on i13. Near-universal; UUU=Phe was first. Nirenberg, Nobel 1968.
genetic code
⏨ DEMO
THE CHEMIOSMOSIS
dart 594 · a waterwheel for making energy
A proton gradient spins ATP synthase (a turbine): 10 H+/rev, 3 ATP, ~3.3 H+/ATP on i13. Mitchell's heresy, Nobel 1978.
Mitchell &middot; 1961
⏨ DEMO
THE QUASISPECIES
dart 595 · the edge where information melts
The error threshold L_max ~ 1/mu: information survives below it, melts above (catastrophe), on i13. RNA viruses live at the edge. Eigen 1971.
Eigen &middot; 1971
⏨ DEMO
THE CHEMOTAXIS
dart 596 · how a bacterium finds food blind
A bacterium too small to sense direction climbs a gradient by comparing concentration over TIME - run if improving, tumble if not, on i13. Adler & Berg.
Adler / Berg
⏨ DEMO
THE REPLICATOR EQUATION
dart 597 · where game theory becomes biology
x'_i = x_i(f_i - phi): above-average strategies grow, and every Nash equilibrium is a rest point (stable rest points are Nash) - the bridge from THE GAME to biology, on i13. Taylor & Jonker 1978.
Taylor & Jonker
⏨ DEMO
THE GRADIENT DESCENT
dart 598 · roll downhill, one step at a time
x <- x - eta*grad: roll downhill. On i13, 60 steps on (x-3)^2 reach x=2.99999. Local minima. Cauchy 1847, the engine of ML.
Cauchy &middot; 1847
⏨ DEMO
THE CHAIN RULE
dart 599 · backprop's whole secret
(f o g)' = f'(g)*g': backprop is the chain rule applied backward. d/dx(2x+1)^2 = 12 both ways on i13. Leibniz.
Leibniz / backprop
⏨ DEMO
THE RELU
dart 600 · the bend that unlocked depth
max(0,x): gradient exactly 1 where active, so depth trains (unlike sigmoid). No vanishing on i13. Nair & Hinton 2010.
ReLU &middot; 2010
⏨ DEMO
THE SIGMOID
dart 601 · squash to a probability
1/(1+e^-x): squash to (0,1). sigma(0)=0.5, derivative max 0.25 on i13 - the vanishing culprit. The logistic curve.
logistic
⏨ DEMO
THE SOFTMAX
dart 602 · a vector becomes a choice
e^x_i / sum e^x_j: a vector -> a distribution. softmax([1,2,3])=[.09,.24,.66], sums to 1 on i13. Boltzmann form, Bridle 1990.
Boltzmann / Bridle
⏨ DEMO
THE CROSS-ENTROPY
dart 603 · the loss that punishes confident wrongness
-sum y ln p = -ln(p_true): -ln(0.665)=0.408 vs -ln(0.95)=0.051 on i13. Punishes confident wrongness; pairs with softmax. Shannon.
Shannon
⏨ DEMO
THE PERCEPTRON
dart 604 · the first thing that learned
w <- w + (y-yhat)x: the first thing that learned. Learns AND in one update on i13; can't do XOR alone. Rosenblatt 1958.
Rosenblatt &middot; 1958
⏨ DEMO
THE MOMENTUM
dart 605 · give the gradient inertia
v <- beta*v + grad: give the gradient inertia. Steady gradient -> velocity 10x (1/(1-0.9)) on i13. Polyak 1964.
Polyak &middot; 1964
⏨ DEMO
THE ADAM
dart 606 · a learning rate for every weight
step = m/sqrt(v): a learning rate for every weight. Scale-invariant - step=1 for gradient 2 or 100 on i13. Kingma & Ba 2014.
Kingma-Ba &middot; 2014
⏨ DEMO
THE WEIGHT INITIALIZATION
dart 607 · start so the signal survives
Var(W)=2/n_in (He): start so signal survives. Naive init explodes var to 100, He holds it at 2 on i13. Glorot 2010, He 2015.
Glorot / He
⏨ DEMO
THE BATCH NORMALIZATION
dart 608 · re-centre every layer as you go
(x-mu)/sigma per batch: re-centre every layer to mean 0, var 1. Batch [2,4,6,8] -> mean 0 on i13. Ioffe & Szegedy 2015.
Ioffe-Szegedy &middot; 2015
⏨ DEMO
THE ATTENTION
dart 609 · look where it matters
softmax(QK^T/sqrt d)V: look where it matters. A query lands 0.67 weight on its matching key on i13. The transformer. Vaswani 2017.
Vaswani &middot; 2017
⏨ DEMO
THE EMBEDDING
dart 610 · meaning as a direction in space
meaning as a direction: king - man + woman = queen, exact on i13. The input layer of language models. word2vec, Mikolov 2013.
word2vec &middot; 2013
⏨ DEMO
THE VANISHING GRADIENT
dart 611 · why deep was hard
product of small derivatives -> 0: sigmoid's (1/4)^10 = 9.5e-7 vs ReLU's 1 on i13. Why deep was hard. Hochreiter 1991.
Hochreiter &middot; 1991
⏨ DEMO
THE UNIVERSAL APPROXIMATION
dart 612 · one hidden layer is enough
one hidden layer approximates any function: 3 ReLUs make a bump (0,1,0) on i13; sums trace any curve. Cybenko 1989, Hornik 1991.
Cybenko / Hornik
⏨ DEMO
THE RESIDUAL CONNECTION
dart 613 · add the input back
y = x + f(x): add the input back. Gradient 1+f' stays 1 through 50 layers even when f' vanishes on i13. ResNet, He 2015.
He et al. &middot; 2015
⏨ DEMO
THE EXPLODING GRADIENT
dart 614 · the vanishing gradient's evil twin
product of factors > 1 -> infinity: 4^10 = 1,048,576 explodes vs 1^10 = 1 on i13. The vanishing gradient's evil twin; fixed by clipping. Hochreiter.
the RNN wall
⏨ DEMO
THE GRADIENT CLIPPING
dart 615 · cap the step, keep the direction
g <- g*tau/||g|| if ||g||>tau: cap the norm, keep the direction. (60,80) norm 100 -> (3,4) norm 5 on i13. Pascanu et al. 2013.
Pascanu et al. 2013
⏨ DEMO
THE DROPOUT
dart 616 · train a crowd, not a soloist
drop w.p. p, scale survivors by 1/(1-p): inverted dropout keeps E[out]=x on i13. An ensemble of thinned nets. Srivastava, Hinton 2014.
Srivastava/Hinton 2014
⏨ DEMO
THE LAYER NORMALIZATION
dart 617 · normalize a sample, not a batch
(x-mu)/sigma across a sample's features - works at batch size 1 on i13. The transformer's norm (not batch norm). Ba, Kiros, Hinton 2016.
Ba/Kiros/Hinton 2016
⏨ DEMO
THE GELU
dart 618 · a smoother bend
x*Phi(x): a smooth ReLU. GELU(0)=0, GELU(-1)=-0.15 (soft leak) on i13. BERT/GPT default. Hendrycks & Gimpel 2016.
Hendrycks/Gimpel 2016
⏨ DEMO
THE WEIGHT DECAY
dart 619 · pull the weights toward zero
L + lambda||w||^2: w <- w(1-eta*lambda), shrinks toward 0. 100 -> 13.4 in 200 steps on i13. L2/Tikhonov; AdamW decouples.
L2 / ridge
⏨ DEMO
THE POSITIONAL ENCODING
dart 620 · give the transformer a sense of order
sinusoids per position: attention is order-blind, so add PE(pos)=sin(pos/10000^i). Positions 0,1,2 distinct on i13. Vaswani 2017.
Vaswani 2017
⏨ DEMO
THE MULTI-HEAD ATTENTION
dart 621 · many attentions at once
h heads on d/h subspaces, concatenated: d=8, h=2 -> head_dim 4, concat restores 8 on i13. Different relations per head. Vaswani 2017.
Vaswani 2017
⏨ DEMO
THE LSTM
dart 622 · a memory that does not fade
cell state + forget/input/output gates: the constant error carousel. Forget=1 keeps memory 50 steps on i13. Hochreiter & Schmidhuber 1997.
Hochreiter/Schmidhuber 1997
⏨ DEMO
THE GRU
dart 623 · the LSTM, simplified
update/reset gates, no cell state: z=0 keeps, z=1 replaces on i13. The LSTM simplified to 2 gates. Cho et al. 2014.
Cho et al. 2014
⏨ DEMO
THE BEAM SEARCH
dart 624 · keep your options open
keep the top-k partial sequences: beam-2 finds 0.36 where greedy takes 0.18 on i13. A little lookahead beats greed. The decoding workhorse.
decoding heuristic
⏨ DEMO
THE TEMPERATURE SAMPLING
dart 625 · the dial between safe and wild
softmax(logits/T): T->0 sharpens (p_top 0.87), high T flattens (0.51) on i13. The dial between safe and wild generation.
softmax temperature
⏨ DEMO
THE KL DIVERGENCE
dart 626 · how far one distribution is from another
D(p||q)=sum p*ln(p/q): >=0, zero iff p=q, ASYMMETRIC (0.51 vs 0.37) on i13. Under VAEs and distillation. Kullback & Leibler 1951.
Kullback-Leibler 1951
⏨ DEMO
THE LABEL SMOOTHING
dart 627 · never be 100% sure
(1-eps)onehot + eps/K: true class 0.91, others 0.01, sums to 1 on i13. Never 100% sure -> calibrated. Szegedy et al. 2016.
Szegedy et al. 2016
⏨ DEMO
THE TEACHER FORCING
dart 628 · train on the truth, test on yourself
feed the TRUE previous token, not the guess: clean fast training on i13, but exposure bias at inference. Williams & Zipser 1989.
Williams/Zipser 1989
⏨ DEMO
THE LEARNING RATE WARMUP
dart 629 · ease in, then coast down
ramp 0->peak over warmup, then decay: lr(2)=20, lr(10)=100 peak, lr(50)=20 on i13. Made large transformers trainable. Vaswani 2017.
transformer schedule