RANDOM NUMBER GENERATION AND ITS BETTER TECHNIQUE
RANDOM NUMBER GENERATION AND ITS BETTER TECHNIQUE
A thesis submitted in partial fulfillment of the requirements for the award of degree of Master of Engineering in
Computer Science and Engineering Submitted By
Prasada Rao Gurubilli (Roll No: 800832004) Under the supervision of
Dr. Deepak Garg Assistant Professor
COMPUTER SCIENCE AND ENGINEERING DEPARTMENT THAPAR UNIVERSITY PATIALA ? 147004
June 2010
Abstract
Random number generators based on linear recurrences modulo 2 are among the fastest long-period generators currently available. The uniformity and independence of the points they produce, over their entire period length, can be measured by theoretical figures of merit that are easy to compute, and those having good values for these figures of merit are statistically reliable in general. Some of these generators can also provide disjoint streams and substreams efficiently. In this paper, we review the most interesting construction methods for these generators, examine their theoretical and empirical properties, and make comparisons. Random number generation is the art and science of deterministically generating a sequence of numbers that is difficult to distinguish from a true random sequence. This thesis introduces the field of random number generation, and studies three types of random number generators in depth. It also includes mathematical techniques for transforming the output of generators to arbitrary distributions, and methods of evaluating and comparing random number generators. It concludes with a summary and historical perspective on the field of random number generation. The mathematics in this thesis is drawn mainly from number theory, with a few fundamental ideas taken from probability and statistics.
iii
Table of Contents
Certificate ......................................................................................................................i Acknowledgement ........................................................................................................ ii Abstract ....................................................................................................................... iii Table of Contents .........................................................................................................iv List of Figures .............................................................................................................vii List of Tables ............................................................................................................. viii List of Abbreviations..............................................................................ix Chapter 1:Introduction ................................................................................................1
1.1 What is a random number generator? ......................................................1 1.2 Transformation of the original sequence...................................................2 1.3 What makes a good random number generator? ..........................................2 1.4 Types of random number generators........................................................4 1.5 Applications of random numbers.............................................................7 Chapter 2: Literature Review ........................................................................ ...........9 2.1 Desirable Attributes of Random Numbers..................................................9 2.2 Methods of random numbers.................................................................9
2.2.1 Mid Square Method.....................................................................9 2.2.2 The Linear Congruential Method....................................................12
iv
2.2.2.1 Properties of Congruential Generators.....................................13 2.2.2.2 LCG Full period...............................................................15 2.2.2.3 Multiplicative congruential Method........................................16 2.2.2.4 Merits and Demerits of LCG................................................18 2.2.3 Quadratic Congruential Method.....................................................19 2.2.4 Fibonacci Generator...................................................................20 2.2.5 Combined Multiple Recursive Generator (CMRG)...............................21 2.2.6 Additive number generator...........................................................24 2.2.7 Combination of random number generator.........................................25 Chapter 3: Problem Statement ...................................................................................28 Chapter 4: Design and Implementation......................................................................29 4.1 Multiple Recursive Generators............................................................29 4.1.1 Feedback Shift Register Generators................................................30 4.2 Combined MRGs............................................................................32 4.3 Overview of the Remainder................................................................33 4.4 Lattice Structure and Quality Criteria.....................................................34 4.4.1 Implementation by the powers of 2- decomposition method...................35 4.5 Search for good parameters................................................................36 4.5.1 A specific generator and some timings.............................................36 Chapter 5: Results .......................................................................................................40
v
Chapter 6: Conclusion and Future Scope...................................................................42 6.1 Conclusion...............................................................................................................42 6.2 Future Scope............................................................................................................42 References ....................................................................................................................43 List of Publications .................................................................................46
vi
List of Figures
Figures: Figure 1.1: Generating the random numbers......................................................3 Figure 1.2: Generating 100000 random dots......................................................4 Figure 1.3: A PCI version (rw4) generating true random numbers at 160 MByte/s.........5 Figure 1.4: Quasi-random numbers................................................................6 Figure 1.5: Pseudorandom numbers...............................................................7 Figure 2.1: 4096 generated points on the unit square..........................................16 Figure 4.1: Feedback Shift Register Generators................................................31 Figure 4.2: Implementation of a CMRG with Powers-of-2 Decomposition method......38 Figure 5.1(a): The resulting time for integers....................................................40 Figure 5.1(b): The resulting time for long integers.............................................40
vii
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- random numbers and monte carlo methods
- generating uniform random numbers
- appendix b random number tables
- appendix b random numbers table and instructions
- chapter 9 random numbers mathworks
- random numbers stanford university computer science
- tips and techniques for using the random number generators
- random number generation
- random number generation rice university
- mathematica tutorial random number generation
Related searches
- python random number between
- random number generator 1 10
- random number picker 1 100
- python random number in range
- random number from 1 to 100
- random number generator 1 50
- google random number generator
- random number generator list 1 10
- random number generator pairs
- pick random number between
- random number generators
- best random number generator