Details
| Original language | English |
|---|---|
| Pages (from-to) | 187-206 |
| Number of pages | 20 |
| Journal | RAIRO - Theoretical Informatics and Applications |
| Volume | 35 |
| Issue number | 2 |
| Publication status | Published - 2001 |
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
ASJC Scopus subject areas
- Computer Science(all)
- Software
- Mathematics(all)
- General Mathematics
- Computer Science(all)
- Computer Science Applications
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: RAIRO - Theoretical Informatics and Applications, Vol. 35, No. 2, 2001, p. 187-206.
Research output: Contribution to journal › Article › Research › peer review
}
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 - http://www.scopus.com/inward/record.url?scp=17944371994&partnerID=8YFLogxK
U2 - 10.1051/ita:2001115
DO - 10.1051/ita:2001115
M3 - Article
AN - SCOPUS:17944371994
VL - 35
SP - 187
EP - 206
JO - RAIRO - Theoretical Informatics and Applications
JF - RAIRO - Theoretical Informatics and Applications
SN - 0988-3754
IS - 2
ER -