Lab 1: Random Number Generation

Random Number

A random number is a number that is generated by a process, whose outcome is unpredictable, and which cannot be subsequently reliably reproduced. Random numbers are important in statistical analysis and probability theory.

Pseudo Random Number

A pseudo-random number generator (PRNG) is a finite state machine with an initial value called the seed [4]. Upon each request, a pseudo-random number generator will return a pseudo-random number based on some deterministic computation or algorithm. The generation of pseudo-random numbers is an important and common task in computer programming. The word pseudo-random is used because the numbers are not random in the sense that they are completely unpredictable and independent of each other. However, they are sufficiently random for practical purposes.

Methods of Generating Random Numbers

1. Linear Congruential Method

   1. Mix Linear Congruential Method

   2. Additive Congruential Method

   3. Multiplicative Congruential Method

   4. Arithmetic Congruential Method

2. Mid Square Method

Linear Congruential Method

1. Mix Linear Congruential method:

Definition

Linear congruential generators (LCGs) are a class of pseudorandom number generators (PRNGs) that generate a sequence of integers [0, m-1] calculated with a linear equation of the form:

Xn+1 = (aXn + c) mod m

where X is the sequence of pseudorandom values m, 0 < m - the "modulus" a, 0 < a < m - the "multiplier" c, 0 <= c < m - the "increment" X0, 0 <= X0 < m - the "seed" or "start value".

Algorithm

1. Start

2. Input the values of a, c, m and X0

3. Set i = 0

4. Generate Xn+1 = (aXn + c) mod m

5. Set i = i + 1

6. If i < n, goto step 4, otherwise goto step 7

7. End

Program

Mixed Linear Congruential Method

Output

Generate by running the program.

1. Multiplicative Congruential Method:

Definition

Multiplicative congruential generators (MCGs) are a class of pseudorandom number generators (PRNGs) that generate a sequence of integers [0, m-1] calculated with a linear equation of the form:

Xn+1 = (aXn) mod m

where X is the sequence of pseudorandom values m, 0 < m - the "modulus" a, 0 < a < m - the "multiplier" X0, 0 <= X0 < m - the "seed" or "start value".

Algorithm

1. Start

2. Input the values of a, m and X0

3. Set i = 0

4. Generate Xn+1 = (aXn) mod m

5. Set i = i + 1

6. If i < n, goto step 4, otherwise goto step 7.

7. End

Program

Multiplicative Congruential Method

Output

Generate by running the program.

1. Additive Congruential Method:

Definition

Additive congruential generators (ACGs) are a class of pseudorandom number generators (PRNGs) that generate a sequence of integers [0, m-1] calculated with a linear equation of the form:

Xn+1 = (Xn + c) mod m

where X is the sequence of pseudorandom values m, 0 < m - the "modulus" c, 0 <= c < m - the "increment" X0, 0 <= X0 < m - the "seed" or "start value".

Algorithm

1. Start

2. Initialize X1 and X2 as seed values.

3. Input n (number of random values to generate) and m (modulus value).

4. Display "Generated numbers: X1 X2".

5. Set i = 2.

6. Repeat the following steps n - 2 times:

   1. Calculate the next random number:

      next = (X1 + X2) % m

   2. Display next.

   3. Update X1 and X2:

      X1 = X2 X2 = next

   4. Increment i by 1.

7. End the loop.

8. Display "Random numbers generated."

9. End

Program

Additive Congruential Method

Output

Generate by running the program.

1. Arithmetic Congruential Method:

Definition

Arithmetic congruential generators (ACGs) are a class of pseudorandom number generators (PRNGs) that generate a sequence of integers [0, m-1] calculated with a linear equation of the form:

Xn+1 = Xn-1 + Xn

where X is the sequence of pseudorandom values m, 0 < m - the "modulus" X0, 0 <= X0 < m - the "seed" or "start value".

Algorithm

1. Start

2. Initialize X1 and X2 as seed values.

3. Input n (number of random values to generate) and m (modulus value).

4. Display "Generated numbers: X1 X2".

5. Set i = 2.

6. Repeat the following steps n - 2 times:

   1. Calculate the next random number:

      next = (X1 + X2) % m

   2. Display next.

   3. Update X1 and X2:

      X1 = X2 X2 = next

   4. Increment i by 1.

7. End the loop.

8. Display "Random numbers generated."

9. End

Program

Arithmetic Congruential Method

Output

Generate by running the program.

Mid Square Method

Definition

The middle-square method is a method of generating pseudorandom numbers. In practice it is not a good method, since its period is usually very short and it has some severe weaknesses, such as the output sequence almost always converging to zero.

Algorithm

1. Start

2. Input the value of seed X0

3. Set i = 0

4. Generate Xn+1 = (Xn)^2

5. Set i = i + 1

6. If i < n, goto step 4, otherwise goto step 7.

7. End

Program

Middle Square Method

Output

Generate by running the program.