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

We first present a circuit that adds at least 1 - epsilon fraction of pairs of numbers correctly and has running time loglog(n/epsilon) + O(sqrt(loglog(n/epsilon))). We then prove that this running time is optimal.

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