Table of Contents

Chess - Programming - PRNG (Pseudo Random Number Generator) - Linear Congruential Generator

Linear Congruential Generator is most common and oldest algorithm for generating pseudo-randomized numbers.

The generator is defined by the recurrence relation: 

Xn+1 = (aXn + c) mod c

NOTE: where

The next random integer is generated using the previous random integer, the integer constants, and the integer modulus. 

#include <iostream>
using namespace std;
 
int main()
{
  int M = 8;
  int a = 5;
  int c = 3;
  int X = 1;
  int i;
 
  for(i=0; i<8; i++)
  {
    X = (a * X + c) % M;
    std::cout << X << “ “;
  }
  return 0;
}

returns: 

0 3 2 5 4 7 6 1

NOTE: This generates a sequence of numbers from 0 to 7 in a fairly scrambled way.

  • If we were to extend the loop we would find that this sequence would repeat over and over.
  • This sequence happens to have a period of M, but other choices for a, and c could have smaller periods (a=3, c=3 has a period of 4).

To make this more useful we will need a large period.

  • To do this we have to choose appropriate values for M, a, and c.
  • To have a maximum period of M the following conditions must be met:
    1. M and c are Relatively Prime so the gcd(M, c) = 1.
    2. (a-1) is divisible by all prime factors of M.
    3. (a-1) mod 4 = 0 if (M mod 4) = 0
#include <iostream>
#include <cmath>
 
static const double A = 0.001342;
static const double C = 0.00025194;
static const double RAND_MAX = 1.0;
 
double rand()
{
  static double prev = 0;
  // WRONG: prev = A * prev + fmod(C, RAND_MAX);
  prev = (A * prev + C) % (RAND_MAX+1);
  return prev;
}
 
int main(int argc, char **argv)
{
  for(int i=0; i<6; i++)
    std::cout << rand() << "\n";
  return 0;
}

returns: 

0.00025194
0.000252278
0.000252279
0.000252279
0.000252279
0.000252279

Switching to int instead of double

This gives some nice results: 

#include <iostream>
#include <cmath>
 
static const int A = 5;
static const int C = 3;
static const int RAND_MAX = 8;
 
double rand()
{
  static int prev = 1;
  // WRONG: prev = A * prev + fmod(C, RAND_MAX);
  prev = (A * prev + C) % (RAND_MAX+1);
  return prev;
}
 
int main(int argc, char **argv)
{
  for(int i=0; i<100; i++)
    std::cout << rand() << "\n";
  return 0;
}

returns: 

8
43
218
1093
5468
27343
136718
683593
3.41797e+06
1.70898e+07
8.54492e+07
4.27246e+08
2.13623e+09
2.09122e+09
1.86615e+09
7.40836e+08
-5.90786e+08
1.34104e+09
...

References

https://en.wikipedia.org/wiki/Linear_congruential_generator

https://www.dreamincode.net/forums/topic/24225-random-number-generation-102/

https://medium.com/@sddkal/c-reimplementing-default-congruential-random-generator-6000936f38a3

https://codeforces.com/blog/entry/61587