Analysis of Carry Propagation in Addition: An Elementary Approach

✍ Scribed by Nicholas Pippenger

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 114 KB
• Volume: 42
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2002.1216

✦ Synopsis

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 C n of the longest carry chain satisfies C n = log 2 n + O 1 . Second, we use a sieve (inclusion-exclusion) argument to give an exact formula for C n . Third, we give an elementary derivation of an asymptotic formula due to Knuth, C n = log 2 n + log 2 n + O log n 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 V n of the length of the longest carry chain: V n = log 2 n + O log n 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 radixexchange sorting and collision-resolution algorithms, which have previously been derived using contour integration and residues.  2002 Elsevier Science (USA)