Differences

This shows you the differences between two versions of the page.

--- chess:programming:prng_pseudo_random_number_generator:linear_congruential_generator [2021/10/31 19:28] – peter
+++ chess:programming:prng_pseudo_random_number_generator:linear_congruential_generator [2021/10/31 20:17] (current) – peter
@@ Line 21: / Line 21: @@
   * 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>
+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>
+.00025194
+.000252278
+.000252279
+.000252279
+.000252279
+.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>
+.41797e+06
+.70898e+07
+.54492e+07
+.27246e+08
+.13623e+09
+.09122e+09
+.86615e+09
+.40836e+08
+-5.90786e+08
+.34104e+09
+...
+</code>
 ----
@@ Line 27: / Line 164: @@
 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