lemon/random.h
changeset 2386 81b47fc5c444
parent 2380 7b0558c52de3
child 2387 317b9a88c350
equal deleted inserted replaced
10:464f24c76fd7 11:48e75795eb44
   119       static const int bits = 64;
   119       static const int bits = 64;
   120 
   120 
   121       static const int length = 312;
   121       static const int length = 312;
   122       static const int shift = 156;
   122       static const int shift = 156;
   123 
   123 
   124       static const Word mul = (Word)0x5851F42Du << 32 | (Word)0x4C957F2Du;
   124       static const Word mul = Word(0x5851F42Du) << 32 | Word(0x4C957F2Du);
   125       static const Word arrayInit = (Word)0x00000000u << 32 |(Word)0x012BD6AAu;
   125       static const Word arrayInit = Word(0x00000000u) << 32 |Word(0x012BD6AAu);
   126       static const Word arrayMul1 = (Word)0x369DEA0Fu << 32 |(Word)0x31A53F85u;
   126       static const Word arrayMul1 = Word(0x369DEA0Fu) << 32 |Word(0x31A53F85u);
   127       static const Word arrayMul2 = (Word)0x27BB2EE6u << 32 |(Word)0x87B0B0FDu;
   127       static const Word arrayMul2 = Word(0x27BB2EE6u) << 32 |Word(0x87B0B0FDu);
   128 
   128 
   129       static const Word mask = (Word)0xB5026F5Au << 32 | (Word)0xA96619E9u;
   129       static const Word mask = Word(0xB5026F5Au) << 32 | Word(0xA96619E9u);
   130       static const Word loMask = ((Word)1u << 31) - 1;
   130       static const Word loMask = (Word(1u) << 31) - 1;
   131       static const Word hiMask = ~loMask;
   131       static const Word hiMask = ~loMask;
   132 
   132 
   133       static Word tempering(Word rnd) {
   133       static Word tempering(Word rnd) {
   134         rnd ^= (rnd >> 29) & ((Word)0x55555555u << 32 | (Word)0x55555555u);
   134         rnd ^= (rnd >> 29) & (Word(0x55555555u) << 32 | Word(0x55555555u));
   135         rnd ^= (rnd << 17) & ((Word)0x71D67FFFu << 32 | (Word)0xEDA60000u);
   135         rnd ^= (rnd << 17) & (Word(0x71D67FFFu) << 32 | Word(0xEDA60000u));
   136         rnd ^= (rnd << 37) & ((Word)0xFFF7EEE0u << 32 | (Word)0x00000000u);
   136         rnd ^= (rnd << 37) & (Word(0xFFF7EEE0u) << 32 | Word(0x00000000u));
   137         rnd ^= (rnd >> 43);
   137         rnd ^= (rnd >> 43);
   138         return rnd;
   138         return rnd;
   139       }
   139       }
   140 
   140 
   141     };
   141     };
   214             curr = state + length - 1; curr[0] = state[0]; --curr;
   214             curr = state + length - 1; curr[0] = state[0]; --curr;
   215             cnt = 1;
   215             cnt = 1;
   216           }
   216           }
   217         }
   217         }
   218         
   218         
   219         state[length - 1] = (Word)1 << (bits - 1);
   219         state[length - 1] = Word(1) << (bits - 1);
   220       }
   220       }
   221       
   221       
   222       void copyState(const RandomCore& other) {
   222       void copyState(const RandomCore& other) {
   223         std::copy(other.state, other.state + length, state);
   223         std::copy(other.state, other.state + length, state);
   224         current = state + (other.current - other.state);
   224         current = state + (other.current - other.state);
   271     template <typename Result, 
   271     template <typename Result, 
   272               int shift = (std::numeric_limits<Result>::digits + 1) / 2>
   272               int shift = (std::numeric_limits<Result>::digits + 1) / 2>
   273     struct Masker {
   273     struct Masker {
   274       static Result mask(const Result& result) {
   274       static Result mask(const Result& result) {
   275         return Masker<Result, (shift + 1) / 2>::
   275         return Masker<Result, (shift + 1) / 2>::
   276           mask((Result)(result | (result >> shift)));
   276           mask(static_cast<Result>(result | (result >> shift)));
   277       }
   277       }
   278     };
   278     };
   279     
   279     
   280     template <typename Result>
   280     template <typename Result>
   281     struct Masker<Result, 1> {
   281     struct Masker<Result, 1> {
   282       static Result mask(const Result& result) {
   282       static Result mask(const Result& result) {
   283         return (Result)(result | (result >> 1));
   283         return static_cast<Result>(result | (result >> 1));
   284       }
   284       }
   285     };
   285     };
   286 
   286 
   287     template <typename Result, typename Word, 
   287     template <typename Result, typename Word, 
   288               int rest = std::numeric_limits<Result>::digits, int shift = 0, 
   288               int rest = std::numeric_limits<Result>::digits, int shift = 0, 
   289               bool last = rest <= std::numeric_limits<Word>::digits>
   289               bool last = rest <= std::numeric_limits<Word>::digits>
   290     struct IntConversion {
   290     struct IntConversion {
   291       static const int bits = std::numeric_limits<Word>::digits;
   291       static const int bits = std::numeric_limits<Word>::digits;
   292     
   292     
   293       static Result convert(RandomCore<Word>& rnd) {
   293       static Result convert(RandomCore<Word>& rnd) {
   294         return (Result)(rnd() >> (bits - rest)) << shift;
   294         return static_cast<Result>(rnd() >> (bits - rest)) << shift;
   295       }
   295       }
   296       
   296       
   297     }; 
   297     }; 
   298 
   298 
   299     template <typename Result, typename Word, int rest, int shift> 
   299     template <typename Result, typename Word, int rest, int shift> 
   300     struct IntConversion<Result, Word, rest, shift, false> {
   300     struct IntConversion<Result, Word, rest, shift, false> {
   301       static const int bits = std::numeric_limits<Word>::digits;
   301       static const int bits = std::numeric_limits<Word>::digits;
   302 
   302 
   303       static Result convert(RandomCore<Word>& rnd) {
   303       static Result convert(RandomCore<Word>& rnd) {
   304         return ((Result)rnd() << shift) | 
   304         return (static_cast<Result>(rnd()) << shift) | 
   305           IntConversion<Result, Word, rest - bits, shift + bits>::convert(rnd);
   305           IntConversion<Result, Word, rest - bits, shift + bits>::convert(rnd);
   306       }
   306       }
   307     };
   307     };
   308 
   308 
   309 
   309 
   310     template <typename Result, typename Word,
   310     template <typename Result, typename Word,
   311               bool one_word = std::numeric_limits<Word>::digits < 
   311               bool one_word = std::numeric_limits<Word>::digits < 
   312                               std::numeric_limits<Result>::digits>
   312                               std::numeric_limits<Result>::digits>
   313     struct Mapping {
   313     struct Mapping {
   314       static Result map(RandomCore<Word>& rnd, const Result& bound) {
   314       static Result map(RandomCore<Word>& rnd, const Result& bound) {
   315         Word max = (Word)(bound - 1);
   315         Word max = Word(bound - 1);
   316         Result mask = Masker<Result>::mask(bound - 1);
   316         Result mask = Masker<Result>::mask(bound - 1);
   317         Result num;
   317         Result num;
   318         do {
   318         do {
   319           num = IntConversion<Result, Word>::convert(rnd) & mask; 
   319           num = IntConversion<Result, Word>::convert(rnd) & mask; 
   320         } while (num > max);
   320         } while (num > max);
   323     };
   323     };
   324 
   324 
   325     template <typename Result, typename Word>
   325     template <typename Result, typename Word>
   326     struct Mapping<Result, Word, false> {
   326     struct Mapping<Result, Word, false> {
   327       static Result map(RandomCore<Word>& rnd, const Result& bound) {
   327       static Result map(RandomCore<Word>& rnd, const Result& bound) {
   328         Word max = (Word)(bound - 1);
   328         Word max = Word(bound - 1);
   329         Word mask = Masker<Word, (std::numeric_limits<Result>::digits + 1) / 2>
   329         Word mask = Masker<Word, (std::numeric_limits<Result>::digits + 1) / 2>
   330           ::mask(max);
   330           ::mask(max);
   331         Word num;
   331         Word num;
   332         do {
   332         do {
   333           num = rnd() & mask;
   333           num = rnd() & mask;
   339     template <typename Result, int exp, bool pos = (exp >= 0)>
   339     template <typename Result, int exp, bool pos = (exp >= 0)>
   340     struct ShiftMultiplier {
   340     struct ShiftMultiplier {
   341       static const Result multiplier() {
   341       static const Result multiplier() {
   342         Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
   342         Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
   343         res *= res;
   343         res *= res;
   344         if ((exp & 1) == 1) res *= (Result)2.0;
   344         if ((exp & 1) == 1) res *= static_cast<Result>(2.0);
   345         return res; 
   345         return res; 
   346       }
   346       }
   347     };
   347     };
   348 
   348 
   349     template <typename Result, int exp>
   349     template <typename Result, int exp>
   350     struct ShiftMultiplier<Result, exp, false> {
   350     struct ShiftMultiplier<Result, exp, false> {
   351       static const Result multiplier() {
   351       static const Result multiplier() {
   352         Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
   352         Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
   353         res *= res;
   353         res *= res;
   354         if ((exp & 1) == 1) res *= (Result)0.5;
   354         if ((exp & 1) == 1) res *= static_cast<Result>(0.5);
   355         return res; 
   355         return res; 
   356       }
   356       }
   357     };
   357     };
   358 
   358 
   359     template <typename Result>
   359     template <typename Result>
   360     struct ShiftMultiplier<Result, 0, true> {
   360     struct ShiftMultiplier<Result, 0, true> {
   361       static const Result multiplier() {
   361       static const Result multiplier() {
   362         return (Result)1.0; 
   362         return static_cast<Result>(1.0); 
   363       }
   363       }
   364     };
   364     };
   365 
   365 
   366     template <typename Result>
   366     template <typename Result>
   367     struct ShiftMultiplier<Result, -20, true> {
   367     struct ShiftMultiplier<Result, -20, true> {
   368       static const Result multiplier() {
   368       static const Result multiplier() {
   369         return (Result)(1.0/1048576.0); 
   369         return static_cast<Result>(1.0/1048576.0); 
   370       }
   370       }
   371     };
   371     };
   372     
   372     
   373     template <typename Result>
   373     template <typename Result>
   374     struct ShiftMultiplier<Result, -32, true> {
   374     struct ShiftMultiplier<Result, -32, true> {
   375       static const Result multiplier() {
   375       static const Result multiplier() {
   376         return (Result)(1.0/424967296.0); 
   376         return static_cast<Result>(1.0/424967296.0); 
   377       }
   377       }
   378     };
   378     };
   379 
   379 
   380     template <typename Result>
   380     template <typename Result>
   381     struct ShiftMultiplier<Result, -53, true> {
   381     struct ShiftMultiplier<Result, -53, true> {
   382       static const Result multiplier() {
   382       static const Result multiplier() {
   383         return (Result)(1.0/9007199254740992.0); 
   383         return static_cast<Result>(1.0/9007199254740992.0); 
   384       }
   384       }
   385     };
   385     };
   386 
   386 
   387     template <typename Result>
   387     template <typename Result>
   388     struct ShiftMultiplier<Result, -64, true> {
   388     struct ShiftMultiplier<Result, -64, true> {
   389       static const Result multiplier() {
   389       static const Result multiplier() {
   390         return (Result)(1.0/18446744073709551616.0); 
   390         return static_cast<Result>(1.0/18446744073709551616.0); 
   391       }
   391       }
   392     };
   392     };
   393 
   393 
   394     template <typename Result, int exp>
   394     template <typename Result, int exp>
   395     struct Shifting {
   395     struct Shifting {
   404     struct RealConversion{ 
   404     struct RealConversion{ 
   405       static const int bits = std::numeric_limits<Word>::digits;
   405       static const int bits = std::numeric_limits<Word>::digits;
   406 
   406 
   407       static Result convert(RandomCore<Word>& rnd) {
   407       static Result convert(RandomCore<Word>& rnd) {
   408         return Shifting<Result, - shift - rest>::
   408         return Shifting<Result, - shift - rest>::
   409           shift((Result)(rnd() >> (bits - rest)));
   409           shift(static_cast<Result>(rnd() >> (bits - rest)));
   410       }
   410       }
   411     };
   411     };
   412 
   412 
   413     template <typename Result, typename Word, int rest, int shift>
   413     template <typename Result, typename Word, int rest, int shift>
   414     struct RealConversion<Result, Word, rest, shift, false> { 
   414     struct RealConversion<Result, Word, rest, shift, false> { 
   415       static const int bits = std::numeric_limits<Word>::digits;
   415       static const int bits = std::numeric_limits<Word>::digits;
   416 
   416 
   417       static Result convert(RandomCore<Word>& rnd) {
   417       static Result convert(RandomCore<Word>& rnd) {
   418         return Shifting<Result, - shift - bits>::shift((Result)rnd()) +
   418         return Shifting<Result, - shift - bits>::
   419           RealConversion<Result, Word, rest-bits, shift + bits>::convert(rnd);
   419           shift(static_cast<Result>(rnd())) +
       
   420           RealConversion<Result, Word, rest-bits, shift + bits>::
       
   421           convert(rnd);
   420       }
   422       }
   421     };
   423     };
   422 
   424 
   423     template <typename Result, typename Word>
   425     template <typename Result, typename Word>
   424     struct Initializer {
   426     struct Initializer {
   425 
   427 
   426       template <typename Iterator>
   428       template <typename Iterator>
   427       static void init(RandomCore<Word>& rnd, Iterator begin, Iterator end) {
   429       static void init(RandomCore<Word>& rnd, Iterator begin, Iterator end) {
   428         std::vector<Word> ws;
   430         std::vector<Word> ws;
   429         for (Iterator it = begin; it != end; ++it) {
   431         for (Iterator it = begin; it != end; ++it) {
   430           ws.push_back((Word)*it);
   432           ws.push_back(Word(*it));
   431         }
   433         }
   432         rnd.initState(ws.begin(), ws.end());
   434         rnd.initState(ws.begin(), ws.end());
   433       }
   435       }
   434 
   436 
   435       static void init(RandomCore<Word>& rnd, Result seed) {
   437       static void init(RandomCore<Word>& rnd, Result seed) {