Research · Papers · Adders, counters and the heap law · MF-077
Multiplicative complexity of four-operand addition
x+y+z+w+c₀+2c₁ = s+2c₀′+4c₁′ using 3 AND gates; full-precision sum of four n-bit integers uses 3n ANDs
Published 2026-08-29
For everyone
Plain summary
A three-product carry cell adds four input bits and two incoming carry bits, producing one sum bit and two outgoing carry bits. It satisfies its arithmetic identity across all 64 possible input combinations using 3 AND operations. Cascading this cell across n columns sums four n-bit unsigned integers using 3n ANDs, verified by replay for n≤3.
An earlier report claimed a 25% improvement by comparing this 3n figure against a 4n result from the Cirbo/STACS-2026 add_sum_n_weighted_bits generator. That generator minimizes total binary gates rather than multiplicative complexity. Standard carry-save addition already achieves 3n ANDs across all tested widths. The construction fixes that specific generator's gate count, but it matches rather than beats the standard baseline for multi-operand addition.
Result
The six-input carry cell satisfies the arithmetic identity
x+y+z+w+c₀+2c₁ = s+2c₀′+4c₁′
across all 64 input assignments using three AND gates. Cascading the cell computes the full-precision sum of four n-bit integers in 3n ANDs.
Evaluated against the standard carry-save baseline from MF-076 across
n = 1,2,3,4,5,6,8,12,16,32,64,
the AND-count delta is zero. Both methods use 3n ANDs at every evaluated width. The construction ties the standard carry-save baseline.
Setting and definitions
The cell takes four operand bits x,y,z,w and two carry bits c₀,c₁ with weights 1 and 2. It outputs sum bit s and carry bits c₀′,c₁′ with weights 1, 2, and 4.
The four-operand cascade applies the cell column-by-column across the bit width. Multiplicative complexity counts AND gates while treating XOR as free. The baseline is standard carry-save addition: Dadda column compression using one-AND full adders followed by a ripple-carry final adder.
Method
Verification used the MF-076 certificate. Exhaustive evaluation of the 64-row truth table confirmed the three-AND cell identity with zero failures. The 3n cascade was checked exhaustively for n≤3. Exact symbolic AND counts were verified under free-XOR with structural common-subexpression elimination using two independent evaluation paths in one test harness.
Evaluations spanned n = 1,2,3,4,5,6,8,12,16,32,64; both the audited cascade and the carry-save baseline used 3n ANDs. The audit scripts, verification certificates, and superseded external framing are included in this paper's downloadable evidence pack.
Discussion
The cell construction is correct, but its comparative advantage was overstated. The previously reported 25% improvement compared 3n against the 4n count from the Cirbo/STACS-2026 add_sum_n_weighted_bits generator, which optimizes total binary gates rather than AND operations. Because standard carry-save addition also achieves 3n ANDs across all tested widths, the actual delta against the standard baseline is zero.
The cell fixes the nonlinear count of that particular compiler, but it does not lower the multiplicative complexity of multi-operand addition. The limits ledger marks this optimization path as PROVED DEAD. This update scopes the external framing of MF-002 without affecting its nine-product constructive content, which made no optimality claim. The register records no broader novelty claim for MF-077.
For everyone — the takeaway
What this means
The carry cell is mathematically sound and passes all verification tests across its 64 inputs and small-width cascades. However, standard adder designs already use 3n AND gates to add four numbers. The earlier 25% savings appeared only because it was compared against a tool optimizing for a different metric. The circuit works as designed, but it matches rather than improves upon standard methods.
Attribution and prior art
Prior art: The claimed 25% improvement is revised: standard carry-save baselines also achieve 3n AND gates, as the Cirbo/STACS generator’s 4n figure optimizes total gates instead. Only the nonlinear gate comparison specific to the Cirbo/STACS generator remains valid.
Register references
- Entry: MF-077.
- Receipts:
zkgolf-transfer-studies/08-multiop-addition-audit/multiop_addition_audit.py(SHA-256bc4f4305…143d);multiop_addition_audit_certificate.json(SHA-25626fabd01…59b6);AUDIT.md; superseded framing inzkgolf-transfer-studies/04-andcount-optimization/REPORT.md§1–3. - Named comparison work: the Cirbo/STACS-2026
add_sum_n_weighted_bitsgenerator. - Prior-art position: the register does not record this.
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 1 of 1 receipt files bundled (10 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.