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

X is the sequence of pseudo-random values.
m, 0< m- modulus.
a, 0< a <m- multiplier.
c, 0< = c<m- increment.
x0, 0⇐x0<m- the seed or start value.

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

To get started, the algorithm requires an initial Seed, which must be provided by some means.
The appearance of randomness is provided by performing modulo arithmetic.

#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

Wiki

Table of Contents

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

Switching to int instead of double

References