THE FOLD / BOSS / THE RAID / THE CARRY LOOKAHEAD
THE CARRY LOOKAHEAD
generate and propagate, computed all at once
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Each bit either generates a carry or propagates one it receives. Written that way, the carries unroll into a formula with no chain in it.
LIT verified live. the lookahead adder agrees with a ripple adder on all 65,536 byte pairs; and the depth is logarithmic rather than linear — 4 against 8 at a byte, 7 against 64 at a word, roughly nine times shallower — though the widest gate then needs 16 inputs, which is why real adders group in fours.
LIT verified live. the lookahead adder agrees with a ripple adder on all 65,536 byte pairs; and the depth is logarithmic rather than linear — 4 against 8 at a byte, 7 against 64 at a word, roughly nine times shallower — though the widest gate then needs 16 inputs, which is why real adders group in fours.
2 HOW IT WAS WEAVED · AI + HUMAN
Carry-lookahead is the foundational trick of fast arithmetic hardware, and the generate/propagate formulation is what makes the parallel prefix adders — Kogge-Stone, Brent-Kung, Sklansky — possible at all.
AVAN (AI) verified the equivalence exhaustively rather than trusting the algebra, and reported the fan-in alongside the depth, because the depth figure alone makes the technique look free. It is not: the unrolled formula for bit k has k+1 terms, and gate delay grows with input count.
AVAN (AI) verified the equivalence exhaustively rather than trusting the algebra, and reported the fan-in alongside the depth, because the depth figure alone makes the technique look free. It is not: the unrolled formula for bit k has k+1 terms, and gate delay grows with input count.
3 ONE DIMENSION
Depth against width, ripple beside lookahead.
4 TWO DIMENSIONS · INTERACTIVE
Watch the carry arrive everywhere at once.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that lookahead removes the carry chain. The inverse is that it converts a long thin problem into a short fat one, and fat has its own limit. The widest term at 64 bits would need a 64-input gate, which no technology builds — so real designs cut the formula into groups and rebuild a chain between them, arriving back at a shallow ripple. Read backwards, the logarithmic depth is an idealisation that survives only until fan-in is priced.
LIT the lookahead adder agrees with a ripple adder on all 65,536 byte pairs; and the depth is logarithmic rather than linear - 4 against 8 at a byte, 7 against 64 at a word, roughly nine times shallower - though the widest gate then needs 16 inputs, which is why real adders group in fours
FIG Carry-lookahead is the foundational trick of fast arithmetic hardware, and the generate/propagate formulation is what makes the parallel prefix adders - Kogge-Stone, Brent-Kung, Sklansky - possible at all. AVAN verified the equivalence exhaustively rather than trusting the algebra, and reported the FAN-IN alongside the depth, because the depth figure alone makes the technique look free. It is not: the unrolled formula for bit k has k+1 terms, and gate delay grows with input count.
FIG Carry-lookahead is the foundational trick of fast arithmetic hardware, and the generate/propagate formulation is what makes the parallel prefix adders - Kogge-Stone, Brent-Kung, Sklansky - possible at all. AVAN verified the equivalence exhaustively rather than trusting the algebra, and reported the FAN-IN alongside the depth, because the depth figure alone makes the technique look free. It is not: the unrolled formula for bit k has k+1 terms, and gate delay grows with input count.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RAID · David Lee Wise (ROOT0), with AVAN