COMPUTATIONAL THINKING

By

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

_{PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY}

• Problem:
• Use the linear congruential method to generate a uniform set of pseudo-random numbers.
• Algorithm development
• Random number generators are frequently used in computing science for among their things, testing and analysing the behavior of algorithms.
• The sequence of random numbers should exhibit the following behavior.

1. The sequence should appear as though each number had occurred by chance.

2. Each number should have a specified probability of falling within a given range.

Dept of CSE

2025 - 26

GENERATION OF PSEUDO-RANDOM NUMBERS

PVPSIT (Autonomous)

Problem Solving Techniques

• The approach generally taken in computing science for random number generation is to simulate random processes by deterministically producing a sequence of numbers that appear to exhibit random behavior.
• These sequences are predictable in advance and for this reason they are usually referred to as pseudo-random sequences.
• There are many methods for generating pseudo-random numbers.
• Midsquare method
• LINEAR CONGRUENTIAL METHOD (LCM)
• Combined Linear Congruential Generators (CLCG)
• Random-Number Streams

​

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

• The implementation of the linear congruential method is very straight forward. Successive members of the linear congruential sequence {x} are generated using the expression:
• x_{n+1 =} (ax_n + b) mod m for n>=0,
• Where the parameters a, b, m, and X_o must be carefully chosen in advance according to certain criteria. The parameters a, b, and m are referred to as the multiplier, increment, and modulus respectively.
• These results can be summarized as follows: all parameters should be integers greater than or equal to zero and m should be greater than x₀, a, and b.

​

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

• Parameter x_o: The parameter x_o can be chosen arbitrarily within the range

0 <= X0 < m.

• Parameter m: The value of m should be greater than or equal to the length of the random sequence required. In addition it must be possible to do the computation (a*x + b) mod m without roundoff.
• Parameter a: The choice of a depends on the choice of m.
• If m is a power of 2 then a should satisfy the condition:

a mod 8 = 5

• If m is a power of 10, then a should be chosen such that:

a mod 200 = 21

​

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

• Further requirements on a are that it should be larger than √m and less than m-√m.
• (a-1) should be a multiple of every prime dividing into m, and if m is a multiple of 4 then (a-1) should also be a multiple of 4.
• These conditions, together with the requirement that b should be relatively prime to m are needed to guarantee that the sequence has a period of m.
• Parameter b: The constant b should be odd and not a multiple of 5.
• When a, b, and m are chosen according to the conditions outlined above a sequence of m pseudo-random numbers in the range 0 to (m-1) can be generated before the sequence begins to repeat.
• The below example is developed using the linear congruential method for an m value of 4096.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

• x_{n+1 =} (ax_n + b) mod m for n>=0,
• where,
• x, is the sequence of pseudo-random numbers
• m = 4096, 0 < m >= length of the random sequence required (m > x0, a, and b)
• a = 109 multiplier
• b = 853 increment
• x₀ = 2, 0 ≤ x₀ < m. (x₀ is called as the seed or start value)

Dept of CSE

2025 - 26

Example:

PVPSIT (Autonomous)

Problem Solving Techniques

• Step 0: Start
• Step 1: Initialize m = 4096.
• Step 2: Initialize a = 109
• Step 3: Initialize b = 853
• Step 4: Initialize x0 = 2
• Step 5: Compute Xn+1 = (a*xn+b) mod m (0 to m-1)
• Step 6: Display Xn+1 as result
• Step 7: Stop

Dept of CSE

2025 - 26

Algorithm:

PVPSIT (Autonomous)

Problem Solving Techniques

• Notes on design
• The linear congruential method is a simple, efficient and practical method for generating pseudo-random numbers.
• A uniform distribution of pseudo-random numbers can be used as a basis for generating other distributions such as the normal and exponential distributions.
• The theoretical basis for the choice of parameters involves a highly sophisticated analysis.
• Applications
• Analysis of algorithms, simulation problems and games.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques