## On the addition of binary numbers

3. R. P. Brent,
On the addition of binary numbers,
* IEEE Transactions on Computers* C-19 (1970), 758-759.
CR 12#20898.
Paper:
pdf (358K).

## Abstract

An upper bound is derived for the time required to add *n*-bit numbers
modulo 2^{n},
using circuit elements with a limited fan-in and
unit delay, and assuming that all numbers have the usual binary
encoding. The upper bound is within a factor 1 + o(1)
of Winograd's lower bound (which holds for all encodings)
as *n* -> infinity, and only
O(*n* log *n*) circuit elements are required.
## Comment

The same result was obtained independently by
Ofman [*Dokl. Akad. Nauk SSSR* 145 (1962) 48-51;
translation: * Sov. Phys. Dokl.* 7 (1968) 589-591].
Go to next publication

Return to Richard Brent's index page