Graduation Year
2007
Document Type
Open Access Senior Thesis
Degree Name
Bachelor of Science
Department
Mathematics
Reader 1
Nicholas Pippenger
Reader 2
Ran Libeskind-Hadas (CS)
Abstract
The average time necessary to add numbers by local parallel computation is directly related to the length of the longest carry propagation chain in the sum. The mean length of longest carry propagation chain when adding two independent uniform random n bit numbers is a well studied topic, and useful approximations as well as an exact expression for this value have been found. My thesis searches for similar formulas for mean length of the longest carry propagation chain in sums that arise when a random n-digit number is multiplied by a number of the form 1 + 2d. Letting Cn, d represent the desired mean, my thesis details how to find formulas for Cn,d using probability, generating functions and linear algebra arguments. I also find bounds on Cn,d to prove that Cn,d = log2 n + O(1), and show work towards finding an even more exact approximation for Cn,d.
Recommended Citation
Izsak, Alexander, "Special Cases of Carry Propagation" (2007). HMC Senior Theses. 197.
https://scholarship.claremont.edu/hmc_theses/197
