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).


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.


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