Minimizing the number of carries in addition

Noga Alon

doi:10.1137/120890612

Minimizing the number of carries in addition

Noga Alon

Research output: Contribution to journal › Article › peer-review

3 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 b²-1/4b². 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 language	English (US)
Pages (from-to)	562-566
Number of pages	5
Journal	SIAM Journal on Discrete Mathematics
Volume	27
Issue number	1
DOIs	https://doi.org/10.1137/120890612
State	Published - 2013
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Carry
Modular addition

Access to Document

10.1137/120890612

Cite this

@article{771ed85ca5c648469f1d1ccc293ee973,

title = "Minimizing the number of carries in addition",

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.",

keywords = "Carry, Modular addition",

author = "Noga Alon",

year = "2013",

doi = "10.1137/120890612",

language = "English (US)",

volume = "27",

pages = "562--566",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - Minimizing the number of carries in addition

AU - Alon, Noga

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Carry

KW - Modular addition

UR - http://www.scopus.com/inward/record.url?scp=84876932372&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876932372&partnerID=8YFLogxK

U2 - 10.1137/120890612

DO - 10.1137/120890612

M3 - Article

AN - SCOPUS:84876932372

SN - 0895-4801

VL - 27

SP - 562

EP - 566

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

Minimizing the number of carries in addition

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this