Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 187-206 |
| Seitenumfang | 20 |
| Fachzeitschrift | RAIRO - Theoretical Informatics and Applications |
| Jahrgang | 35 |
| Ausgabenummer | 2 |
| Publikationsstatus | Veröffentlicht - 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.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Software
- Mathematik (insg.)
- Allgemeine Mathematik
- Informatik (insg.)
- Angewandte Informatik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: RAIRO - Theoretical Informatics and Applications, Jahrgang 35, Nr. 2, 2001, S. 187-206.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › 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 -