Ignore:
Timestamp:
Jul 21, 2020, 4:59:34 PM (2 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
arm-eh, 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:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/code/utils.hpp

    r50d529e ra82a8f4  
    3535};
    3636
     37// class Random {
     38// private:
     39//      unsigned int seed;
     40// public:
     41//      Random(int seed) {
     42//              this->seed = seed;
     43//      }
     44
     45//      /** returns pseudorandom x satisfying 0 <= x < n. **/
     46//      unsigned int next() {
     47//              seed ^= seed << 6;
     48//              seed ^= seed >> 21;
     49//              seed ^= seed << 7;
     50//              return seed;
     51//      }
     52// };
     53
     54constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b);
     55constexpr uint64_t extendedEuclidX(uint64_t a, uint64_t b){
     56    return (b==0) ? 1 : extendedEuclidY(b, a - b * (a / b));
     57}
     58constexpr uint64_t extendedEuclidY(uint64_t a, uint64_t b){
     59    return (b==0) ? 0 : extendedEuclidX(b, a - b * (a / b)) - (a / b) * extendedEuclidY(b, a - b * (a / b));
     60}
     61
    3762class Random {
    3863private:
    39         unsigned int seed;
     64        uint64_t x;
     65
     66        static constexpr const uint64_t M  = 1ul << 48ul;
     67        static constexpr const uint64_t A  = 25214903917;
     68        static constexpr const uint64_t C  = 11;
     69        static constexpr const uint64_t D  = 16;
     70
     71public:
     72        static constexpr const uint64_t m  = M;
     73        static constexpr const uint64_t a  = A;
     74        static constexpr const uint64_t c  = C;
     75        static constexpr const uint64_t d  = D;
     76        static constexpr const uint64_t ai = extendedEuclidX(A, M);
    4077public:
    4178        Random(int seed) {
    42                 this->seed = seed;
     79                this->x = seed * a;
    4380        }
    4481
    4582        /** returns pseudorandom x satisfying 0 <= x < n. **/
    4683        unsigned int next() {
    47                 seed ^= seed << 6;
    48                 seed ^= seed >> 21;
    49                 seed ^= seed << 7;
    50                 return seed;
    51         }
     84                //nextx = (a * x + c) % m;
     85                x = (A * x + C) & (M - 1);
     86                return x >> D;
     87        }
     88        unsigned int prev() {
     89                //prevx = (ainverse * (x - c)) mod m
     90                unsigned int r = x >> D;
     91                x = ai * (x - C) & (M - 1);
     92                return r;
     93        }
     94
     95        void set_raw_state(uint64_t _x) {
     96                this->x = _x;
     97        }
     98
     99        uint64_t get_raw_state() {
     100                return this->x;
     101        }
    52102};
    53103
Note: See TracChangeset for help on using the changeset viewer.