Systems Simulation Chapter 7: Random-Number Generation PDF

Chapter 6 - Random-Number Generation

Linear Congruential Method. Generating Random Numbers. Prof. Dr. Mesut Güneş c without actually generating any numbers. • Empirical tests: applied to actual ...

Random Number Generators

number generator is called a Linear Congruential Generator (LCG) and is defined by a recursion as follows: Zn+1 = (aZn + c) mod m n ≥ 0

UNIT 5:Random number generation And Variation Generation

EXAMPLE 1 Use the linear congruential method to generate a sequence of random numbers with X0 = 27 a= 17

On-line Numerical Recipes in C http://lib-www.lanl.gov/numerical

The linear congruential method has the advantage of being very fast requiring Park and Miller [1] have surveyed a large number of random number generators.

RANDOM NUMBER GENERATION AND ITS BETTER TECHNIQUE

When the increment c=0 it is called multiplicative congruential method. • Linear congruential random number generators are widely used in simulation and.

Chapter 4: (01) Random Number Generation

▫ linear congruential generator (LCG). ➢ a recursive algorithm for The only positive integer that (exactly) divides both m and c is 1 (i.e. c and m have no ...

Chapter 7 Random-Number Generation

▫ The seed for a linear congruential random-number generator: □ Is the integer value X0 that initializes the random-number sequence. □ Any value in the

Overview of lecture slides 01

Linear congruential algorithm. Simple traditional algorithm: Xn+1 = (aXn + c) mod m Good pseudo-random number generators exist

multiplicative congruential random number generators with modulus

Congruential generator discrepancy

Chapter 6 - Random-Number Generation

The selection of the values for a c

Random numbers and Monte Carlo(*) Techniques

(pseudo)random numbers generation: example I1 - “Linear congruential method (LCM)”. (Lehemer 1948). In+1 = (a In + c) mod m. Limits of the algorithm:.

993SM - Laboratory of Computational Physics lecture II - part I

17 mar 2021 (pseudo)random numbers generation: example I1 - “Linear congruential method (LCM)”. (Lehemer 1948). In+1 = (a In + c) mod m.

Linear Congruential Generator

Xn+1 = (a*Xn + c)%m – Linear congruential series Code for linear congruential generator ... random number a in (a1a2) distributed as g(a).

993SM - Laboratory of Computational Physics lecture II March 9 2022

9 mar 2022 (pseudo)random numbers generation: example I1 - “Linear congruential method (LCM)”. (Lehemer 1948). In+1 = (a In + c) mod m.

Chapter 7 Random-Number Generation

Techniques for Generating Random. Numbers. ? Linear Congruential Method (LCM). The selection of the values for a c

Chapter 4: (01) Random Number Generation

Linear congruential generator (LCG) A sequence of pseudo-random numbers U(i)

Chapter 7 Random-Number Generation

Techniques for Generating Random. Numbers. ? Linear Congruential Method (LCM). The selection of the values for a c

Systems Simulation Chapter 7: Random-Number Generation

22 apr 2014 The linear congruential method (LCM) produces a sequence of integers X1

Random numbers and Monte Carlo(*) Techniques

(pseudo)random numbers generation: example I1 - “Linear congruential method (LCM)”. (Lehemer 1948). In+1 = (a In + c) mod m. Limits of the algorithm:.

[PDF] Chapter 6 - Random-Number Generation

Combined Linear Congruential Method • Tests for Random Numbers • Real Random Numbers Prof Dr Mesut Güne? ? Ch 6 Random-Number Generation

[PDF] Chapter 4: (01) Random Number Generation

Pseudo-Random Numbers 8 ? linear congruential generator (LCG) ? a recursive algorithm for producing a sequence of pseudorandom numbers

[PDF] Random Number Generators - Columbia University

The most common and easy to understand and implement random number generator is called a Linear Congruential Generator (LCG) and is defined by a recursion as

[PDF] 2WB05 Simulation Lecture 5: Random-number generators

Most random-number generators in use today are linear congruential generators They produce a sequence of integers between 0 and m ? 1 according to

[PDF] Chapter 7 Random-Number Generation

Techniques for Generating Random Numbers ? Linear Congruential Method (LCM) The selection of the values for a c m and X0 drastically

[PDF] Linear Congruential Generator - CERN Indico

Linear Congruential Generator ? Goal: Generate Un uniform in the interval [01) ? Generate Xn in [0m) Un = Xn/m ? Xn+1 = (a*Xn + c) m – Linear

[PDF] RANDOM NUMBER GENERATION AND ITS BETTER TECHNIQUE

Random number generators based on linear recurrences modulo 2 are among the When the increment c=0 it is called multiplicative congruential method

[PDF] Generating random numbers

Linear congruential generator generate more than m/1000 numbers Composite generator X n+1 = a 1 X n + c Shuffling a random number generator

[PDF] Systems Simulation Chapter 7: Random-Number Generation

22 avr 2014 · The linear congruential method (LCM) produces a sequence of integers X1X2 between 0 and m ? 1 by following a recursive relationship Xi+1

[PDF] Random Number Generator (RNG)

SNU/NUKE/EHK Random Number Generation (cont ) PDF: ?Linear Congruential Generator divisor of c and m is 1) and the multiplier a-1 = 4k where

How is the linear congruential method used to generate random numbers?
A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms.
What is the formula for the LCG method?
The simple form of the LCG algorithm is as follows: X n+1 = (a X n +b) mod m , n? 0 ; A constant in the above algorithm is called a multiplier, the constant b is called an increment, and the constant m is called modulus.
What is the formula for linear congruential generator?
An LCG is defined by the equation L_n ? (a ? L_n_-₁ + c) mod m, where the values of m (the modulus, a positive integer), a (the multiplier, a positive integer less than m) and c (the increment, either 0 or a positive integer less than m) are chosen by the designer of the LCG.
Full-Period Theorem (Hull and Dobell, 1966) In general, cycle length determined by parameters m, a, and c: The LCG Zi = (aZi-1 + c) (mod m) has full period (m) if and only all three of the following hold: 1. c and m are relatively prime (i.e., the only positive integer that divides both c and m is 1).

Systems Simulation Chapter 7: Random-Number Generation

Systems Simulation

Chapter 7: Random-Number Generation

Fatih Cavdur

fatihcavdur@uludag.edu.tr

April 22, 2014

Systems Simulation Chapter 7: Random-Number Generation

Introduction

Random Numbers (RNs) are a necessary basic ingredient in the simulation of almost all discrete systems. Most computer languages have a subroutine, object or function that generates a RN. Similarly, simulation languages generate RNs that are usedto generate event times and other random variables. We will look at the generation of RNs and some randomness tests in this chapter. Next chapter will show how we can use them to generate RVs. Systems Simulation Chapter 7: Random-Number Generation

Properties of RNs

A sequence of RNs,R1,R2,..., must have two important statistical properties: uniformity and independence. Each RN,Rimust be an independent sample drawn from a continuous uniform distribution between 0 and 1.

0,otherwise

E(R) =?

1 0 rdr=1 2

V(R) =E(R2)-[E(R)]2=1

12 Systems Simulation Chapter 7: Random-Number Generation

Properties of RNs

Some Consequences of Uniformity and Independence

If the interval [0,1] is divided intonclasses (sub-intervals) of equal length, the expected number of observations in each interval isN/n, whereNis the total number of observations. The probability of observing a value in a particular interval is independent of the previous values drawn. Systems Simulation Chapter 7: Random-Number Generation

Generation of Pseudo-RNs

Problems and Errors

Numbers might not be uniformly distributed.

Numbers might be discrete-valued.

The mean / variance of the generated numbers might be too high or too low.

There might be dependence, such as,

autocorrelation numbers successively higher or lower than adjacent numbers several numbers above the mean followed several numbers below the mean Systems Simulation Chapter 7: Random-Number Generation

Generation of Pseudo-RNs

Important Considerations

The routine should be fast.

The routine should be portable.

The routine should have a sufficiently long cycle.

The RNs should be replicable (repeatable).

Most importantly, the generated RNs should closely approximate the ideal statistical properties of uniformity and independence. Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Linear Congruential Method

The linear congruential method (LCM) produces a sequence of integers,X1,X2,...between 0 andm-1 by following a recursive relationship. X i+1= (aXi+c) modm,i= 0,1,2,... R i=Xi m,i= 1,2,... The initial valueX0is called the seed,ais called the multiplier,cis the increment andmis the modulus. Ifc= 0, it is known as themultiplicative congruential method, and ifc?= 0, it is called as themixed congruential method. Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Linear Congruential Method

Example

Use the LGM to generate a sequence of RNs with

X0= 27,a= 17,c= 43 andm= 100.

X 0= 27 X

1= (17×27 + 43) mod 100 = 2?R1=2

100= 0.02

2= (17×2 + 43) mod 100 = 77?R2=77

100= 0.77

3= (17×77 + 43) mod 100 = 52?R3=52

100= 0.52

Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Linear Congruential Method

Properties to Consider

Generated numbers must be approximately uniform and independent. Moreover, other properties, such asmaximum densityand maximum periodmust be considered. By maximum density is meant that the values assumed by

Ri,i= 1,2,..., leave no large gaps on [0,1].

In many simulation languages, values such asm= 231-1 and m= 248are in common use in generators. To help achieve maximum density and to avoid cycling, the generator should have the largest possible period. Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Linear Congruential Method

Properties to Consider

1Forma power of 2, saym= 2b, andc?= 0, the longest

possible period isP=m= 2b, which is achieved wheneverc is relatively prime tom(the greatest common factor ofcand mis 1) anda= 1 + 4k, wherekis an integer.

2Forma power of 2, saym= 2b, andc= 0, the longest

possible period isP=m/4 = 2b-2, which is achieved if the seedX0is odd and if the multipliera, is given bya= 3 + 8k ora= 5 + 8k, for somek= 0,1,....

3Forma prime number andc= 0, the longest possible period

isP=m-1, which is achieved whenever the multiplier,a, has the property that the smallest integerksuch thatak-1 is divisible bymisk=m-1. Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Linear Congruential Method

Properties to Consider-Example 1

Using the multiplicative LCM, find the period of the generator for

a= 13,m= 26= 64 andX0= 1,2,3,4. When the seed is 1 or 3,the sequence has a period of 16. Period lengths of 8 and 4 isachieved when the seed is 2 and 4, respectively. In this example,

m= 26= 64 andc= 0. The max period is thenP=m/4 = 16.

Table :Periods for Various Seeds

i XiXiXiXi

0 1 2 3 4

1 13 26 39 52

2 41 18 59 36

3 21 42 63 20

4 17 34 51 4

5 29 58 23 52

6 57 50 43 36

7 37 10 47 20

8 33 2 35 4

Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Linear Congruential Method

Properties to Consider-Example 2

Witha= 13 = 1 + 4×k= 1 + 4×3 ,c= 3 is relatively prime to m= 16 andX0= 1, we have the following sequence with the max period ofP=m= 2b= 24= 16:

Table :Max Period

i Xii Xi

1 0 9 8

2 3 10 11

3 10 11 2

4 5 12 13

5 4 13 12

6 7 14 15

7 14 15 6

8 9 16 1

Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Linear Congruential Method

Properties to Consider-Example 3

Witha= 3 ,c= 0, prime numberm= 17 andX0= 1, we have the following sequence with the max period ofP=m-1 = 16 whenk= 16 is the smallest integer such thatak-1 = 316-1 (which equals to 43,046,720) is divisible byk=m-1 = 16 (verify that fork<16,ak-1 is not divisible byk=m-1):

Table :Max Period

i Xii Xi

1 3 9 14

2 9 10 8

3 10 11 7

4 13 12 4

5 5 13 12

6 15 14 2

7 11 15 6

8 16 16 1

Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Combined Linear Congruential Method

Combined Linear Congruential Generators

A RNG with a period of 231-1≈2×109is no longer adequate due to the increasing complexity. So, combine two or more multiplicative congruential generators in such a way that the combined generator has good statistical properties and a longer period. IfWi1,Wi2,...,Wikare any independent, discrete-valued RVs (not necessarily identically distributed), but one of them, say W i1, is uniform on the integers from 0 tom1-2, then, the following is uniform on the integers from 0 tom1-2. W i=(( k? j=1W ij)) modm1-1 Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Combined Linear Congruential Method

Combined Linear Congruential Generators

LetXi1,Xi2,...Xikbe theith output fromkdifferent

multiplicative congruential generators. X i=(( k? j=1(-1)j-1Xij)) modm1-1 R i=? Xi m1,Xi>0 m 1-1 m1,Xi= 0

The maximum period is given by

P=(m1-1)(m2-1)...(mk-1)

2k-1 Systems Simulation Chapter 7: Random-Number Generation

Techniques for RN Generation

Combined Linear Congruential Method

Combined Linear Congruential Generators

Algorithm by L"Ecuyer (1998)

Step (1)

Select seedX1,0in the range [1,2,147,483,562] for the first generator, and seedX2,0in the range [1,2,147,483,398] for the second. Setj= 0.

Step (2)Evaluate each individual generator.

1,j+1= 40,014X1,jmod 2,147,483,563

Xquotesdbs_dbs17.pdfusesText_23

[PDF] Systems Simulation Chapter 7: Random-Number Generation

How is the linear congruential method used to generate random numbers?

What is the formula for the LCG method?

What is the formula for linear congruential generator?

Systems Simulation

Chapter 7: Random-Number Generation

Fatih Cavdur

April 22, 2014

Introduction

Introduction

Properties of RNs

Properties of RNs

0,otherwise

E(R) =?

V(R) =E(R2)-[E(R)]2=1

Properties of RNs

Properties of RNs

Some Consequences of Uniformity and Independence

Generation of Pseudo-RNs

Generation of Pseudo-RNs

Problems and Errors

Numbers might not be uniformly distributed.

Numbers might be discrete-valued.

There might be dependence, such as,

Generation of Pseudo-RNs

Generation of Pseudo-RNs

Important Considerations

The routine should be fast.

The routine should be portable.

The RNs should be replicable (repeatable).

Techniques for RN Generation

Linear Congruential Method

Linear Congruential Method

Techniques for RN Generation

Linear Congruential Method

Linear Congruential Method

Example

Use the LGM to generate a sequence of RNs with

X0= 27,a= 17,c= 43 andm= 100.

1= (17×27 + 43) mod 100 = 2?R1=2

100= 0.02

2= (17×2 + 43) mod 100 = 77?R2=77

100= 0.77

3= (17×77 + 43) mod 100 = 52?R3=52

100= 0.52

Techniques for RN Generation

Linear Congruential Method

Linear Congruential Method

Properties to Consider

Ri,i= 1,2,..., leave no large gaps on [0,1].

Techniques for RN Generation

Linear Congruential Method

Linear Congruential Method

Properties to Consider

1Forma power of 2, saym= 2b, andc?= 0, the longest

2Forma power of 2, saym= 2b, andc= 0, the longest

3Forma prime number andc= 0, the longest possible period

Techniques for RN Generation

Linear Congruential Method

Linear Congruential Method

Properties to Consider-Example 1

Table :Periods for Various Seeds

0 1 2 3 4

1 13 26 39 52

2 41 18 59 36

3 21 42 63 20

4 17 34 51 4

5 29 58 23 52

6 57 50 43 36

7 37 10 47 20

8 33 2 35 4

Techniques for RN Generation

Linear Congruential Method

Linear Congruential Method

Properties to Consider-Example 2

Table :Max Period

1 0 9 8

2 3 10 11

3 10 11 2

4 5 12 13