Analysis of Carry Propagation in Addition: An Elementary Approach
Our goal in this paper is to analyze carry propagation in addition using only elementary methods (that is, those not involving residues, contour integration, or methods of complex analysis). Our results concern the length of the longest carry chain when two independent uniformly distributed n-bit numbers are added. First, we show using just first- and second-moment arguments that the expected length Cn of the longest carry chain satisfies Cn = log2n + O(1). Second, we use a sieve (inclusion–exclusion) argument to give an exact formula for Cn. Third, we give an elementary derivation of an asymptotic formula due to Knuth, Cn = log2n + Φ(log2 n) + O((logn)4/n), where Φ(ν) is a bounded periodic function of ν, with period 1, for which we give both a simple integral expression and a Fourier series. Fourth, we give an analogous asymptotic formula for the variance Vn of the length of the longest carry chain: Vn = Ψ(log2 n) + O((logn)5/n), where Ψ(ν) is another bounded periodic function of ν, with period 1. Our approach can be adapted to addition with the “end-around” carry that occurs in the sign-magnitude and 1s-complement representations. Finally, our approach can be adapted to give elementary derivations of some asymptotic formulas arising in connection with radix-exchange sorting and collision-resolution algorithms, which have previously been derived using contour integration and residues.
© 2002 Elsevier Science
Nicholas Pippenger, Analysis of Carry Propagation in Addition: An Elementary Approach, Journal of Algorithms, Volume 42, Issue 2, February 2002, Pages 317-333.