Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Tight Bounds on Expected Time to Add Correctly and Add Mostly Correctly

Peter S. Gemmell and Mor Harchol

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-93-737
April 1993

http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-737.pdf

We consider the problem of adding two n-bit numbers which are chosen independently and uniformly at random where the adder is circuit of AND, OR, and NOT gates of fanin two.

The fastest currently known worst-case adder has running time log n + O(sqrt of log n).

We first present a circuit which adds at least 1 - epsilon fraction of pairs of numbers correctly and has running time log log (n\epsilon) + O(sqrt of log log (n\epsilon)).

We then prove that this running time is optimal.

Next we present a circuit which always produces the correct answer. We show this circuit adds two n-bit numbers from the uniform distribution in expected (1\2) log n + O(sqrt of log n) time, a speed up factor of two over the best possible running time of a worst-case adder.

We prove that this expected running time is optimal.


BibTeX citation:

@techreport{Gemmell:CSD-93-737,
    Author = {Gemmell, Peter S. and Harchol, Mor},
    Title = {Tight Bounds on Expected Time to Add Correctly and Add Mostly Correctly},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Apr},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6024.html},
    Number = {UCB/CSD-93-737},
    Abstract = {We consider the problem of adding two <i>n</i>-bit numbers which are chosen independently and uniformly at random where the adder is circuit of AND, OR, and NOT gates of fanin two. <p>The fastest currently known worst-case adder has running time log <i>n</i> + <i>O</i>(sqrt of log <i>n</i>). <p>We first present a circuit which adds at least 1 - epsilon fraction of pairs of numbers correctly and has running time log log (<i>n</i>\epsilon) + <i>O</i>(sqrt of log log (<i>n</i>\epsilon)). <p>We then prove that this running time is optimal. <p>Next we present a circuit which always produces the correct answer. We show this circuit adds two <i>n</i>-bit numbers from the uniform distribution in expected (1\2) log <i>n</i> + <i>O</i>(sqrt of log <i>n</i>) time, a speed up factor of two over the best possible running time of a worst-case adder. <p>We prove that this expected running time is optimal.}
}

EndNote citation:

%0 Report
%A Gemmell, Peter S.
%A Harchol, Mor
%T Tight Bounds on Expected Time to Add Correctly and Add Mostly Correctly
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-93-737
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6024.html
%F Gemmell:CSD-93-737