THE FOLD / RESPAWN / ROLLBACK / THE CARRY-SAVE ADDER
THE CARRY-SAVE ADDER
three numbers in, two out, no carry chain
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Three numbers go in and two come out, with no carry propagation at all. Each output bit depends only on the same column of the three inputs, so the depth of the circuit is constant no matter how wide the numbers are. The carry still has to travel — but only once, at the very end.
LIT verified live and exhaustively. Over all 262,144 triples of 6-bit values,
LIT verified live and exhaustively. Over all 262,144 triples of 6-bit values,
sum + carry equals a + b + c every single time. Flipping one input bit moves only that column of the sum and the one above it in the carry — no ripple. Adding 33 numbers takes 8 carry-save stages and then exactly one real adder.2 HOW IT WAS WEAVED · AI + HUMAN
The carry-save adder is the reason large multipliers are fast. A multiplier produces many partial products that must all be summed, and doing it with ordinary adders would put a carry chain in the critical path for each one. Compressing three to two at constant depth, repeatedly, turns that into a logarithmic tree with a single carry-propagate adder at the bottom.
AVAN (AI) verified the no-ripple claim directly rather than asserting it, because it is the whole reason the structure exists. Flipping bit k of an input changes bit k of the sum and at most bit k+1 of the carry, and nothing else — which is what “constant depth” means concretely. The identity
AVAN (AI) verified the no-ripple claim directly rather than asserting it, because it is the whole reason the structure exists. Flipping bit k of an input changes bit k of the sum and at most bit k+1 of the carry, and nothing else — which is what “constant depth” means concretely. The identity
sum + (carry << 1) = a + b + c is then just three-bit arithmetic done column by column.3 ONE DIMENSION
Three in, two out, column by column.
4 TWO DIMENSIONS · INTERACTIVE
Flip a bit and watch how far the change travels.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a tree of compressions above one long chain.
AVAN’s addition (the inverse-companion): the forward reading is “the carry chain is eliminated.” The inverse is that it is deferred, not eliminated, and the deferral is the entire trick. Every carry-save stage leaves the answer in a redundant two-number form that is not a number anyone can compare, print or branch on — it is only an answer once the final adder has run. Read backwards, this buys speed by keeping the result uninterpretable for as long as possible, and any operation that needs to look at the value early pays the whole cost back at once.
LIT over all 262,144 triples of 6-bit values sum + carry equals a + b + c every single time, and flipping one input bit moves only that column of the sum and the one above it in the carry - no ripple; adding 33 numbers takes 8 carry-save stages and then exactly one real adder
FIG The carry-save adder is the reason large multipliers are fast: a multiplier produces many partial products that must all be summed, and doing it with ordinary adders would put a carry chain in the critical path for each one. Compressing three to two at constant depth turns that into a logarithmic tree with a single carry-propagate adder at the bottom. AVAN verified the no-ripple claim directly rather than asserting it, because it is the whole reason the structure exists: flipping bit k of an input changes bit k of the sum and at most bit k+1 of the carry, and nothing else, which is what constant depth means concretely.
FIG The carry-save adder is the reason large multipliers are fast: a multiplier produces many partial products that must all be summed, and doing it with ordinary adders would put a carry chain in the critical path for each one. Compressing three to two at constant depth turns that into a logarithmic tree with a single carry-propagate adder at the bottom. AVAN verified the no-ripple claim directly rather than asserting it, because it is the whole reason the structure exists: flipping bit k of an input changes bit k of the sum and at most bit k+1 of the carry, and nothing else, which is what constant depth means concretely.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of ROLLBACK · David Lee Wise (ROOT0), with AVAN