# 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

### , 1993

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

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.

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}, Year= {1993}, Month= {Apr}, Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/6024.html %F Gemmell:CSD-93-737