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.
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/item/ITA_2001__35_2_187_0/
[1] Probability and Measure, 2nd Ed. Wiley, New York (1986). | MR | Zbl
,[2] Preliminary discussion of the logical design of an electronic computing instrument. Inst. for Advanced Study Report (1946). Reprinted in John von Neumann Collected Works, Vol. 5. Pergamon Press, New York (1961). | MR
, and ,[3] A stochastically quasi-optimal algorithm. Preprint (1999).
, and ,[4] Die mittlere Additionsdauer eines Paralleladdierwerks. Acta Inform. 2 (1973) 283-291. | MR | Zbl
,[5] Introduction to Algorithms. MIT Press, Cambridge, USA (1997). | MR | Zbl
, and ,[6] Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 (1995) 3-58. | MR | Zbl
, and ,[7] Algorithmische Zahlentheorie. Vieweg, Braunschweig (1996). | Zbl
,[8] Hoare's selection algorithm: A Markov chain approach. J. Appl. Probab. 35 (1998) 36-45. | Zbl
,[9] On the median-of- version of Hoare’s selection algorithm. RAIRO: Theoret. Informatics Appl. 33 (1999) 177-192. | Numdam | Zbl
,[10] Asymptotic distribution theory for Hoare's selection algorithm. Adv. Appl. Probab. 28 (1996) 252-269. | Zbl
and ,[11] The Art of Computer Programming, Vol. 3, Sorting and Searching. Addison-Wesley, Reading (1973). | MR | Zbl
,[12] The average time for carry propagation. Nederl. Akad. Wetensch. Indag. Math. 40 (1978) 238-242. | MR | Zbl
,[13] Concentration, in Probabilistic Methods for Algorithmic Discrete Mathematics, edited by M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed. Springer, Berlin (1998). | Zbl
,[14] Large deviations for Quicksort. J. Algorithms 21 (1996) 476-507. | MR | Zbl
and ,[15] A limiting distribution for quicksort. RAIRO: Theoret. Informatics Appl. 23 (1989) 335-343. | Numdam | MR | Zbl
,[16] Extreme Values, Regular Variation and Point Processes. Springer, New York (1987). | MR | Zbl
,[17] A limit theorem for “Quicksort”. RAIRO: Theoret. Informatics Appl. 25 (1991) 85-100. | Numdam | Zbl
,[18] Real and Complex Analysis, 2nd Ed. Tata McGraw-Hill, New Delhi (1974). | MR | Zbl
,[19] Computer Number Systems & Arithmetic. Prentice-Hall, New Jersey (1985). | Zbl
,[20] An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading (1996). | Zbl
and ,[21] Effiziente Algorithmen für grundlegende Funktionen. B.G. Teubner, Stuttgart (1996). | MR | Zbl
,