Research · Papers · Adders, counters and the heap law · MF-076
On the multiplicative complexity of adding K unsigned n-bit integers
Full-precision sum of K unsigned n-bit integers: (K−1)·n ANDs asymptotically, (K−1)·n for power-of-two K (n ≥ 1), K − HW(K) at n=1
Published 2026-08-29
For everyone
Plain summary
Adding several unsigned numbers requires routing carry bits into higher columns. A full-precision sum retains all carry positions without dropping overflow. This entry records a carry-save baseline that compresses columns with full adders down to two rows, then adds those rows with a standard ripple-carry adder. Under an AND-cost model where XORs are free, the circuit uses (K−1)·n AND gates asymptotically for K inputs of width n. When K is a power of two, the cost is exactly (K−1)·n for every width n. At width n=1, the count reduces to K − HW(K), where HW(K) is the number of set bits in K's binary representation. Small-width test runs verified the count across tested parameter pairs, and an exhaustive replay across all inputs for K=4, n≤3 produced zero errors. The result establishes an explicit baseline for multi-operand adder comparisons; it claims no algorithmic novelty and does not establish optimality for general K.
Result
In the XOR-free, AND-charged multiplicative complexity model, greedy column compression with full adders implemented via the one-AND majority identity
MAJ(a,b,c)=((a⊕c)(b⊕c))⊕c,
reducing to two rows followed by a ripple-carry adder, computes the exact full-precision sum of K unsigned n-bit integers using (K−1)·n ANDs asymptotically.
When K is a power of two, the circuit uses exactly (K−1)·n ANDs for every n ≥ 1. At n=1, the count equals K − HW(K), matching the Boyar–Peralta multiplicative complexity for the K-bit Hamming-weight function.
Setting and definitions
Let K be the number of unsigned operands, each of width n. The goal is their exact full-precision sum. Costs are measured by the number of AND gates; XOR operations are free.
Full adders compress each bit column greedily until two rows remain, and a ripple-carry adder finishes the summation. HW(K) denotes the Hamming weight of K (the count of ones in its binary representation). Each full-adder carry bit uses the one-AND majority form MAJ(a,b,c)=((a⊕c)(b⊕c))⊕c.
Method
The result was derived via symbolic gate counts on the carry-save tree and confirmed by exhaustive small-width execution. The audit tested the parameter grid:
K ∈ {2,3,4,5,6,7,8,16}
n ∈ {1,2,4,8,16,32}.
For K=4 and n≤3, an exhaustive check evaluated all possible input assignments with zero mismatches. The n=1 gate counts matched the known K − HW(K) values.
The execution scripts, audit logs, and verification certificates are available in this paper's downloadable evidence pack.
Discussion
MF-076 provides the reference AND count against which multi-operand adder architectures should be measured. The entry makes no claim of architectural novelty, and the register records no specific prior-art attribution for the baseline circuit itself.
Exact multiplicative complexity remains open for general K ≥ 3. The carry-save construction establishes the upper bound (K−1)·n on tested values, degenerating to K − HW(K) at n=1. By contrast, the best proven circuit lower bound is approximately n + ⌈log₂K⌉ − 1, leaving the gap n+1 ≤ MC ≤ 3n at K=4. The bit-counting floor (K−1)n − ⌈log₂K⌉ reflects structural full-adder/half-adder counting rather than a strict circuit lower bound and fails to be tight at n=1. Proving optimality of (K−1)·n for general K ≥ 3 will require new lower-bound techniques.
For everyone — the takeaway
What this means
This result provides a standard reference cost for adding K numbers of n bits without dropping carry bits. The carry-save approach needs roughly (K−1)·n AND gates, and that number is exact at all widths whenever K is a power of two. For single-bit inputs, the gate count simplifies to K − HW(K). Any proposed adder circuit aiming for low AND counts should compare itself against this baseline under identical costing rules. Whether a circuit can beat this bound for general K remains an open theoretical problem.
Register references
- Entry: MF-076.
- 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. - Named prior-art work: Boyar–Peralta for the
K − HW(K)Hamming-weight complexity. - Prior-art position for the construction: not recorded in register.
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-30
- 2026-08-27Summing `K` unsigned `n`-bit integers using full-adder column compression requires exactly `(K−1)·n` AND gates when `K` is a power of two (and asymptotically for all `K`). At `n=1`, this matches the Boyar–Peralta multiplicative complexity `K − HW(K)` for the Hamming-weight function, confirmed via exact symbolic counts and exhaustive testing.
- 2026-08-29Published on this site.
- 2026-08-30Superseded on 2026-08-30: while the FullAdd frontier construction remains a valid upper bound, any universal optimality claim is false and is replaced by the composed exact theorem MF-099, supported by internal reports and replay checks.