×

zbMATH — the first resource for mathematics

Recent trends in random number and random vector generation. (English) Zbl 0737.65001
This is an expository paper on recent work concerning the generation of uniformly distributed pseudorandom numbers and vectors.
All the methods mentioned in the paper are clearly exposed and illustrated and often compared each other so that the reader can recover an exhaustive knowledge of the matter. The distribution uniformity is generally evaluated by considering the asymptotic behaviour of discrepancy.
The most relevant methods mentioned are the following: the linear congruential method which goes back to D. H. Lehmer [Proc. 2nd Symposium Large-Scale Digital Calculating Machines, 141–146 (1951; Zbl 0045.40001)] but is also object of recent studies, e.g. by G. S. Fishman and L. R. Moore III [SIAM J. Sci. Stat. Comput. 7, 24–45 (1986; Zbl 0603.65003); Erratum: ibid. 7, 1058 (1986; Zbl 0615.65004)]; the nonlinear congruential method, introduced by J. Eichenauer, H. Grothe, and J. Lehn [Metrika 35, No. 3–4, 241–250 (1988; Zbl 0653.65006)]; the inversive congruential method, introduced by J. Eichenauer, H. Grothe and J. Lehn [Stat. Hefte 27, 315–326 (1986; Zbl 0607.65001)]; the shift register methods, whose first diffusion goes back to R. C. Tausworthe [Math. Comput. 19, 201–209 (1965; Zbl 0137.34804)], but widely studied also in recent times.
Two final chapters concern the generation of pseudorandom vectors (utilizing the methods of matrix generators) and the generation of quasirandom vectors.
In the references eighty five papers are quoted.

MSC:
65C10 Random number generation in numerical analysis
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
11K45 Pseudo-random numbers; Monte Carlo methods
65D32 Numerical quadrature and cubature formulas
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L. Afflerbach, The sub-lattice structure of linear congruential random number generators, Manuscripta Math. 55 (1986) 455–465. · Zbl 0601.65005
[2] L. Afflerbach and H. Grothe, The lattice structure of pseudo-random vectors generated by matrix generators, J. Comp. Appl. Math. 23 (1988) 127–131. · Zbl 0658.65006
[3] L. Afflerbach and R. Weilbächer, The exact determination of rectangle discrepancy for linear congruential pseudorandom numbers, Math. Comp. 53 (1989) 343–354. · Zbl 0672.65008
[4] D.A. André, G.L. Mullen and H. Niederreiter, Figures of merit for digital multistep pseudorandom numbers, Math. Comp. 54 (1990) 737–748. · Zbl 0699.65003
[5] I.A. Antonov and V.M. Saleev, An economic method of computingLP t -sequences (Russian), Zh. Vychisl. Mat. i. Mat. Fiz. 19 (1979) 243–245. · Zbl 0432.65006
[6] A.C. Arvillias and D.G. Maritsas, Partitioning the period of a class ofm-sequences and application to pseudorandom number generation, J. ACM 25 (1978) 675–686. · Zbl 0402.65003
[7] V.C. Bhavsar and J.R. Isaac, Design and analysis of parallel Monte Carlo algorithms, SIAM J. Sci. Statist. Comp. 8 (1987) s73-s95. · Zbl 0638.65004
[8] I. Borosh and H. Niederreiter, Optimal multipliers for pseudo-random number generation by the linear congruential method, BIT 23 (1983) 65–74. · Zbl 0505.65001
[9] P. Bratley and B.L. Fox, Algorithm 659: Implementing Sobol’s quasirandom sequence generator, ACM Trans. Math. Software 14 (1988) 88–100. · Zbl 0642.65003
[10] P. Bratley, B.L. Fox and L.E. Schrage,A Guide to Simulation, 2nd ed. (Springer, New York, 1987). · Zbl 0515.68070
[11] B.J. Collings, String decomposition of full-period Tausworthe sequences, Comm. Statist. Simulation Comp. 16 (1987) 673–678. · Zbl 0634.65004
[12] B.J. Collings and G.B. Hembree, Initializing generalized feedback shift register pseudorandom number generators, J. ACM 33 (1986), 706–711; Addendum, idi. B.J. Collings and G.B. Hembree, Initializing generalized feedback shift register pseudorandom number generators, J. ACM 35 (1988) 1001. · Zbl 0661.65003
[13] I. Deák, Multidimensional integration and stochastic programming,Numerical Techniques for Stochastic Optimization, eds. Yu. Ermoliev and R.J.-B. Wets (Springer, Berlin, 1988) pp. 187–200.
[14] A. de Matteis and S. Pagnutti, Parallelization of random number generators and long-range correlations, Numer. Math. 53 (1988) 595–608. · Zbl 0633.65006
[15] V. Denzer and A. Ecker, Optimal multipliers for linear congruential pseudo-random number generators with prime moduli, BIT 28 (1988) 803–808. · Zbl 0665.65005
[16] L. Devroye,Non-Uniform Random Variate Generation (Springer, New York, 1986). · Zbl 0593.65005
[17] H.J.A. Duparc, C.G. Lekkerkerker and W. Peremans, Reduced sequences of integers and pseudo-random numbers, Report ZW 1953-002, Math. Centrum, Amsterdam (1953). · Zbl 0051.27403
[18] J. Eichenauer, H. Grothe and J. Lehn, Marsaglia’s lattice test and non-linear congruential pseudo random number generators, Metrika 35 (1988) 241–250. · Zbl 0653.65006
[19] J. Eichenauer, H. Grothe, J. Lehn and A. Topuzoĝlu, A multiple recursive nonlinear congruential pseudo random number generator, Manuscripta Math. 59 (1987) 331–346. · Zbl 0609.65005
[20] J. Eichenauer and J. Lehn, A non-linear congruential pseudo random number generator, Statist. Papers 27 (1986) 315–326. · Zbl 0607.65001
[21] J. Eichenauer and J. Lehn, On the structure of quadratic congruential sequences, Manuscripta Math. 58 (1987) 129–140. · Zbl 0598.65004
[22] J. Eichenauer, J. Lehn and A. Topuzoĝlu, A nonlinear congruential pseudorandom number generator with power of two modulus, Math. Comp. 51 (1988) 757–759. · Zbl 0701.65008
[23] J. Eichenauer and H. Niederreiter, On Marsaglia’s lattice test for pseudorandom numbers, Manuscripta Math. 62 (1988) 245–248. · Zbl 0663.65006
[24] J. Eichenauer-Herrmann and H. Grothe, A remark on long-range correlations in multiplicative congruential pseudorandom number generators. Numer. Math. 56 (1989) 609–611. · Zbl 0662.65003
[25] J. Eichenauer-Herrmann, H. Grothe and J. Lehn, On the period length of pseudorandom vector sequences generated by matrix generators, Math. Comp. 52 (1989) 145–148. · Zbl 0657.65008
[26] J. Eichenauer-Herrmann, H. Grothe, H. Niederreiter and A. Topuzoĝlu, On the lattice structure of a nonlinear generator with modulus 2{\(\alpha\)}, J. Comp. Appl. Math. 31 (1990) 81–85. · Zbl 0702.65006
[27] H. Faure, Discrépance de suites associées à un système de numération (en dimensions). Acta Arith. 41 (1982) 337–351.
[28] G.S. Fishman, Multiplicative congruential random number generators with modulus 2{\(\beta\)}: An exhaustive analysis for {\(\beta\)}=32 and a partial analysis for {\(\beta\)}=48. Math. Comp. 54 (1990) 331–344. · Zbl 0686.65004
[29] G.S. Fishman and L.R. Moore, An exhaustive analysis of multiplicative congruential random number generators with modulus 231–1, SIAM J. Sci. Statist. Comp. 7 (1986) 24–45; Erratum, ibid. G.S. Fishman and L.R. Moore, An exhaustive analysis of multiplicative congruential random number generators with moduls 231–1, SIAM J. Sci. Statist. Comp. 7 (1986) 1058. · Zbl 0603.65003
[30] B.L. Fox, Algorithm 647: Implementation and relative efficiency of quasirandom sequence generators, ACM Trans. Math. Software 12 (1986) 362–376. · Zbl 0615.65003
[31] M. Fushimi, Increasing the orders of equidistribution of the leading bits of the Takusworthe sequence, Inf. Process. Lett. 16 (1983) 189–192. · Zbl 0512.65005
[32] M. Fushimi, Designing a uniform random number generator whose subsequences arek-distributed, SIAM J. Comput. 17 (1988) 89–99. · Zbl 0637.65002
[33] M. Fushimi and S. Tezuka, Thek-distribution of the generalized feedback shift register pseudorandom numbers, Comm. ACM 26 (1983) 516–523. · Zbl 0515.68047
[34] H. Grothe, Matrixgeneratoren zur Erzeugung gleichverteilter Zufallsvektoren,Zufallszahlen und Simulationen, eds. L. Afflerbach and J. Lehn (Teubner, Stuttgart, 1986) pp. 29–34.
[35] H. Grothe, Matrix generators for pseudo-random vector generation, Statist. Papers 28 (1987) 233–238. · Zbl 0629.65006
[36] H. Grothe, Matrixgeneratoren zur Erzeugung gleichverteillter Pseudozufallsvektoren, Dissertation, Techn. Hochschule Darmstadt (1988). · Zbl 0652.65008
[37] J.H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2 (1960) 84–90; Berichtigung, ibid. J.H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Number. Math. 2 (1960) 196. · Zbl 0090.34505
[38] E. Hlawka, Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Ann. Mat. Pura Appl. 54 (1961) 325–333. · Zbl 0103.27604
[39] L.K. Hua and Y. Wang,Applications of Number Theory to Numerical Analysis (Springer, Berlin, 1981). · Zbl 0465.10045
[40] J. Kiefer, On large deviations of the empiric d.f. of vector chance variables and a law of the iterated logarithm, Pacific J. Math. 11 (1961) 649–660. · Zbl 0119.34904
[41] S. Kirkpatrick and E. P. Stoll, A very fast shift-register sequence random number generator.J. Comput. Phys. 40 (1981) 517–526. · Zbl 0458.65003
[42] D.E. Knuth.The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed. (Addison-Wesley, Reading, MA, 1981). · Zbl 0477.65002
[43] R.F. Koopman. The orders of equidistribution of subsequences of some asymptotically random sequences, Comm. ACM 29 (1986) 802–806. · Zbl 0641.65007
[44] L. Kuipers and H. Niederreiter,Uniform Distribution of Sequences (Wiley, New York, 1974). · Zbl 0281.10001
[45] G. Larcher and H. Niederreiter, Optimal coefficients modulo prime powers in the three-dimensional case. Ann. Mat. Pura Appl. 155 (1989) 299–315. · Zbl 0697.65007
[46] P. L’Ecuyer, Efficient and portable combined random number generators. Comm. ACM 31 (1988) 742–749, 774.
[47] D.H. Lehmer, Mathematical methods in large-scale computing units,Proc. 2nd Symp. on Large-Scale Digital Calculating Machinery, Cambridge, MA, 1949 (Harvard Univ. Press, Cambridge, MA, 1951) pp. 141–146.
[48] T.G. Lewis and W.H. Payne, Generalized feedback shift register pseudorandom number algorithm, J. ACM 20 (1973) 456–468. · Zbl 0266.65009
[49] R. Lidl and H. Niederreiter,Finite Fields (Addison-Wesley, Reading, MA, 1983).
[50] R. Lidl and H. Niederreiter,Introduction to Finite Fields and Their Applications (Cambridge Univ. Press, Cambrdige, 1986). · Zbl 0629.12016
[51] G. Marsanglia, The structure of linear congruential sequences, in:Applications of Number Theory to Numerical Analysis, ed. S.K. Zaremba (Academic Press, New York, 1972) pp. 249–285.
[52] G. Marsaglia and L.-H. Tsay, Matrices and the structure of random number sequences, Linear Algebra Appl. 67 (1985) 147–156. · Zbl 0572.65002
[53] G.L. Mullen and H. Niederreiter, Optimal characterstic polymonials for digital multistep pseudorandom numbers, Computing 39 (1987) 155–163. · Zbl 0618.65004
[54] H. Niederreiter, Pseudo-random numbers and optimal coefficients. Adv. Math. 26 (1977) 99–181. · Zbl 0366.65004
[55] H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978) 957–1041. · Zbl 0404.65003
[56] H. Niederreiter, Applications des corps finis aux nombres pseudo-aléatoires,Sém. Théorie des Nombres 1982–1983, Exp. 38, Univ. de Bordeaux 1, Talence (1983).
[57] H. Niederreiter, The performance ofk-step pseudorandom number generators under the uinformity test, SIAM J. Sci. Statist. Comp. 5 (1984) 798–810. · Zbl 0557.65005
[58] H. Niederreiter, The serial test for pseudo-random numbers generated by the linear congruential method, Number. Math. 46 (1985) 51–68. · Zbl 0554.65006
[59] H. Niederreiter, A pseudorandom vector generator based on finite field arithmetic, Math. Japonica 31 (1986) 759–774. · Zbl 0619.65002
[60] H. Niederreiter, Pseudozufallszahlen und die Theorie der Gleichverteilung, Sitzungsber. Österr. Akad. Wiss. Math.-Naturwiss. Kl. Abt. II 195 (1986) 109–138. · Zbl 0616.10040
[61] H. Niederreiter, A statistical analysis of generalized feedback shift register pseudorandom number generators, SIAM J. Sci. Statist. Comp. 8 (1987) 1035–1051. · Zbl 0634.65003
[62] H. Niederreiter, Point sets and sequences with small discrepancy. Monatsh. Math. 104 (1987) 273–337. · Zbl 0626.10045
[63] H. Niederreiter, Remarks on nonlinear congruential pseudorandom numbers, Metrika 35 (1988) 321–328. · Zbl 0663.65005
[64] H. Niederreiter, Statistical independence of nonlinear congruential pseudorandom numbers, Monatsh. Math. 106 (1988). 149–159. · Zbl 0652.65007
[65] H. Niederreiter, Quasi-Monte Carlo methods for multidimensional numerical integration,Numerical Integration III, eds. H. Brass and G. Hämmerlin, Int. Series of Num. Math., 85 (Birkhäuser, Basel, 1988) pp. 157–171. · Zbl 0662.65021
[66] H. Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988) 51–70. · Zbl 0651.10034
[67] H. Niederreiter, The serial test for digitalk-step pseudorandom numbers. Math. J. Okayama Univ. 30 (1988) 93–119. · Zbl 0666.65003
[68] H. Niederreiter, The serieal test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989) 135–144. · Zbl 0657.65007
[69] H. Niederreiter, Statistical independence properties of pseudorandom vectors produced by matrix generators. J. Comp. Appl. Math. 31 (1990) 139–151. · Zbl 0708.65007
[70] H. Niederreiter, Lower bounds for the discrepancy of inversive congruential pseudorandom numbers, Math. Comp. 55 (1990) 277–287. · Zbl 0708.65006
[71] H. Niederreiter, Pseudorandom numbers generated from shift register sequences, in:Zahlentheoretische Analysis, Springer Lecture Notes in Math., to appear. · Zbl 0718.11034
[72] N. Niki, Finite field arithmetics and multidimensional unform pseudorandom numbers (Japanese), Proc. Inst. Statist. Math. 32 (1984) 231–239. · Zbl 0568.65004
[73] A.I. Pavlov and B.B. Pokhodzeî, Pseudo-random numbers generated by linear recurrence relations over a finite field (Russian), Zh. Vychisl. Mat. i Mat. Fiz. 19 (1979) 836–842.
[74] O.E. Percus and J.K. Percus, Long range correlations in linear congruential generators, J. Comput. Phys. 77 (1988). 267–269. · Zbl 0644.65003
[75] B.D. Ripley, The lattice structure of pseudo-random number generators, Proc. Roy. Soc. London Ser. A 389 (1983) 197–204. · Zbl 0516.65003
[76] W.M. Schmidt, Irregularities of distribution VII, Acta Arith. 21 (1972) 45–50. · Zbl 0244.10035
[77] I.M. Sobol’, The distribution of points in a cube and the approximate evaluation of integrals (Russian), Zh. Vychisl. Mat. i Mat Fiz. 7 (1967). 784–802.
[78] E.A.D.E. Tahmi, Contribution aux générateurs de vecteurs pseudo-aléatoires, Thèse, Univ. Sci. Techn. H. Boumedienne, Algiers (1982).
[79] R.C. Tausworthe, Random numbers generated by linear recurrence modulo two, Math. Comp. 19 (1965) 201–209. · Zbl 0137.34804
[80] S. Tezuka, On the discrepancy of GFSR pseudorandom numbers, J. ACM 34 (1987) 939–949. · Zbl 0633.65005
[81] S. Tezuka, A heuristic approach for finding asymptotically random GFSR generators, J. Inf. Proc. 10 (1987) 178–182.
[82] S. Tezuka. On optimal GFSR pseudorandom number generators, Math. Comp. 50 (1988) 531–533. · Zbl 0644.65004
[83] A. van Wijngaarden, Mathematics and computing,Proc. Symp. on Automatic Digital Computation, London, 1954 (H.M. Stationery Office, London, 1954) pp. 125–129.
[84] B.A. Wichmann and I.D. Hill, An efficient and portable pseudo-random number generator, Appl. Stat. 31 (1982) 188–190; Corrections, ibid. B.A. Wichmann and I.D. Hill. An efficient and portable pseudo-random number generator, Appl. Stat. 33 (1984) 123.
[85] B.A. Wichmann and I.D. Hill, Building a random-number generator, Byte 12, No. 3 (1987) 127–128.
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.