Porównanie generatorów liczb pseudolosowych

• Autorzy: Piotr Sulewski

Warianty tytułu

Comparison of Normal Random Number Generators

• Języki publikacji: PL

Abstrakty

Losowanie prób w badaniach statystycznych i w obliczeniach numerycznych, jak również symulacyjne badanie modeli probabilistycznych właściwie we wszystkich dziedzinach wiedzy wymagają wyposażenia komputera w generatory liczb pseudolosowych. Głównym celem pracy jest porównanie generatorów liczb pseudolosowych normalnych na podstawie ich analizy dokonanej za pomocą różnego rodzaju kryteriów. Zbadano właściwości 12 generatorów liczb pseudolosowych o rozkładzie normalnym. Zaproponowano rozszerzenie rodziny generatorów o dwa tzw. generatory aplikacyjne oraz przyjęcie nowego podejścia do sprawdzania jakości generatorów. Przedstawiono narzędzie przygotowane w języku C++ oraz w języku Visual Basic for Application (VBA) do prowadzenia samodzielnych badań z użyciem generatorów. Symulacje Monte Carlo przeprowadzono w języku C++, a obliczenia wykonano w edytorze VBA przy użyciu arkusza kalkulacyjnego Microsoft Excel 2016. Analiza uzyskanych wyników wskazuje, że najlepsze właściwości mają generatory: MP Monty Pythona, R, Biegun oraz Ziggurat. Najmniej użyteczne okazują się generatory: BM Boxa-Mullera, Wallace'a, Iloraz oraz Excel. (abstrakt oryginalny)

EN

The sampling in statistical surveys and numerical calculations as well as simulation testing of probabilistic models in virtually all fields of knowledge require a computer endowed with pseudorandom numbers generators. The main goal of the study is to compare the normal random number generators using various criteria. The properties of 12 random number generators for a normal distribution were investigated. Then, the family of generators was extended by two so-called application generators and a new approach for checking the quality of generators was adopted. A ready-made tool prepared in C++ and in Visual Basic for Application (VBA) for conducting self-contained research using generators was presented. All Monte Carlo simulations were carried out in C++, while the calculations were performed in the VBA editor using the Microsoft Excel 2016 spreadsheet. The analysis of the obtained results shows that the generators with best properties are: MP Monty Python, R, Biegun and Ziggurat. The worst generators, are: BM Box-Muller, Wallace, Iloraz and Excel. (original abstract)

Słowa kluczowe

PL

Rozkłady normalne; Symulacja Monte Carlo

EN

Normal distribution; Monte Carlo simulation

• Czasopismo: Wiadomości Statystyczne
• Rocznik: 2019
• Numer: nr 7
• Strony: 5--31

Twórcy

autor

Piotr Sulewski

• Akademia Pomorska w Słupsku

Bibliografia

• Abdi, H., Molin, P. (2007). Lilliefors/Van Soest's test of normality. W: N. Salkind (red.), Encyclopedia of Measurement and Statistics. Thousand Oaks: Sage.
• Ahrens, J. H., Dieter, U. (1972). Computer methods for sampling from the exponential and normal distributions. Communication of the ACM, 15(10), 873-882.
• Ahrens, J. H., Dieter, U. (1988). Efficient table-free sampling methods for the exponential, Cauchy, and normal distributions. Communication of the ACM, 31(11), 1330- 1337.
• Anderson, T. W., Darling, D. A. (1952). Asymptotic theory of certain "goodness-of-fit" criteria based on stochastic processes. Annals of Mathematical Statistics, 23(2), 193-212. DOI: 10.1214/aoms/1177729437.
• Bell, J. R. (1968). Algorithm 334: Normal random deviates. Communication of the ACM, 11(7), 498.
• Bloom, G. (1958). Statistical estimates and transformed Beta variables. New York: Wiley.
• Box, G. E. P., Muller, M. E. (1958). A note on the generation of random normal deviates. Annals of Mathematical Statistics, 29(2), 610-611.
• Brent, R. P. (1974). Algorithm 488: A Gaussian pseudo-random number generator. Communication of the ACM, 17(12), 704-706.
• Chen, J., Moon, J., Bazargan, K. (2004). Reconfigurable readback- signal generator based on a field programmable gate array. IEEE Transactions on Magnetics, 40(3), 1744-1750.
• Chen, W., Burford, R. L. (1981). Quality evaluation of some combinations of unit uniform random number generators and unit normal transformation algorithms. W: R. M. Huhn, E. R. Comer, F. O. Simons Jr. (red.), ANSS'81: Proceedings of the 14th Annual Symposium on Simulation (s. 129-149). Tampa: IEEE Press Piscataway.
• Cramer, H. (1928). On the Composition of Elementary Errors. Scandinavian Actuarial Journal, 1(1), 13-74.
• Cramer, H. (1958). Metody matematyczne w statystyce. Warszawa: PWN.
• D'Agostino, R. B. (1986). Tests for the Normal Distribution. W: R. B. D'Agostino, M. A. Stephens (red.), Goodness-of- Fit Techniques (s. 367-413). New York: Marcel Dekker.
• Gebhardt, F. (1964). Generating normally distributed random numbers by inverting the normal distribution function. Mathematics of Computation, 18(86), 302-306.
• Kabal, P. (2000). Generating Gaussian pseudo-random deviates. McGill University.
• Kinderman, A. J., Monahan, J. F. (1977). Computer generation of random variables using the ratio of uniform deviates. ACM Transactions on Mathematical Software, 3(3), 257-260.
• Knop, R. (1969). Remark on Algorithm 334 [g5]: normal random deviates. Communication of the ACM, 12(5), 281.
• Kolmogorov, A. (1933). Sulla determinazione empirica di una legge di distributione. Giornale dell' Istituto Italiano degli Attuari, (4), 83-91.
• Kronmal, R. (1964). Evaluation of a pseudorandom normal number generator. Journal of the ACM, 11(3), 357-363.
• Kuiper, N. H. (1960). Tests concerning random points on a circle. Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen Series A, (63), 38-47.
• L'Ecuyer, P. (1992). Testing random number generators. W: J. J. Swain, D. Goldsman, R. C. Crain, J. R. Wilson (red.), Proceedings of the 24th Conference on Winter Simulation (s. 305-313). New York: ACM Press.
• L'Ecuyer, P. (2001). Software for uniform random number generation: distinguishing the good and the bad. W: Proceedings of the 33rd Conference on Winter Simulation (s. 95-105). Washington: IEEE Computer Society.
• L'Ecuyer, P., Simard, R. (2005). TestU01. Pobrane z: http://simul.iro.umontreal.ca/.
• L'Ecuyer, P., Simard, R. (2007). TestU01: AC library for empirical testing of random number generators. ACM Transactions on Mathematical Software, 33(4), 22.
• Leva, J. L. (1992). A fast normal random number generator. ACM Transactions on Mathematical Software, 18(4), 449-453.
• Lilliefors, H. W. (1967). On the Kolmogorov-Smirnov Test for Normality with Mean and Variance Unknown. Journal of the American Statistical Association, 62(318), 399- 402.
• Marsaglia, G. (1997). The Diehard random number test suite. Pobrane z: https://github.com/nmondal /diehard.c.
• Marsaglia, G., Bray, T. A. (1964). A convenient method for generating normal variables. SIAM Review, 6(3), 260 -264.
• Marsaglia, G., Tsang, W. W. (1998). The Monty Python Method for Generating Random Variables. ACM Transactions on Mathematical Software, 24(3), 341-350.
• Marsaglia, G., Tsang, W. W. (2000). The Ziggurat Method for Generating Random Variables. Journal of Statistical Software, 5(8), 1-7.
• Matsumoto, M., Nishimura, T. (1998). Mersenne twister: A 623- dimensionally equidistributed uniform pseudo-random number generator. ACM Transactions on Modeling and Computer Simulation, 8(1), 3-30.
• McCollum, J. M., Lancaster, J. M., Bouldin, D. W., Peterson, G. D. (2003). Hardware acceleration of pseudo- random number generation for simulation applications. W: IEEE Southeastern Symposium on System Theory. Morgantown: IEEE. DOI: 10.1109/SSST.2003.1194578.
• Melard, G. (2014). On the accuracy of statistical procedures in Microsoft Excel 2010. Computational Statistics, 29(5), 1095-1128.
• Molle, J. W. D., Hinich, M. J., Morrice, D. J. (1992). Higher-order cumulant spectral-based statistical tests of pseudo-random variate generators. W: Proceedings of the 24th Conference on Winter Simulation (s. 618-625). New York: ACM Press.
• Muller, M. E. (1958). An inverse method for the generation of random normal deviates on large-scale computers. Mathematical Tables and Other Aids to Computation, 12(63), 167-174.
• Muller, M. E. (1959). A comparison of methods for generating normal deviates on digital computers. Journal of the ACM, 6(3), 376- 383.
• Ohirko, I., Zaniewski, I., Ogirko, O. (2016). Modelowanie i symulacja w naukach ekonomicznych. Autobusy: technika, eksploatacja, systemy transportowe, 17(6), 1742-1747.
• Razali, N. M., Wah, Y. B. (2011). Power comparisons of shapiro-wilk, kolmogorov-smirnov, lilliefors and anderson-darling tests. Journal of Statistical Modeling and Analytics, 2(1), 21- 33.
• Renyi, A. (1953). On the theory of order statistics. Acta Mathematica Acadamiae Scientiarum Hun-garnicae (4), 191- 232.
• Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., Vo, S. (2001). A statistical test suite for random and pseudorandom number generators for cryptographic applications. Gaithersburg: National Institute of Standards and Technology (NIST).
• Schollmeyer, M. F., Tranter, W. H. (1991). Noise generators for the simulation of digital communication systems. W: Proceedings of the 24th Annual Symposium on Simulation (s. 264-275). Los Alamitos: IEEE Computer Society Press.
• Shapiro, S. S., Wilk, M. B. (1965). An Analysis of Variance Test for Normality. Biometrika, 52(3/4), 591-611.
• Smirnov, N. (1948). Table for estimating the goodness of fit of empirical distributions. Annals of Mathematical Statistics, (19), 279-281.
• Sulewski, P. (2000). Test trendu i sezonowości. Wiadomości Statystyczne, (5), 11-19.
• Thomas, D. B., Luk, W., Leong, P. H. W., Villasenor, J. D. (2007). Gaussian random number generators. Journal ACM Computing Surveys, 39(4), 1-38.
• Wallace, C. (2005). Random number generators. Technical report, Monash University. Pobrano z: http://www.datamining.monash.edu.au/software/random/.
• Watson, G. S. (1961). Goodness-of-Fit Tests on a Circle. Biometrika, 48(1/2), 109-114.
• Wetherill, G. B. (1965). An approximation to the inverse normal function suitable for the generation of random normal deviates on electronic computers. Journal of the Royal Statistical Society Series C, 14(2-3), 201-205.
• Wichura, M. J. (1988). Algorithm AS 241: The Percentage Points of the Normal Distribution. Journal of the Royal Statistical Society. Series C, 37(3), 477-484.
• Wieczorkowski, R., Zieliński, R. (1997). Komputerowe generatory liczb losowych. Warszawa: WNT.