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

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download