CARRY-SAVE do not propagate the carry — save it in a second number, add it later
When you must add many numbers (a multiplier's partial products), propagating carries at every step is waste. The carry-save adder refuses: adding three numbers, it produces two — a sum vector (a ⊕ b ⊕ c) and a carry vector (the carries, un-propagated) — whose ordinary sum equals the original three (with the carry vector shifted left by one). The carry is deferred, not resolved, so each step is carry-free and instant; only the very last step pays the propagation once. It is the “3:2 compressor” at the heart of every fast multiplier (Wallace, Dadda trees).
THE TECHNIQUE a+b+c → (a⊕b⊕c) + (carries « 1); defer the carry
The demo compresses three numbers to two — a sum vector and a carry vector — whose sum is the original: 5+6+7=18: live demo
HISTORY & CREDIT von Neumann · Wallace 1964
“Every addition must resolve its carry.” — carry-save keeps the carry in a second number and adds many operands carry-free, paying the propagation only once at the end. cited
the trick · 3 numbers → 2 (sum vector + carry vector); no carry propagation per step. 1964 · Chris Wallace — the Wallace tree of carry-save adders for fast multiplication (Dadda, 1965, refined it). redundant · the two-vector form is a redundant number representation — the carry lives on, deferred.
Keep the carry in a second number and add many at once; pay the propagation just once, at the end. The deferred carry. Wallace 1964
RECOMMEND FOR I-13 the deferred carry, on the compiler
On the canonical compiler, 5+6+7 compresses to sum-vector 4 and carry-vector 7, whose sum 4+(7«1)=18 is the original:
$ i13 run c_carrysave.i13 # 3:2 : s=a^b^c, cy=(a&b)|(b&c)|(a&c)
RUN OK · 30 step(s) · peak stack 3 · call depth 0
s = 4 cy = 7
result = 18 -- s + (cy<<1) = 5+6+7, the carry deferred to the last step
Recommend: carry-save is the thread's central move made literal — keep the carry in a second number, add it later — and i13 compresses 5+6+7 to a sum/carry pair summing to 18. Tempting as a keeper (it is the carry carried), but honestly not: deferring the carry is a speed/resource mechanism (its final value is bit-identical to a plain sum), and the redundant two-vector form is a resource encoding — the B40 exclusion. Still, the closest hardware echo of the thread's “a fold without a carry is one-way”: here the carry is saved so the work can go on.