On the Addition of Binary Numbers

Abstract

An upper bound is derived for the time required to add 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 + ε) of Winograd's lower bound (which holds for all encodings), where ε→0 as n→∞, and only O(n log n) circuit elements are required.