臺灣博碩士論文加值系統

亂數產生器的用途在很多的應用上扮演一個非常重要的角色，像是加密系統，模擬， 統計方法的分析也都必須倚賴亂數。這些研究的品質及可信度必須要有一個好的亂數產生器來支持。且參數 B=16807，C=0，M=2147483647 之LCG是現在電腦套裝軟體中常見的基本亂數產生器，但是它的週期短，只能在一維空間均勻分佈，況且它無法通過Diehard 這一套檢驗亂數產生器的系統檢驗。 DX-k-s是一套高維均勻分佈，有效率，週期長，且可用來配備於各種電腦的亂數產生器。我們主要研究的目的就是要探討這一套亂數產生器用Diehard來檢驗的表現。根據我們的實驗結果報告，DX-k-s 幾乎通過了所有Diehard裡的檢驗法。而且分析檢驗結果，我們發現DX之參數k，s，和B 對DX-k-s 在Diehard 裡的表現並無顯著影響。我們也特別檢驗了參數M= =2147427929 和 B=521816 的DX-1511-4，這個亂數產生器的週期等於 ，而且它可以在1511維以內的空間均勻分佈。現今鮮少有亂數產生器可以通過Diehard 裡的所有檢驗法，而DX-1511-4 辦到了。 總而言之，由我們的檢驗結果來評估，DX是一套相當好，值得推薦的亂數產生器。

Random numbers are used in many modern applications, such as computer games, the generation of cryptographic keys, simulation studies, and many scientific experiments. Quality of these applications and studies rely heavily on the quality of the random number generator (RNG) used. LCG with B=16807, C=0, M=2147483647 is very popular and used as a default RNG in many computer systems; but it does not pass all the tests in the Diehard test suite [19]. DX-k-s generators, proposed recently by Deng and Xu [4], is a system of High-dimensional uniformly, Efficient, Long-cycle, and Portable uniform random number generators. The main objective of this study is to investigate the empirical performance of the DX-k-s random number generators. We test DX-k-s random number generators by the Diehard test suite with a well-planned experimental design. According to the results of our experiments, DX family generators pass almost all the tests in Diehard and the parameters, k, s, and B do not significantly affect the performances of the RNGs under study. We also test a particular generator DX-1511-4 with M= =2147427929 and B=521816. This generator has a very long period of and is equi-distributed up to 1511 dimensions. In particular, DX-1511-4 passes all the tests in Diehard. We conclude that, based on our empirical study, DX-k-s generators is a very good family of RNGs.

CONTENTS

Chinese Abstract ………………………………………………………… i
English Abstract ………………………………………………………… ii
Acknowledgements ………………………………………………………… iii
Table of Contents ………………………………………………………… iv
List of Tables ………………………………………………………… v
List of Figures ………………………………………………………… vi
Chapter One Introduction ……………………………………………… 1
Chapter Two Literature Review ………………………………………… 3
2.1 Pseudo-random Number Generators ……………………… 3
2.2 Linear Congruential Generator : LCG …………………… 3
2.3 Multiple Recursive Generator : MRG …………………… 4
2.4 Fast Multiple Recursive Generator : FMRG……………… 5
2.5 A System of Generators by Deng & Xu : DX …………… 5
Chapter Three An Empirical Study ……………………………………… 8
3.1 Introduction ……………………………………………… 8
3.2 C program ………………………………………………… 8
3.3 Initial Seeds for 5 Replicates……………………………… 8
3.4 Selection of B’s …………………………………………… 8
3.5 KS-test in Diehard Test Suite …………………………… 9
3.6 Tests in Diehard Suite …………………………………… 9
3.7 Design of the Experiment ………………………………… 10
Chapter Four Result of the Empirical Studies …………………………… 12
4.1 Tests of Random Numbers and Our Experiment Results … 12
4.2 ANOVA & Discussion …………………………………… 13
4.3 A Comparison Study with LCG…………………………… 14
4.4 DX-1511-4 with M=2 -55719 and B=521816 …………… 14
Chapter Five Conclusion ………………………………………………… 15
Reference ……………………………………………………………… 16
Appendix I ……………………………………………………………… 18
Appendix II ……………………………………………………………… 21
Appendix III ……………………………………………………………… 23

[1] Bogomolny, A. Pigeonhole Principle. http://www.cut-the-knot.com/do_ you_know/pigeon.shtml.
[2] Dieter, U. 1993. Erzeugung von gleichverteilten zufallszahlen. Jahrbuch Uberblicke Mathematik, Vieweg, Braunschweig, 25-44.
[3] Deng, L.Y. and Lin, D.K.J. 2000. Random number generation for the new century. American Statistician, 54, 145-150.
[4] Deng, L.Y. and Xu, H.Q. 2003. A system of high-dimensional, efficient, long-cycle and portable uniform random number generators. ACM Transactions on Mathematical Software, April 2003, 1–11.
[5] Deng, L.Y. and Xu, H.Q. Supplement to DX random number generators. http://www.cs.memphis.edu/~dengl/dx-rng/
[6] Fishman, G.S. and Moore, L.R. 1986. An exhaustive analysis of multiplicative congruential random number generators with modulus 231-1. SIAM J. Sci. Comput., 7, 24-25.
[7] Grothe, H. 1988. Matrixgeneratoren zur erzeugung gleichverteilter pseudozufallsvektoren. Technische Hochschule Darmstadt, PhD thesis.
[8] Grube, A. 1973. Mehrfach rekursiv erzeugte zufallszahlen. University of Karlruhe, PhD thesis.
[9] Kao, C. and Tang, H.C. 1995. Symmetry property of multiplicative congruential random number generator in chi-square test. Computer Math, Intern. J. 55, 113-118.
[10] Kao, C. and Wong, J.Y. 1998. Random number generators with long period and sound statistical properties. Computers and Mathmatics with Application, 36. 3, 113-121.
[11] Knuth, D.E. 1981. The Art of Computer Programming: Vol 2 / Seminumerical Algorithms. 2nd ed. Addison-Wesley.
[12] L'Ecuyer, P. 1990. Random numbers for simulation. Comm. ACM, 33, 85-97.
[13] L'Ecuyer, P., Blouin, F., and Couture, R. 1993. A search for good multiple recursive generators. ACM Transactions on Modeling and Computer Simulation, 3, 87-98.
[14] L'Ecuyer, P. and Couture, R. 1997. An implementation of the lattice and spectral tests for multiple recursive linear random number generators. INFORMS Journal on Computing, 9, 2, 206-217.
[15] L'Ecuyer, P. 1997. Bad lattice structures for vectors of non-successive values produced by some linear recurrences. INFORMS Journal on Computing, 9, 57-60.
[16] Lehmer, D.H. 1949. Mathematical methods in large-scale computing units. Proc. 2nd Sympos. on Large-Scale Digital Calculating Machinery, Harvard University Press, Cambridge, MA, 141-146.
[17] Marsaglia, G. 1968. Random numbers fall mainly in the planes. Proceedings of National Academic of Science, 6, 101-102.
[18] Marsaglia, G. 1995. The Marsaglia random number CDROM including the Diehard battery of tests of randomness. http://stat.fsu.edu/pub/diehard/
[19] Nelson, S. 1998. Tests for randomness. DiehardC, Version 1.03. http://www.ciphersbyritter.com/NEWS3/RANDTEST.HTM
[20] Park, S.K. and Miller, K.W. 1988. Random Number Generators: Good Ones are Hard to Find. Transactions of the ACM, 31, 10, 1192-1201.