Analysis of Carry Propagation in Addition: An Elementary Approach

Document Type

Article

Department

Mathematics (HMC)

Publication Date

2-2002

Abstract

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.

Rights Information

© 2002 Elsevier Science

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Link to Full Text

Share

COinS