1 /* boost random/linear_congruential.hpp header file

     2  *

     3  * Copyright Jens Maurer 2000-2001

     4  * Distributed under the Boost Software License, Version 1.0. (See

     5  * accompanying file LICENSE_1_0.txt or copy at

     6  * http://www.boost.org/LICENSE_1_0.txt)

     7  *

     8  * See http://www.boost.org for most recent version including documentation.

     9  *

    10  * $Id: linear_congruential.hpp,v 1.22 2005/05/21 15:57:00 dgregor Exp $

    11  *

    12  * Revision history

    13  *  2001-02-18  moved to individual header files

    14  */

    15 

    16 #ifndef BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP

    17 #define BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP

    18 

    19 #include <iostream>

    20 #include <cassert>

    21 #include <stdexcept>

    22 #include <boost/config.hpp>

    23 #include <boost/limits.hpp>

    24 #include <boost/static_assert.hpp>

    25 #include <boost/random/detail/const_mod.hpp>

    26 #include <boost/detail/workaround.hpp>

    27 

    28 namespace boost {

    29 namespace random {

    30 

    31 // compile-time configurable linear congruential generator

    32 template<class IntType, IntType a, IntType c, IntType m, IntType val>

    33 class linear_congruential

    34 {

    35 public:

    36   typedef IntType result_type;

    37 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION

    38   static const bool has_fixed_range = true;

    39   static const result_type min_value = ( c == 0 ? 1 : 0 );

    40   static const result_type max_value = m-1;

    41 #else

    42   BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);

    43 #endif

    44   BOOST_STATIC_CONSTANT(IntType, multiplier = a);

    45   BOOST_STATIC_CONSTANT(IntType, increment = c);

    46   BOOST_STATIC_CONSTANT(IntType, modulus = m);

    47 

    48   // MSVC 6 and possibly others crash when encountering complicated integral

    49   // constant expressions.  Avoid the check for now.

    50   // BOOST_STATIC_ASSERT(m == 0 || a < m);

    51   // BOOST_STATIC_ASSERT(m == 0 || c < m);

    52 

    53   explicit linear_congruential(IntType x0 = 1)

    54     : _modulus(modulus), _x(_modulus ? (x0 % _modulus) : x0)

    55   { 

    56     assert(c || x0); /* if c == 0 and x(0) == 0 then x(n) = 0 for all n */

    57     // overflow check

    58     // disabled because it gives spurious "divide by zero" gcc warnings

    59     // assert(m == 0 || (a*(m-1)+c) % m == (c < a ? c-a+m : c-a)); 

    60 

    61     // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope

    62 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS

    63     BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer);

    64 #endif

    65   }

    66 

    67   template<class It>

    68   linear_congruential(It& first, It last) { seed(first, last); }

    69 

    70   // compiler-generated copy constructor and assignment operator are fine

    71   void seed(IntType x0 = 1)

    72   {

    73     assert(c || x0);

    74     _x = (_modulus ? (x0 % _modulus) : x0);

    75   }

    76 

    77   template<class It>

    78   void seed(It& first, It last)

    79   {

    80     if(first == last)

    81       throw std::invalid_argument("linear_congruential::seed");

    82     IntType value = *first++;

    83     _x = (_modulus ? (value % _modulus) : value);

    84   }

    85 

    86   result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return c == 0 ? 1 : 0; }

    87   result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return modulus-1; }

    88 

    89   IntType operator()()

    90   {

    91     _x = const_mod<IntType, m>::mult_add(a, _x, c);

    92     return _x;

    93   }

    94 

    95   static bool validation(IntType x) { return val == x; }

    96 

    97 #ifdef BOOST_NO_OPERATORS_IN_NAMESPACE

    98     

    99   // Use a member function; Streamable concept not supported.

   100   bool operator==(const linear_congruential& rhs) const

   101   { return _x == rhs._x; }

   102   bool operator!=(const linear_congruential& rhs) const

   103   { return !(*this == rhs); }

   104 

   105 #else 

   106   friend bool operator==(const linear_congruential& x,

   107                          const linear_congruential& y)

   108   { return x._x == y._x; }

   109   friend bool operator!=(const linear_congruential& x,

   110                          const linear_congruential& y)

   111   { return !(x == y); }

   112     

   113 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551))

   114   template<class CharT, class Traits>

   115   friend std::basic_ostream<CharT,Traits>&

   116   operator<<(std::basic_ostream<CharT,Traits>& os,

   117              const linear_congruential& lcg)

   118   {

   119     return os << lcg._x;

   120   }

   121 

   122   template<class CharT, class Traits>

   123   friend std::basic_istream<CharT,Traits>&

   124   operator>>(std::basic_istream<CharT,Traits>& is,

   125              linear_congruential& lcg)

   126   {

   127     return is >> lcg._x;

   128   }

   129  

   130 private:

   131 #endif

   132 #endif

   133     

   134   IntType _modulus;   // work-around for gcc "divide by zero" warning in ctor

   135   IntType _x;

   136 };

   137 

   138 // probably needs the "no native streams" caveat for STLPort

   139 #if !defined(__SGI_STL_PORT) && BOOST_WORKAROUND(__GNUC__, == 2)

   140 template<class IntType, IntType a, IntType c, IntType m, IntType val>

   141 std::ostream&

   142 operator<<(std::ostream& os,

   143            const linear_congruential<IntType,a,c,m,val>& lcg)

   144 {

   145     return os << lcg._x;

   146 }

   147 

   148 template<class IntType, IntType a, IntType c, IntType m, IntType val>

   149 std::istream&

   150 operator>>(std::istream& is,

   151            linear_congruential<IntType,a,c,m,val>& lcg)

   152 {

   153     return is >> lcg._x;

   154 }

   155 #elif defined(BOOST_NO_OPERATORS_IN_NAMESPACE) || defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551))

   156 template<class CharT, class Traits, class IntType, IntType a, IntType c, IntType m, IntType val>

   157 std::basic_ostream<CharT,Traits>&

   158 operator<<(std::basic_ostream<CharT,Traits>& os,

   159            const linear_congruential<IntType,a,c,m,val>& lcg)

   160 {

   161     return os << lcg._x;

   162 }

   163 

   164 template<class CharT, class Traits, class IntType, IntType a, IntType c, IntType m, IntType val>

   165 std::basic_istream<CharT,Traits>&

   166 operator>>(std::basic_istream<CharT,Traits>& is,

   167            linear_congruential<IntType,a,c,m,val>& lcg)

   168 {

   169     return is >> lcg._x;

   170 }

   171 #endif

   172 

   173 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION

   174 //  A definition is required even for integral static constants

   175 template<class IntType, IntType a, IntType c, IntType m, IntType val>

   176 const bool linear_congruential<IntType, a, c, m, val>::has_fixed_range;

   177 template<class IntType, IntType a, IntType c, IntType m, IntType val>

   178 const typename linear_congruential<IntType, a, c, m, val>::result_type linear_congruential<IntType, a, c, m, val>::min_value;

   179 template<class IntType, IntType a, IntType c, IntType m, IntType val>

   180 const typename linear_congruential<IntType, a, c, m, val>::result_type linear_congruential<IntType, a, c, m, val>::max_value;

   181 template<class IntType, IntType a, IntType c, IntType m, IntType val>

   182 const IntType linear_congruential<IntType,a,c,m,val>::modulus;

   183 #endif

   184 

   185 } // namespace random

   186 

   187 // validation values from the publications

   188 typedef random::linear_congruential<int32_t, 16807, 0, 2147483647, 

   189   1043618065> minstd_rand0;

   190 typedef random::linear_congruential<int32_t, 48271, 0, 2147483647,

   191   399268537> minstd_rand;

   192 

   193 

   194 #if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T)

   195 // emulate the lrand48() C library function; requires support for uint64_t

   196 class rand48 

   197 {

   198 public:

   199   typedef int32_t result_type;

   200 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION

   201   static const bool has_fixed_range = true;

   202   static const int32_t min_value = 0;

   203   static const int32_t max_value = integer_traits<int32_t>::const_max;

   204 #else

   205   enum { has_fixed_range = false };

   206 #endif

   207   int32_t min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; }

   208   int32_t max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::numeric_limits<int32_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); }

   209   

   210   explicit rand48(int32_t x0 = 1) : lcf(cnv(x0)) { }

   211   explicit rand48(uint64_t x0) : lcf(x0) { }

   212   template<class It> rand48(It& first, It last) : lcf(first, last) { }

   213   // compiler-generated copy ctor and assignment operator are fine

   214   void seed(int32_t x0 = 1) { lcf.seed(cnv(x0)); }

   215   void seed(uint64_t x0) { lcf.seed(x0); }

   216   template<class It> void seed(It& first, It last) { lcf.seed(first,last); }

   217 

   218   int32_t operator()() { return static_cast<int32_t>(lcf() >> 17); }

   219   // by experiment from lrand48()

   220   static bool validation(int32_t x) { return x == 1993516219; }

   221 

   222 #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE

   223 

   224 #ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS

   225   template<class CharT,class Traits>

   226   friend std::basic_ostream<CharT,Traits>&

   227   operator<<(std::basic_ostream<CharT,Traits>& os, const rand48& r)

   228   { os << r.lcf; return os; }

   229 

   230   template<class CharT,class Traits>

   231   friend std::basic_istream<CharT,Traits>&

   232   operator>>(std::basic_istream<CharT,Traits>& is, rand48& r)

   233   { is >> r.lcf; return is; }

   234 #endif

   235 

   236   friend bool operator==(const rand48& x, const rand48& y)

   237   { return x.lcf == y.lcf; }

   238   friend bool operator!=(const rand48& x, const rand48& y)

   239   { return !(x == y); }

   240 #else

   241   // Use a member function; Streamable concept not supported.

   242   bool operator==(const rand48& rhs) const

   243   { return lcf == rhs.lcf; }

   244   bool operator!=(const rand48& rhs) const

   245   { return !(*this == rhs); }

   246 #endif

   247 private:

   248   random::linear_congruential<uint64_t,

   249     uint64_t(0xDEECE66DUL) | (uint64_t(0x5) << 32), // xxxxULL is not portable

   250     0xB, uint64_t(1)<<48, /* unknown */ 0> lcf;

   251   static uint64_t cnv(int32_t x) 

   252   { return (static_cast<uint64_t>(x) << 16) | 0x330e;  }

   253 };

   254 #endif /* !BOOST_NO_INT64_T && !BOOST_NO_INTEGRAL_INT64_T */

   255 

   256 } // namespace boost

   257 

   258 #endif // BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP