lemon/random.h
changeset 495 0f40b9d26049
parent 482 879c55700cd4
child 517 2b6d5d22bb23
equal deleted inserted replaced
22:4395e2388ccf 23:74ca063b1b7f
   342         } while (num > max);
   342         } while (num > max);
   343         return num;
   343         return num;
   344       }
   344       }
   345     };
   345     };
   346 
   346 
   347     template <typename Result, int exp, bool pos = (exp >= 0)>
   347     template <typename Result, int exp>
   348     struct ShiftMultiplier {
   348     struct ShiftMultiplier {
   349       static const Result multiplier() {
       
   350         Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
       
   351         res *= res;
       
   352         if ((exp & 1) == 1) res *= static_cast<Result>(2.0);
       
   353         return res;
       
   354       }
       
   355     };
       
   356 
       
   357     template <typename Result, int exp>
       
   358     struct ShiftMultiplier<Result, exp, false> {
       
   359       static const Result multiplier() {
   349       static const Result multiplier() {
   360         Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
   350         Result res = ShiftMultiplier<Result, exp / 2>::multiplier();
   361         res *= res;
   351         res *= res;
   362         if ((exp & 1) == 1) res *= static_cast<Result>(0.5);
   352         if ((exp & 1) == 1) res *= static_cast<Result>(0.5);
   363         return res;
   353         return res;
   364       }
   354       }
   365     };
   355     };
   366 
   356 
   367     template <typename Result>
   357     template <typename Result>
   368     struct ShiftMultiplier<Result, 0, true> {
   358     struct ShiftMultiplier<Result, 0> {
   369       static const Result multiplier() {
   359       static const Result multiplier() {
   370         return static_cast<Result>(1.0);
   360         return static_cast<Result>(1.0);
   371       }
   361       }
   372     };
   362     };
   373 
   363 
   374     template <typename Result>
   364     template <typename Result>
   375     struct ShiftMultiplier<Result, -20, true> {
   365     struct ShiftMultiplier<Result, 20> {
   376       static const Result multiplier() {
   366       static const Result multiplier() {
   377         return static_cast<Result>(1.0/1048576.0);
   367         return static_cast<Result>(1.0/1048576.0);
   378       }
   368       }
   379     };
   369     };
   380 
   370 
   381     template <typename Result>
   371     template <typename Result>
   382     struct ShiftMultiplier<Result, -32, true> {
   372     struct ShiftMultiplier<Result, 32> {
   383       static const Result multiplier() {
   373       static const Result multiplier() {
   384         return static_cast<Result>(1.0/424967296.0);
   374         return static_cast<Result>(1.0/4294967296.0);
   385       }
   375       }
   386     };
   376     };
   387 
   377 
   388     template <typename Result>
   378     template <typename Result>
   389     struct ShiftMultiplier<Result, -53, true> {
   379     struct ShiftMultiplier<Result, 53> {
   390       static const Result multiplier() {
   380       static const Result multiplier() {
   391         return static_cast<Result>(1.0/9007199254740992.0);
   381         return static_cast<Result>(1.0/9007199254740992.0);
   392       }
   382       }
   393     };
   383     };
   394 
   384 
   395     template <typename Result>
   385     template <typename Result>
   396     struct ShiftMultiplier<Result, -64, true> {
   386     struct ShiftMultiplier<Result, 64> {
   397       static const Result multiplier() {
   387       static const Result multiplier() {
   398         return static_cast<Result>(1.0/18446744073709551616.0);
   388         return static_cast<Result>(1.0/18446744073709551616.0);
   399       }
   389       }
   400     };
   390     };
   401 
   391 
   411               bool last = rest <= std::numeric_limits<Word>::digits>
   401               bool last = rest <= std::numeric_limits<Word>::digits>
   412     struct RealConversion{
   402     struct RealConversion{
   413       static const int bits = std::numeric_limits<Word>::digits;
   403       static const int bits = std::numeric_limits<Word>::digits;
   414 
   404 
   415       static Result convert(RandomCore<Word>& rnd) {
   405       static Result convert(RandomCore<Word>& rnd) {
   416         return Shifting<Result, - shift - rest>::
   406         return Shifting<Result, shift + rest>::
   417           shift(static_cast<Result>(rnd() >> (bits - rest)));
   407           shift(static_cast<Result>(rnd() >> (bits - rest)));
   418       }
   408       }
   419     };
   409     };
   420 
   410 
   421     template <typename Result, typename Word, int rest, int shift>
   411     template <typename Result, typename Word, int rest, int shift>
   422     struct RealConversion<Result, Word, rest, shift, false> {
   412     struct RealConversion<Result, Word, rest, shift, false> {
   423       static const int bits = std::numeric_limits<Word>::digits;
   413       static const int bits = std::numeric_limits<Word>::digits;
   424 
   414 
   425       static Result convert(RandomCore<Word>& rnd) {
   415       static Result convert(RandomCore<Word>& rnd) {
   426         return Shifting<Result, - shift - bits>::
   416         return Shifting<Result, shift + bits>::
   427           shift(static_cast<Result>(rnd())) +
   417           shift(static_cast<Result>(rnd())) +
   428           RealConversion<Result, Word, rest-bits, shift + bits>::
   418           RealConversion<Result, Word, rest-bits, shift + bits>::
   429           convert(rnd);
   419           convert(rnd);
   430       }
   420       }
   431     };
   421     };