Pseudo random number using the Linear Congruential Generator

The Linear Congruential Generator is one of the methods of generating a random number. This is a well-known algorithm that consumes less amounts of time and memory because of the simple implementation methods.

LCG logic

The logic that LCG uses to generate a random number is based on a discontinuous piecewise linear equation. It generates a sequence of randomized numbers using a mathematical equation that takes a total of 4 inputs.

Xn+1 = (a*Xn + c) mod m

  • X: Seed (base value) to generate more numbers (X>=0)(X >= 0)

  • a: Multiplier (m>a>=0)(m>a>=0)

  • c: Increment (m>c>=0)(m>c>=0)

  • m: Modulus (m>a,c)(m>a,c)

Block Diagram of LCG
Block Diagram of LCG

Explanation

The illustration above is the explanation of LCG logic. The block diagram shows arithmetic operations that are carried out in LCG. This is the base diagram, but the subtractor and comparator can be removed and replaced by a multiplexer. The variables a, m, and c are the inputs, and the X is the random number generated by LCG.

Example

In the coding widget below, we have the implementation of LCG using C++.

#include <iostream>
#include <vector>
using namespace std;
void LCG(vector<int>& rand_num)
{
int X = 12;// Seed value(Base)
int m = 15;// Modulus parameter
int a = 2;// Multiplier term
int c = 4;// Increment term
rand_num[0] = X;
for (int i = 1; i <10 ; i++)
{
//passing value to the equation
rand_num[i] = ((rand_num[i - 1] * a) + c) % m;
}
}
int main()
{
vector<int> rand_num(8);
LCG(rand_num);
for (int i = 0; i < 8; i++)
{
cout << rand_num[i] << " ";
}
return 0;
}

Explanation

  • Line 5-18: LCG is implemented by passing the declared variables to the equation using a for-loop, and those values are stored in rand_num vector.

  • Line 22-27: We called LCG function and displayed the vector using a for-loop.

Copyright ©2024 Educative, Inc. All rights reserved