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.
Keywords :
Addition, binary numbers, computational complexity, group multiplication, logic circuits, logical design.; Australia; Computational complexity; Computer science; Delay effects; Encoding; Logic circuits; Mathematical model; Terminology; Upper bound; Addition, binary numbers, computational complexity, group multiplication, logic circuits, logical design.;
