×
de Matteis, A.; Pagnutti, S.

Parallelization of random number generators and long-range correlations. (English) Zbl 0633.65006

Numer. Math. 53, No. 5, 595-608 (1988).
Partitions of pseudo-random sequences generated by congruential schemes are investigated for use on computer systems where multiple processing units run in parallel for the solution of a Monte Carlo problem. A special partition is suggested which ensures independence between the units working simultaneously, and yields reproducible sequences. The analysis performed has brought out the existence of strong autocorrelations between terms located far apart in the sequences, depending only the congruential nature of the generators. The study of these correlations - carried out in a number theoretic framework - points out that only small fractions of the sequences can be safely used.

Cited in 2 Reviews
Cited in 20 Documents

MSC:

65C10 Random number generation in numerical analysis
65C05 Monte Carlo methods
65Y05 Parallel numerical computation

Keywords:

partitions of pseudo-random sequences; congruential schemes; Monte Carlo problem; strong autocorrelations; parallel computing
Cite Review PDF
Full Text: DOI EuDML

References:

[1] Ahrens, J., Dieter, U., Grube, A.: Pseudo-random numbers: A new proposal for the choice of multiplicators. Computing6, 121-138 (1970) · Zbl 0212.18205 · doi:10.1007/BF02241740
[2] Andrews, G.R., Schneider, F.B.: Concepts and notations for concurrent programming. ACM Comput. Surv.15, 3-43 (1983) · Zbl 0515.68025 · doi:10.1145/356901.356903
[3] Borosh, I., Niederreiter, H.: Optimal multipliers for pseudo-random generation by the linear congruential method. BIT23, 65-74 (1983) · Zbl 0505.65001 · doi:10.1007/BF01937326
[4] Cenacchi, G., De Matteis, A.: Pseudo-random numbers for comparative Monte Carlo calculations. Numer. Math.16, 11-15 (1970) · doi:10.1007/BF02162402
[5] Chambers, R.P.: Random number generation. IEEE Spectrum.4, Part 1, No. 2, 48-56 (1967) · doi:10.1109/MSPEC.1967.5216203
[6] Coveyou, R.R.: Serial correlation in the generation of pseudo-random numbers. J. Ass. Comput. Mach.7, 72-74 (1960) · Zbl 0096.33903
[7] CRAY-1 and CRAY-X-MP Computer systems library reference manual. SR-0014, Rev. H. February 1984
[8] De Matteis, A., Faleschini, B.: Some arithmetical properties in connection with pseudo-random numbers. Boll. Unione Mat. Ital.18, 171-184 (1963) · Zbl 0116.26805
[9] Di Chio, P., Zecca, V.: IBM ECSEC facilities: user’s guide. IBM Technical report G 513-4080, Rome, December 1985
[10] Dieter, U., Ahrens, J.: An exact determination of serial correlations of pseudo-random numbers. Numer. Math.17, 101-123 (1971) · Zbl 0228.65006 · doi:10.1007/BF01406000
[11] Greenberger, M.: Notes on a new pseudo-random number generator. J. Assoc. Comput. Mach.8, 163-167 (1961) · Zbl 0104.36005
[12] Hammersley, J.M., Handscomb, D.C.: Monte Carlo methods. London: Methuen 1964
[13] Hill, G.W.: Cyclic properties of pseudo-random sequences of Mersenne prime residues. Comput. J.22, 80-85, (1979) · Zbl 0401.65001 · doi:10.1093/comjnl/22.1.80
[14] Holmlid, L., Rynefors, K.: Uniformity of congruential pseudo-random number generators. Dependence on length of number sequence and resolution. J. Comput. Phys.26, 297-306 (1978) · Zbl 0378.65002 · doi:10.1016/0021-9991(78)90072-4
[15] Marsaglia, G.: Random numbers fall mainly in the planes. Proc. Nat. Acad. Sci. USA61, 25-28 (1968) · Zbl 0172.21002 · doi:10.1073/pnas.61.1.25
[16] Marsaglia, G.: Regularities in congruential random number generators. Numer. Math.16, 8-10 (1970) · Zbl 0212.18204 · doi:10.1007/BF02162401
[17] Marsaglia, G.: The structure of linear congruential sequences. In: Applications of number theory to numerical analysis (S.K. Zaremba, ed.), pp. 249-287. New York: Academic Press 1972
[18] Moshman, J.: The generation of pseudo-random numbers on a decimal calculator. J. Assoc. Comput. Mach.1, 88-91 (1954)
[19] Neuman, F., Merrick, R.: Autocorrelation peaks in congruential pseudo-random number generators. IEEE Trans. Comput.C-25, 457-560 (1976) · Zbl 0329.65007 · doi:10.1109/TC.1976.1674632
[20] Neuman, F., Martin, C.F.: The autocorrelation structure of Tausworthe pseudo-random number generators. IEEE Trans. Comput.C-25, 460-464 (1976) · Zbl 0329.65008 · doi:10.1109/TC.1976.1674633
[21] Peach, P.: Bias in pseudo-random numbers. J. Amer. Statist. Assoc.56, 610-618 (1961) · Zbl 0111.14801 · doi:10.2307/2282083
[22] Ramamoorthy, C.V., Li, H.F.: Pipeline architecture. ACM Comput. Surv.9, 61-102 (1977) · Zbl 0348.68038 · doi:10.1145/356683.356687
[23] Rotenberg, A.: A new pseudo-random number generator. J. Assoc. Comput. Mach.7, 75-77 (1960) · Zbl 0096.33902
[24] Zaremba, S.K.: The mathematical basis of Monte Carlo and quasi-Monte Carlo methods. SIAM Rev.10, 303-314 (1968) · doi:10.1137/1010056
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.