Geodesic
On the number of iterations required by Von Neumann addition
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 187-206

Voir la notice de l'article provenant de la source Numdam

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.

Classification : 68Q25, 65Y20
Keywords: carry propagation, limit distributions, total variation distance, logarithmic periodicity, Gumbel distributions, discretization, large deviations 
@article{ITA_2001__35_2_187_0,
     author = {Gr\"ubel, Rudolf and Reimers, Anke},
     title = {On the number of iterations required by {Von} {Neumann} addition},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {187--206},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {2},
     year = {2001},
     mrnumber = {1862462},
     zbl = {1053.68051},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_2001__35_2_187_0/}
}
TY  - JOUR
AU  - Grübel, Rudolf
AU  - Reimers, Anke
TI  - On the number of iterations required by Von Neumann addition
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 187
EP  - 206
VL  - 35
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_2001__35_2_187_0/
LA  - en
ID  - ITA_2001__35_2_187_0
ER  - 
%0 Journal Article
%A Grübel, Rudolf
%A Reimers, Anke
%T On the number of iterations required by Von Neumann addition
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 187-206
%V 35
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_2001__35_2_187_0/
%G en
%F ITA_2001__35_2_187_0
Grübel, Rudolf; Reimers, Anke. On the number of iterations required by Von Neumann addition. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 2, pp. 187-206. http://geodesic.mathdoc.fr/item/ITA_2001__35_2_187_0/