Changeset a82a8f4 for doc/theses/thierry_delisle_PhD/code/utils.hpp

Timestamp:

Jul 21, 2020, 4:59:34 PM (5 years ago)

Author:

Thierry Delisle <tdelisle@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

c0587193

Parents:

50d529e

Message:

Added two new variants to the ready queue which are based on the idea of running the RNG backwards in certain cases

File:

• doc/theses/thierry_delisle_PhD/code/utils.hpp (modified) (1 diff)

doc/theses/thierry_delisle_PhD/code/utils.hpp

@@ -35 +35 @@
 };
 
+// class Random {
+// private:
+//      unsigned int seed;
+// public:
+//      Random(int seed) {
+//              this->seed = seed;
+//      }
+
+//      /** returns pseudorandom x satisfying 0 <= x < n. **/
+//      unsigned int next() {
+//              seed ^= seed << 6;
+//              seed ^= seed >> 21;
+//              seed ^= seed << 7;
+//              return seed;
+//      }
+// };
+
+constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b);
+constexpr uint64_t extendedEuclidX(uint64_t a, uint64_t b){
+    return (b==0) ? 1 : extendedEuclidY(b, a - b * (a / b));
+}
+constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b){
+    return (b==0) ? 0 : extendedEuclidX(b, a - b * (a / b)) - (a / b) * extendedEuclidY(b, a - b * (a / b));
+}
+
 class Random {
 private:
-        unsigned int seed;
+        uint64_t x;
+
+        static constexpr const uint64_t M  = 1ul << 48ul;
+        static constexpr const uint64_t A  = 25214903917;
+        static constexpr const uint64_t C  = 11;
+        static constexpr const uint64_t D  = 16;
+
+public:
+        static constexpr const uint64_t m  = M;
+        static constexpr const uint64_t a  = A;
+        static constexpr const uint64_t c  = C;
+        static constexpr const uint64_t d  = D;
+        static constexpr const uint64_t ai = extendedEuclidX(A, M);
 public:
         Random(int seed) {
-                this->seed = seed;
+                this->x = seed * a;
         }
 
         /** returns pseudorandom x satisfying 0 <= x < n. **/
         unsigned int next() {
-                seed ^= seed << 6;
-                seed ^= seed >> 21;
-                seed ^= seed << 7;
-                return seed;
-        }
+                //nextx = (a * x + c) % m;
+                x = (A * x + C) & (M - 1);
+                return x >> D;
+        }
+        unsigned int prev() {
+                //prevx = (ainverse * (x - c)) mod m
+                unsigned int r = x >> D;
+                x = ai * (x - C) & (M - 1);
+                return r;
+        }
+
+        void set_raw_state(uint64_t _x) {
+                this->x = _x;
+        }
+
+        uint64_t get_raw_state() {
+                return this->x;
+        }
 };