Random Number Generation (RNG) Pembangkitan Bilangan

Random Number Generation (RNG) – Pembangkitan Bilangan Random

Random Number Generation

1

Definition of RNG • RNG suatu algoritma yg digunakan utk menghasilkan urutan angka2 sbg hasil perhitungan dgn komp., yg diketahui distribusinya shg angka2 tsb muncul sec. random & digunakan terus-menerus Sequence/urutan Distribusi Munculnya angka2 secara random


Umumnya default: distribusi uniform 2

Applications of RNG • • • • • •

in gambling, statistical sampling, computer simulation, cryptography, completely randomized design, and other areas where producing an unpredictable result is desirable. Random Number Generation

3

Applications of RNG • In general, where unpredictability is paramount — such as in security applications — hardware generators are generally preferred. • RNG are very useful in developing Monte Carlo method simulations as debugging is facilitated by the ability to run the same sequence of random numbers again by starting from the same random seed. • They are also used in cryptography so long as the seed is secret. Sender and receiver can generate the same set of numbers automatically to use as keys. Random Number Generation

4

Description of random number • Dapat dinyatakan dalam: – Table random number – Electronic random number – Congruential pseudo random number Yang sering digunakan


5

Pseudo RNG (PRNG) • A PRNG also known as a deterministic random bit generator (DRBG), • is an algorithm for generating a sequence of numbers that approximates the properties of random numbers.


6

Pseudo RNG (PRNG) • The generation of pseudo-random numbers is an important and common task in computer programming. • Uses computational algorithms that produce long sequences of apparently random results, • It is determined by a shorter initial value known as a seed or key


7

Pseudo RNG (PRNG) • One of the most common PRNG is the linear congruential generator, which uses the recurrence :

X n +1 = (a * X n + b) mod m X: random number; a: koefisien; b: konstanta; m: modulo.

Additive/arithmatic PRNG

1

Lebih besar dari √m Bernilai ganjil bila m bernilai pangkat dua, & bukan kelipatan m

Note: pemilihan X0 adalah: integer, ganjil, cukup besar Random Number Generation

8

The other kinds of PRNG • Multiplicative PRNG

X n +1 = (a * X n ) mod m


2

9

Random Number Generation Desirable Attributes: – Uniformity – Independence – Efficiency – Replicability – Long Cycle Length


10

Random Number Generation (cont.) Each random number Rt is an independent sample drawn from a continuous uniform distribution between 0 and 1 1 , 0 ≤ x ≤ 1 pdf: f(x) =  0 , otherwise


11

Techniques for Generating Random Number MidSquare Example: X0 = 7182 (seed) X 02 = 51581124 ==> R1 = 0.5811 X 02 = (5811) 2 = 33767721 ==> R2 = 0.7677 etc.


12

Techniques for Generating Random Number (cont.) Note: Cannot choose a seed that guarantees that the sequence will not degenerate and will have a long period. Also, zeros, once they appear, are carried in subsequent numbers. 2 X Ex1: X0 = 5197 (seed) 0 = 27008809 2 X ==> R1 = 0.0088 1 = 00007744 ==> R2 = 0.0077 Ex2: X0 = 4500 (seed) X 02= 20250000 ==> R1 = 0.2500 X12= 06250000 ==> R2 = 0.2500 Random Number Generation

13

Techniques for Generating Random Number (cont.) Multiplicative Congruential Method: Basic Relationship Xi+1 = a Xi (mod m), where a ≥ 0 and m ≥ 0 Most natural choice for m is one that equals to the capacity of a computer word. m = 2b (binary machine), where b is the number of bits in the computer word. m = 10d (decimal machine), where d is the number of digits in the computer word. Random Number Generation

14

Techniques for Generating Random Number (cont.) The max period(P) is: For m a power of 2, say m = 2b, and c ≠ 0, the longest possible period is P = m = 2b , which is achieved provided that c is relatively prime to m (that is, the greatest common factor of c and m is 1), and a = 1 + 4k, where k is an integer. For m a power of 2, say m = 2b, and c = 0, the longest possible period is P = m / 4 = 2b-2 , which is achieved provided that the seed X0 is odd and the multiplier, a, is given by a = 3 + 8k or a = 5 + 8k, for some k = 0, 1,...


15

Techniques for Generating Random Number (cont.) For m a prime number and c = 0, the longest possible period is P = m - 1, which is achieved provided that the multiplier, a, has the property that the smallest integer k such that ak - 1 is divisible by m is k = m - 1,


16

Techniques for Generating Random Number (cont.) (Example 1) Using the multiplicative congruential method, find the period of the generator for a = 13, m = 26, and X0 = 1, 2, 3, and 4. The solution is given in next slide. When the seed is 1 and 3, the sequence has period 16. However, a period of length eight is achieved when the seed is 2 and a period of length four occurs when the seed is 4.


17

Techniques for Generating Random Number (cont.) Period Determination Using Various seeds i

Xi

Xi

Xi

Xi

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 13 41 21 17 29 57 37 33 45 9 53 49 61 25 5 1

2 26 18 42 34 58 50 10 2

3 39 59 63 51 23 43 47 35 7 27 31 19 55 11 15 3

4 52 36 20 4


18

Techniques for Generating Random Number (cont.) Linear Congruential Method: Xi+1 = (aXi + c) mod m, i = 0, 1, 2.... (Example 2) let X0 = 27, a = 17, c = 43, and m = 100, then X1 = (17*27 + 43) mod 100 = 2 R1 = 2 / 100 = 0.02 X2 = (17*2 + 43) mod 100 = 77 R2 = 77 / 100 = 0.77 ......... Random Number Generation

19

Exercises/Tugas1 1. 2. 3. 4.

Diketahui x0 = 12357, a = 197, m = 1387, dan b = 2357. Uraikan sec. berurut utk mendapatkan bil. Random sebanyak 10 kali, dgn menggunakan arithmetic PRNG. Diketahui x0 = 12357, a = 197, m = 1387. Uraikan sec. berurut utk mendapatkan bil. Random sebanyak 10 kali, dgn menggunakan muliplicative PRNG. Untuk Example 1 di atas, uraikan bila x0 yang bernilai lainnya, silahkan ditentukan sendiri nilai x0 tersebut dan bagaimana pengulangan data random semunya. Untuk example 2, lanjutkan dengan perhitungan pembangkitan random berikutnya misal sampai dengan 100 kali pembangkitan (gunakan excel). Apakah data pembangkitan random semu tersebut muncul antara 0 dan 1.


20

References • Herman D. Hughes, CSE808 Modeling and Discrete Simulation, Michigan State University, Fall 2003 • Tri Harsono, Materi Ajar Modeling and Simulation, PENS, 2013


21

Random Number Generation (RNG) Pembangkitan Bilangan

Recommend Documents