Deriving a carry-lookahead adder from ripple-carry in Lean 4, with formally verified steps
satnam6502 · x · 2026-10-15
satnam6502 published a Lean 4 derivation transforming a ripple-carry adder into a carry-lookahead adder built on Sklansky's parallel prefix network, with every transformation formally verified; full code and proofs are open.
- Minimal spec: the carry into column i is just overflow of the low i columns plus carry-in
- Derivation chain: full-adder law → scan lemma → scan fusion → scan1 → parallel prefix, depth dropping from n to ⌈log₂(n+1)⌉
- gp(a,b) = (a∧b, a⊕b) encodes each column's generate/propagate bits
- Three diagrams show the structural evolution: carry chain → generate/propagate → scan of (g,p) pairs
More from Research
- Domingos Cites New Result Claiming RL Is 'Basically Useless' vs Supervised Learning — pmddomingos · 2026-10-23
- Wolfram Opens Rule 30 Prizes to AIs: $30,000 for Three Open Problems — cephaloform · 2026-10-23
- Stanford and Databricks use AI agents to reproduce medical findings and test analytical robustness — ChengleiSi · 2026-10-23
- EMNLP paper: diffusion LMs internally encode latent denoising timestep representations — gsarti_ · 2026-10-23
- KU Leuven and VIB open two Group Leader professorships in AI for Biology, start 2027 — jpillowtime · 2026-10-23
- Subspace Tuning curbs LLM catastrophic forgetting by freezing principal singular directions — scottniekum · 2026-10-23