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:33] – 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>
 ----
@@ Line 35: / Line 81: @@
 {
   static double prev = 0;
-  prev = A * prev + fmod(C, RAND_MAX);
+  // WRONG: prev = A * prev + fmod(C, RAND_MAX);
+  prev = (A * prev + C) % (RAND_MAX+1);
   return prev;
 }
@@ Line 75: / Line 122: @@
 {
   static int prev = 1;
-  prev = A * prev + (C % RAND_MAX);
+  // WRONG: prev = A * prev + fmod(C, RAND_MAX);
+  prev = (A * prev + C) % (RAND_MAX+1);
   return prev;
 }
@@ Line 116: / 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