×

zbMATH — the first resource for mathematics

On the number of iterations required by von Neumann addition. (English) Zbl 1053.68051
Summary: We investigate the number of iterations needed by an addition algorithm due to 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 (1963; Zbl 0188.00104)] if the input is random. Several authors have obtained 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 bution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.

MSC:
68Q25 Analysis of algorithms and problem complexity
65Y20 Complexity and performance of numerical algorithms
Software:
ARIBAS
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML
References:
[1] P. Billingsley , Probability and Measure , 2nd Ed. Wiley, New York ( 1986 ). MR 830424 | Zbl 0649.60001 · Zbl 0649.60001
[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 ). MR 22442
[3] P. Chassaing , J.F. Marckert and M. Yor , A stochastically quasi-optimal algorithm . Preprint ( 1999 ). · Zbl 1084.68145
[4] V. Claus , Die mittlere Additionsdauer eines Paralleladdierwerks . Acta Inform. 2 ( 1973 ) 283 - 291 . MR 366092 | Zbl 0304.68048 · Zbl 0304.68048 · doi:10.1007/BF00289501
[5] Th.H. Cormen , Ch.E. Leiserson and R.L. Rivest , Introduction to Algorithms . MIT Press, Cambridge, USA ( 1997 ). MR 1066870 | Zbl 1047.68161 · Zbl 1047.68161
[6] Ph. Flajolet , X. Gourdon and Ph. Dumas , Mellin transforms and asymptotics: Harmonic sums . Theoret. Comput. Sci. 144 ( 1995 ) 3 - 58 . MR 1337752 | Zbl 0869.68057 · Zbl 0869.68057 · doi:10.1016/0304-3975(95)00002-E
[7] O. Forster , Algorithmische Zahlentheorie . Vieweg, Braunschweig ( 1996 ). Zbl 0870.11001 · Zbl 0870.11001
[8] R. Grübel , Hoare’s selection algorithm: A Markov chain approach . J. Appl. Probab. 35 ( 1998 ) 36 - 45 . Article | Zbl 0913.60059 · Zbl 0913.60059 · doi:10.1239/jap/1032192549 · minidml.mathdoc.fr
[9] R. Grübel , On the median-of-\(k\) version of Hoare’s selection algorithm . RAIRO: Theoret. Informatics Appl. 33 ( 1999 ) 177 - 192 . Numdam | Zbl 0946.68058 · Zbl 0946.68058 · doi:10.1051/ita:1999112 · eudml:221976
[10] R. Grübel and U. Rösler , Asymptotic distribution theory for Hoare’s selection algorithm . Adv. Appl. Probab. 28 ( 1996 ) 252 - 269 . Zbl 0853.60033 · Zbl 0853.60033 · doi:10.2307/1427920
[11] D.E. Knuth , The Art of Computer Programming , Vol. 3, Sorting and Searching. Addison-Wesley, Reading ( 1973 ). MR 445948 | Zbl 0302.68010 · Zbl 0302.68010
[12] D.E. Knuth , The average time for carry propagation . Nederl. Akad. Wetensch. Indag. Math. 40 ( 1978 ) 238 - 242 . MR 497803 | Zbl 0382.10035 · Zbl 0382.10035
[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 ). Zbl 0927.60027 · Zbl 0927.60027
[14] C. McDiarmid and R.B. Hayward , Large deviations for Quicksort . J. Algorithms 21 ( 1996 ) 476 - 507 . MR 1417660 | Zbl 0863.68059 · Zbl 0863.68059 · doi:10.1006/jagm.1996.0055
[15] M. Régnier , A limiting distribution for quicksort . RAIRO: Theoret. Informatics Appl. 23 ( 1989 ) 335 - 343 . Numdam | MR 1020478 | Zbl 0677.68072 · Zbl 0677.68072 · eudml:92338
[16] S.I. Resnick , Extreme Values , Regular Variation and Point Processes. Springer, New York ( 1987 ). MR 900810 | Zbl 0633.60001 · Zbl 0633.60001
[17] U. Rösler , A limit theorem for “Quicksort” . RAIRO: Theoret. Informatics Appl. 25 ( 1991 ) 85 - 100 . Numdam | Zbl 0718.68026 · Zbl 0718.68026 · eudml:92383
[18] W. Rudin , Real and Complex Analysis , 2nd Ed. Tata McGraw-Hill, New Delhi ( 1974 ). MR 344043 | Zbl 0278.26001 · Zbl 0278.26001
[19] N.R. Scott , Computer Number Systems & Arithmetic . Prentice-Hall, New Jersey ( 1985 ). Zbl 0613.65046 · Zbl 0613.65046
[20] R. Sedgewick and Ph. Flajolet , An Introduction to the Analysis of Algorithms . Addison-Wesley, Reading ( 1996 ). Zbl 0841.68059 · Zbl 0841.68059
[21] I. Wegener , Effiziente Algorithmen für grundlegende Funktionen . B.G. Teubner, Stuttgart ( 1996 ). MR 1076624 | Zbl 0697.68011 · Zbl 0697.68011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.