Research · Papers · Adders, counters and the heap law · ML-047
Multiplicative complexity of the three-product carry cell
Cascade of x+y+z+w+c₀+2c₁ = s+2c₀′+4c₁′ (3 ANDs) computes sum of 4 unsigned n-bit integers in exactly 3n ANDs, matching (K−1)·n for K = 4
Published 2026-08-29
For everyone
Plain summary
The study-04 carry cell works as claimed: it adds four n-bit integers using 3n AND operations. That total appeared to beat prior art only because the author compared it to a 4n figure from Cirbo/STACS-2026, which counted total binary gates rather than ANDs alone. Standard carry-save compression already achieves 3n ANDs for four operands. Exhaustive checks through n <= 3 and symbolic counts through n = 64 confirm the circuit is sound, but it matches the standard baseline instead of improving on it. The improvement claim is withdrawn.
Result
Under the XOR-free/AND-charged cost model, the six-input cell satisfies
x+y+z+w+c₀+2c₁ = s+2c₀′+4c₁′
across all 64 assignments with three AND gates. Its cascade computes the full-precision sum of four unsigned n-bit integers in exactly 3n ANDs. The standard carry-save baseline requires (K−1)·n ANDs, yielding 3n for K = 4. The measured delta is zero across all tested widths: n = 1,2,3,4,5,6,8,12,16,32,64. The improvement route is PROVED DEAD.
Setting and definitions
Full-precision addition retains all carries generated above bit n−1. The carry-save baseline applies single-AND full adders in a Dadda compression tree terminated by a ripple-carry adder. Multiplicative complexity charges unit cost per AND gate; XOR gates are free.
Method
The audit verified the cell identity across all 64 input assignments, verified the cascaded adder exhaustively for n ≤ 3, and derived exact symbolic AND counts through n = 64 across two independent paths with structural common subexpression elimination. Verification scripts, certificates, and raw audit output are available in this paper's downloadable evidence pack; the baseline reference is MF-076.
Discussion
The prior 4n baseline came from the Cirbo/STACS-2026 add_sum_n_weighted_bits generator, which minimizes total binary gate count rather than multiplicative complexity. The three-product carry cell remains structurally sound, and the constructive contributions of MF-002 stand unretracted. However, against the correct carry-save baseline, the design yields parity rather than an asymptotic or constant-factor reduction in multi-operand adder multiplicative complexity.
For everyone — the takeaway
What this means
The new circuit adds four numbers correctly and uses three AND operations per bit slice. Standard textbook methods use the exact same number of AND operations. The original claim of a speedup came from comparing an AND count against a total gate count. The circuit is a valid alternative implementation, but it does not reduce the nonlinear cost of multi-operand addition.
Attribution and prior art
Prior art: The claimed improvement has been withdrawn: Cirbo (STACS-2026) optimized total binary gates, whereas the carry-save construction is the relevant comparison for AND-gate count.
Register references
- ML-047
zkgolf-transfer-studies/08-multiop-addition-audit/multiop_addition_audit.py(SHA-256bc4f4305…143d)multiop_addition_audit_certificate.json(SHA-25626fabd01…59b6)AUDIT.mdzkgolf-transfer-studies/04-andcount-optimization/REPORT.md, §1–3- Cirbo/STACS-2026
- MF-076; MF-077
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 3 of 3 receipt files bundled (7 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.