On the number of iterations required by Von Neumann addition

Rudolf Grübel; Anke Reimers

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2001)

  • Volume: 35, Issue: 2, page 187-206
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Grübel, Rudolf, and Reimers, Anke. "On the number of iterations required by Von Neumann addition." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 35.2 (2001): 187-206. <http://eudml.org/doc/92661>.

@article{Grübel2001,
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.},
author = {Grübel, Rudolf, Reimers, Anke},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {carry propagation; limit distributions; total variation distance; logarithmic periodicity; Gumbel distributions; discretization; large deviations; multiprecision arithmetic},
language = {eng},
number = {2},
pages = {187-206},
publisher = {EDP-Sciences},
title = {On the number of iterations required by Von Neumann addition},
url = {http://eudml.org/doc/92661},
volume = {35},
year = {2001},
}

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
PB - EDP-Sciences
VL - 35
IS - 2
SP - 187
EP - 206
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.
LA - eng
KW - carry propagation; limit distributions; total variation distance; logarithmic periodicity; Gumbel distributions; discretization; large deviations; multiprecision arithmetic
UR - http://eudml.org/doc/92661
ER -

References

top
  1. [1] P. Billingsley, Probability and Measure, 2nd Ed. Wiley, New York (1986). Zbl0649.60001MR830424
  2. [2] A.W. Burks, H.H. Goldstine and J. von Neumann, 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). MR22442
  3. [3] P. Chassaing, J.F. Marckert and M. Yor, A stochastically quasi-optimal algorithm. Preprint (1999). Zbl1084.68145
  4. [4] V. Claus, Die mittlere Additionsdauer eines Paralleladdierwerks. Acta Inform. 2 (1973) 283-291. Zbl0304.68048MR366092
  5. [5] Th.H. Cormen, Ch.E. Leiserson and R.L. Rivest, Introduction to Algorithms. MIT Press, Cambridge, USA (1997). Zbl1047.68161MR1066870
  6. [6] Ph. Flajolet, X. Gourdon and Ph. Dumas, Mellin transforms and asymptotics: Harmonic sums. Theoret. Comput. Sci. 144 (1995) 3-58. Zbl0869.68057MR1337752
  7. [7] O. Forster, Algorithmische Zahlentheorie. Vieweg, Braunschweig (1996). Zbl0870.11001
  8. [8] R. Grübel, Hoare’s selection algorithm: A Markov chain approach. J. Appl. Probab. 35 (1998) 36-45. Zbl0913.60059
  9. [9] R. Grübel, On the median-of- k version of Hoare’s selection algorithm. RAIRO: Theoret. Informatics Appl. 33 (1999) 177-192. Zbl0946.68058
  10. [10] R. Grübel and U. Rösler, Asymptotic distribution theory for Hoare’s selection algorithm. Adv. Appl. Probab. 28 (1996) 252-269. Zbl0853.60033
  11. [11] D.E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching. Addison-Wesley, Reading (1973). Zbl0302.68010MR445948
  12. [12] D.E. Knuth, The average time for carry propagation. Nederl. Akad. Wetensch. Indag. Math. 40 (1978) 238-242. Zbl0382.10035MR497803
  13. [13] C. McDiarmid, Concentration, in Probabilistic Methods for Algorithmic Discrete Mathematics, edited by M. Habib, C. McDiarmid, J. Ramirez–Alfonsin and B. Reed. Springer, Berlin (1998). Zbl0927.60027
  14. [14] C. McDiarmid and R.B. Hayward, Large deviations for Quicksort. J. Algorithms 21 (1996) 476-507. Zbl0863.68059MR1417660
  15. [15] M. Régnier, A limiting distribution for quicksort. RAIRO: Theoret. Informatics Appl. 23 (1989) 335-343. Zbl0677.68072MR1020478
  16. [16] S.I. Resnick, Extreme Values, Regular Variation and Point Processes. Springer, New York (1987). Zbl0633.60001MR900810
  17. [17] U. Rösler, A limit theorem for “Quicksort”. RAIRO: Theoret. Informatics Appl. 25 (1991) 85-100. Zbl0718.68026
  18. [18] W. Rudin, Real and Complex Analysis, 2nd Ed. Tata McGraw-Hill, New Delhi (1974). Zbl0278.26001MR344043
  19. [19] N.R. Scott, Computer Number Systems & Arithmetic. Prentice-Hall, New Jersey (1985). Zbl0613.65046
  20. [20] R. Sedgewick and Ph. Flajolet, An Introduction to the Analysis of Algorithms. Addison-Wesley, Reading (1996). Zbl0841.68059
  21. [21] I. Wegener, Effiziente Algorithmen für grundlegende Funktionen. B.G. Teubner, Stuttgart (1996). Zbl0697.68011MR1076624

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.