THE FOLD / GRIND / THE-MAINFRAME / THE WALLACE TREE
THE WALLACE TREE
partial products crushed in parallel
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Wallace tree is how fast hardware multiplies. A schoolbook multiply forms one partial product per bit of the multiplier and adds them in sequence — slow, because each add waits for the last. Wallace instead crushes the whole stack of partial products in parallel using 3:2 compressors (full adders): each takes three rows and outputs two — a sum row and a carry row — preserving the total, since x+y+z = sum + 2·carry. Layer after layer the height falls 3→2 until only two rows remain, which a single carry-propagate adder finishes. The depth is logarithmic in the number of partial products, which is why multipliers use it.
LIT verified live: over 200,000 random 8-bit pairs, the carry-save (3:2) reduction of the partial products, finished with one add, equals a·b exactly (window.__wallace). FIG no framing; the partial-product generation and carry-save compression run in-browser.
LIT verified live: over 200,000 random 8-bit pairs, the carry-save (3:2) reduction of the partial products, finished with one add, equals a·b exactly (window.__wallace). FIG no framing; the partial-product generation and carry-save compression run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-mainframe — the multiplier at the core of the machine, crushing a mountain of partial products to two rows in log-depth. AVAN (AI) built the instrument: the partial products, the 3:2 carry-save compressors, the final add, and the a·b check.
Credit as content: Christopher Wallace (1964). The weave: David names the mainframe; I confirm the parallel carry-save reduction yields exactly the product.
Credit as content: Christopher Wallace (1964). The weave: David names the mainframe; I confirm the parallel carry-save reduction yields exactly the product.
3 ONE DIMENSION
Partial products stacked, then reduced by 3:2 compressors — three rows become two (sum + carry) — until only two remain.
4 TWO DIMENSIONS · INTERACTIVE
Pick two numbers; the partial products compress layer by layer, then one add gives exactly a·b.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the product, from a log-depth compression tree.
AVAN’s addition (the inverse-companion): don’t add the rows in sequence — compress them in parallel. The inverse of ‘shift-and-add, depth n’ is ‘3:2 compressors crush n partial products to 2 rows in log-depth, then one add.’ Magenta is the sequential add chain; green is the compression tree. Crush in parallel, add once.
LIT Genuine Wallace tree multiplier (Christopher Wallace, 1964). Verified live: over 200000 random 8-bit pairs, generating the partial products and reducing them with 3:2 carry-save compressors (s=x^y^z, c=((x&y)|(x&z)|(y&z))<<1, preserving x+y+z=s+2c) down to two rows, then one add, equals a·b exactly (window.__wallace.matchesProduct).
FIG No framing: the partial-product generation and carry-save compression run in-browser. The AVAN inverse is honest — instead of adding the partial products in sequence (depth n), 3:2 compressors crush n rows to 2 in logarithmic depth, then one carry-propagate add finishes. Magenta is the sequential add chain; green is the compression tree. Crush in parallel, add once.
FIG No framing: the partial-product generation and carry-save compression run in-browser. The AVAN inverse is honest — instead of adding the partial products in sequence (depth n), 3:2 compressors crush n rows to 2 in logarithmic depth, then one carry-propagate add finishes. Magenta is the sequential add chain; green is the compression tree. Crush in parallel, add once.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-MAINFRAME · David Lee Wise (ROOT0), with AVAN