On the number of iterations required by von Neumann addition

R. Grübel; Anke Reimers

doi:10.1051/ita:2001115

On the number of iterations required by von Neumann addition

R. Grübel^*
, Anke Reimers

^*Corresponding author for this work

Faculty of Mathematics and Physics

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

Abstract

We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.

Original language	English
Pages (from-to)	187-206
Number of pages	20
Journal	RAIRO - Theoretical Informatics and Applications
Volume	35
Issue number	2
DOIs	https://doi.org/10.1051/ita:2001115 https://doi.org/10.15488/2694
Publication status	Published - 2001

Keywords

Carry propagation
Discretization
Gumbel distributions
Large deviations
Limit distributions
Logarithmic periodicity
Total variation distance

ASJC Scopus subject areas

Software
General Mathematics
Computer Science Applications

Access to Document

http://www.numdam.org/item/ITA_2001__35_2_187_0/Licence: Other

Cite this

@article{85f394edce8744c0b2a8f4d0aafa1bca,

title = "On the number of iterations required by von Neumann addition",

abstract = "We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.",

keywords = "Carry propagation, Discretization, Gumbel distributions, Large deviations, Limit distributions, Logarithmic periodicity, Total variation distance",

author = "R. Gr{\"u}bel and Anke Reimers",

year = "2001",

doi = "10.1051/ita:2001115",

language = "English",

volume = "35",

pages = "187--206",

journal = "RAIRO - Theoretical Informatics and Applications",

issn = "0988-3754",

publisher = "EDP Sciences",

number = "2",

}

TY - JOUR

T1 - On the number of iterations required by von Neumann addition

AU - Grübel, R.

AU - Reimers, Anke

PY - 2001

Y1 - 2001

N2 - We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.

AB - We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.

KW - Carry propagation

KW - Discretization

KW - Gumbel distributions

KW - Large deviations

KW - Limit distributions

KW - Logarithmic periodicity

KW - Total variation distance

UR - https://www.scopus.com/pages/publications/17944371994

U2 - 10.1051/ita:2001115

DO - 10.1051/ita:2001115

M3 - Article

AN - SCOPUS:17944371994

SN - 0988-3754

VL - 35

SP - 187

EP - 206

JO - RAIRO - Theoretical Informatics and Applications

JF - RAIRO - Theoretical Informatics and Applications

IS - 2

ER -

On the number of iterations required by von Neumann addition

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this