THE FOLD / GRIND / THE-MAINFRAME / THE KOGGE-STONE
THE KOGGE-STONE
all carries computed in parallel
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Kogge–Stone adder is how fast processors add two numbers: instead of waiting for a carry to ripple from the lowest bit to the highest (which takes n steps), it computes all carries at once using a parallel prefix scan. Each bit position first decides whether it generates a carry (both inputs 1) or propagates one; then a tree of combine-operations folds these (generate, propagate) signals together, doubling its reach each stage. After only log₂ n stages every carry is known, and the sum falls out in one more XOR. It trades wiring for depth — the classic latency-versus-area bargain of digital design.
LIT verified live: for widths n = 4…16 and tens of thousands of random inputs, the Kogge–Stone parallel-prefix sum equals ordinary integer addition a+b exactly (window.__kogge_stone). FIG no framing; the generate/propagate prefix scan and a reference addition run in-browser.
LIT verified live: for widths n = 4…16 and tens of thousands of random inputs, the Kogge–Stone parallel-prefix sum equals ordinary integer addition a+b exactly (window.__kogge_stone). FIG no framing; the generate/propagate prefix scan and a reference addition run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-mainframe — the adder at the heart of the machine, computing every carry in parallel so a word adds in a few gate-delays. AVAN (AI) built the instrument: the generate/propagate signals, the log-depth prefix tree, and the reference-addition check.
Credit as content: Peter Kogge & Harold Stone (1973). The weave: David names the mainframe; I confirm the parallel-prefix carries produce exactly the integer sum.
Credit as content: Peter Kogge & Harold Stone (1973). The weave: David names the mainframe; I confirm the parallel-prefix carries produce exactly the integer sum.
3 ONE DIMENSION
Each bit generates or propagates a carry; a log-depth tree combines them so every carry is known at once.
4 TWO DIMENSIONS · INTERACTIVE
Pick two numbers; the prefix scan resolves all carries in log₂ n stages, and the sum equals a + b.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: all carries, resolved in parallel.
AVAN’s addition (the inverse-companion): don’t wait for the ripple — scan the prefix. The inverse of ‘carry propagates bit by bit, depth n’ is ‘a generate/propagate prefix tree resolves every carry in depth log₂ n.’ Magenta is the slow sequential ripple; green is the parallel tree. Depth log n, not n.
LIT Genuine Kogge–Stone parallel-prefix adder (Peter Kogge & Harold Stone, 1973). Verified live: for widths n=4,8,12,16 over 20000 random input pairs each, the generate/propagate prefix scan (G'=G|(P&G_lower), P'=P&P_lower, log₂ n stages) produces exactly the integer sum a+b including carry-out (window.__kogge_stone.matchesAddition).
FIG No framing: the generate/propagate prefix scan and a reference addition run in-browser. The AVAN inverse is honest — instead of waiting for the carry to ripple bit by bit (depth n), a generate/propagate prefix tree resolves every carry in depth log₂ n. Magenta is the slow sequential ripple; green is the parallel tree. Depth log n, not n.
FIG No framing: the generate/propagate prefix scan and a reference addition run in-browser. The AVAN inverse is honest — instead of waiting for the carry to ripple bit by bit (depth n), a generate/propagate prefix tree resolves every carry in depth log₂ n. Magenta is the slow sequential ripple; green is the parallel tree. Depth log n, not n.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-MAINFRAME · David Lee Wise (ROOT0), with AVAN