Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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:

<code>
Xn+1 = (aXn + c) mod c
</code>

**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.

----

<code cpp>
#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;
} 
</code>

returns:

<code cpp>
0 3 2 5 4 7 6 1
</code>

<WRAP info>
**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:
    - M and c are Relatively Prime so the gcd(M, c) = 1.
    - (a-1) is divisible by all prime factors of M.
    - (a-1) mod 4 = 0 if (M mod 4) = 0

</WRAP>


----

<code cpp>
#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;
}
</code>

returns:

<code cpp>
0.00025194
0.000252278
0.000252279
0.000252279
0.000252279
0.000252279
</code>

----

===== Switching to int instead of double =====

This gives some nice results:

<code cpp>
#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;
}
</code>

returns:

<code cpp>
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
...
</code>

----

===== 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