Linear Congruence method for generating Pseudo Random Numbers
Linear Congruential Method is a class of Pseudo Random Number Generator (PRNG) algorithms used for generating sequences of random-like numbers in a specific range. This method can be defined as:
where,
X, is the sequence of pseudo-random numbers
m, ( > 0) the modulus
a, (0, m) the multiplier
c, (0, m) the increment
X0, [0, m) – Initial value of sequence known as seedm, a, c, and X0 should be chosen appropriately to get a period almost equal to m.
For a = 1, it will be the additive congruence method.
For c = 0, it will be the multiplicative congruence method.
Approach:
- Choose the seed value X0, Modulus parameter m, Multiplier term a, and increment term c.
- Initialize the required amount of random numbers to generate (say, an integer variable noOfRandomNums).
- Define a storage to keep the generated random numbers (here, vector is considered) of size noOfRandomNums.
- Initialize the 0th index of the vector with the seed value.
- For rest of the indexes follow the Linear Congruential Method to generate the random numbers.
randomNums[i] = ((randomNums[i – 1] * a) + c) % m
Finally, return the random numbers.
Below is the implementation of the above approach:
C++
// C++ implementation of the // above approach #include <bits/stdc++.h> using namespace std; // Function to generate random numbers void linearCongruentialMethod( int Xo, int m, int a, int c, vector< int >& randomNums, int noOfRandomNums) { // Initialize the seed state randomNums[0] = Xo; // Traverse to generate required // numbers of random numbers for ( int i = 1; i < noOfRandomNums; i++) { // Follow the linear congruential method randomNums[i] = ((randomNums[i - 1] * a) + c) % m; } } // Driver Code int main() { int Xo = 5; // Seed value int m = 7; // Modulus parameter int a = 3; // Multiplier term int c = 3; // Increment term // Number of Random numbers // to be generated int noOfRandomNums = 10; // To store random numbers vector< int > randomNums( noOfRandomNums); // Function Call linearCongruentialMethod( Xo, m, a, c, randomNums, noOfRandomNums); // Print the generated random numbers for ( int i = 0; i < noOfRandomNums; i++) { cout << randomNums[i] << " " ; } return 0; } |
Java
// Java implementation of the above approach import java.util.*; class GFG{ // Function to generate random numbers static void linearCongruentialMethod( int Xo, int m, int a, int c, int [] randomNums, int noOfRandomNums) { // Initialize the seed state randomNums[ 0 ] = Xo; // Traverse to generate required // numbers of random numbers for ( int i = 1 ; i < noOfRandomNums; i++) { // Follow the linear congruential method randomNums[i] = ((randomNums[i - 1 ] * a) + c) % m; } } // Driver code public static void main(String[] args) { // Seed value int Xo = 5 ; // Modulus parameter int m = 7 ; // Multiplier term int a = 3 ; // Increment term int c = 3 ; // Number of Random numbers // to be generated int noOfRandomNums = 10 ; // To store random numbers int [] randomNums = new int [noOfRandomNums]; // Function Call linearCongruentialMethod(Xo, m, a, c, randomNums, noOfRandomNums); // Print the generated random numbers for ( int i = 0 ; i < noOfRandomNums; i++) { System.out.print(randomNums[i] + " " ); } } } // This code is contributed by offbeat |
Python3
# Python3 implementation of the # above approach # Function to generate random numbers def linearCongruentialMethod(Xo, m, a, c, randomNums, noOfRandomNums): # Initialize the seed state randomNums[ 0 ] = Xo # Traverse to generate required # numbers of random numbers for i in range ( 1 , noOfRandomNums): # Follow the linear congruential method randomNums[i] = ((randomNums[i - 1 ] * a) + c) % m # Driver Code if __name__ = = '__main__' : # Seed value Xo = 5 # Modulus parameter m = 7 # Multiplier term a = 3 # Increment term c = 3 # Number of Random numbers # to be generated noOfRandomNums = 10 # To store random numbers randomNums = [ 0 ] * (noOfRandomNums) # Function Call linearCongruentialMethod(Xo, m, a, c, randomNums, noOfRandomNums) # Print the generated random numbers for i in randomNums: print (i, end = " " ) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the above approach using System; class GFG{ // Function to generate random numbers static void linearCongruentialMethod( int Xo, int m, int a, int c, int [] randomNums, int noOfRandomNums) { // Initialize the seed state randomNums[0] = Xo; // Traverse to generate required // numbers of random numbers for ( int i = 1; i < noOfRandomNums; i++) { // Follow the linear congruential method randomNums[i] = ((randomNums[i - 1] * a) + c) % m; } } // Driver code public static void Main(String[] args) { // Seed value int Xo = 5; // Modulus parameter int m = 7; // Multiplier term int a = 3; // Increment term int c = 3; // Number of Random numbers // to be generated int noOfRandomNums = 10; // To store random numbers int [] randomNums = new int [noOfRandomNums]; // Function call linearCongruentialMethod(Xo, m, a, c, randomNums, noOfRandomNums); // Print the generated random numbers for ( int i = 0; i < noOfRandomNums; i++) { Console.Write(randomNums[i] + " " ); } } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript program to implement // the above approach // Function to generate random numbers function linearCongruentialMethod(Xo, m, a, c, randomNums, noOfRandomNums) { // Initialize the seed state randomNums[0] = Xo; // Traverse to generate required // numbers of random numbers for (let i = 1; i < noOfRandomNums; i++) { // Follow the linear congruential method randomNums[i] = ((randomNums[i - 1] * a) + c) % m; } } // Driver Code // Seed value let Xo = 5; // Modulus parameter let m = 7; // Multiplier term let a = 3; // Increment term let c = 3; // Number of Random numbers // to be generated let noOfRandomNums = 10; // To store random numbers let randomNums = new Array(noOfRandomNums).fill(0); // Function Call linearCongruentialMethod(Xo, m, a, c, randomNums, noOfRandomNums); // Print the generated random numbers for (let i = 0; i < noOfRandomNums; i++) { document.write(randomNums[i] + " " ); } </script> |
Output:
5 4 1 6 0 3 5 4 1 6
The literal meaning of pseudo is false. These random numbers are called pseudo because some known arithmetic procedure is utilized to generate. Even the generated sequence forms a pattern hence the generated number seems to be random but may not be truly random.