Alexander Izsak

Harvey Mudd College Mathematics 2007

mugshot
Thesis Proposal: Special Cases of Carry Propagation
Final Report: Final Report
Thesis Advisor: Prof. Nick Pippenger
Second Reader: Prof. Ran Libeskind-Hadas

Special Cases of Carry Propagation

Addition is an extremely fundamental and popular operator. Yet mathematics lacked a good estimation for the asymptotic behavior shown by the mean amount of carries that propagate when adding numbers until until Donald Knuth provided one in 1978. Nick Pippenger reproved this formula without relying on complex analysis, as was the case for Knuth. I intend to extend this method to finding expressions for mean number and variance of carry propagations under certain multiplications and may expand upon Pippenger's analysis to explore other algorithmic problems as well.