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 2n,
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