Minimizing the number of carries in addition

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

When numbers are added in base b in the usual way, carries occur. If two random, independent 1-digit numbers are added, then the probability of a carry is b-1/2b. Other choices of digits lead to less carries. In particular, if for odd b we use the digits {-(b-1)/2,-(b-3)/2,..,.. (b-1)/2} then the probability of carry is only b2-1/4b2. Diaconis, Shao, and Soundararajan conjectured that this is the best choice of digits, and proved that this is asymptotically the case when b = p is a large prime. In this note we prove this conjecture for all odd primes p.

Original languageEnglish (US)
Pages (from-to)562-566
Number of pages5
JournalSIAM Journal on Discrete Mathematics
Volume27
Issue number1
DOIs
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Carry
  • Modular addition

Fingerprint Dive into the research topics of 'Minimizing the number of carries in addition'. Together they form a unique fingerprint.

Cite this