KOGGE-STONE the carry as a parallel prefix — log-depth, the fastest wide adder
Carry-lookahead (dart 377) says every carry is a formula; Kogge-Stone says: compute all those formulas as a parallel prefix scan. Combine the generate/propagate pairs with an associative operator — (g,p) ∘ (g′,p′) = (g | (p & g′), p & p′) — in a tree of depth log₂n, and every carry falls out at once. It is the classic parallel-prefix (scan) adder: minimum depth, at the cost of many wires. The same scan primitive that computes prefix sums (batch 40) computes carries here — addition is a scan whose operator is the carry rule.
THE TECHNIQUE prefix scan of (g,p) with (g,p)∘(g′,p′) = (g|(p&g′), p&p′)
The demo combines two generate/propagate cells with the Kogge-Stone operator — the associative step that a log-depth tree is built from: live demo
HISTORY & CREDIT Kogge & Stone, 1973
“A faster adder is a cleverer circuit.” — it is a scan: the carry rule is associative, so a prefix tree of depth log n computes every carry in parallel. Addition is a scan. cited
1973 · Peter Kogge & Harold Stone — the parallel-prefix formulation (for recurrences generally). the operator · (g,p)∘(g′,p′) is associative — so a scan applies. kin · the prefix-sum scan (batch 40, dart 322) — same primitive, carry-rule operator.
The carry rule is associative, so every carry is a prefix of one scan, resolved in log depth. Addition, revealed as a scan. Kogge–Stone 1973
RECOMMEND FOR I-13 the prefix combine, on the compiler
On the canonical compiler, the Kogge-Stone combine of a generating cell (g0=1,p0=0) with a propagating cell (g1=0,p1=1) gives (g=1,p=0) — the carry propagated through the operator:
$ i13 run c_koggestone.i13 # (g,p) o (g',p') = (g|(p&g'), p&p')
RUN OK · 18 step(s) · peak stack 3 · call depth 0
g = 1 p = 0 -- the associative prefix step; a log-depth tree of these is the adder
Recommend: Kogge-Stone is the carry as a parallel prefix — addition revealed as a scan whose operator is the carry rule — and i13 runs the associative combine. Not a keeper (it is the fastest way to the same sum — a resource/depth property, B40-excluded; and the scan primitive itself was covered in batch 40). The dart that ties the carry to the prefix sum: the same associative scan, a different monoid.