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.