boost/random/shuffle_output.hpp

   1 /* boost random/shuffle_output.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: shuffle_output.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $
  11  *
  12  * Revision history
  13  *  2001-02-18  moved to individual header files
  14  */
  15
  16 #ifndef BOOST_RANDOM_SHUFFLE_OUTPUT_HPP
  17 #define BOOST_RANDOM_SHUFFLE_OUTPUT_HPP
  18
  19 #include <iostream>
  20 #include <algorithm>     // std::copy
  21 #include <cassert>
  22 #include <boost/config.hpp>
  23 #include <boost/limits.hpp>
  24 #include <boost/static_assert.hpp>
  25 #include <boost/cstdint.hpp>
  26 #include <boost/random/linear_congruential.hpp>
  27
  28 namespace boost {
  29 namespace random {
  30
  31 /**
  32  * Instatiations of class template shuffle_output model a
  33  * \pseudo_random_number_generator. It mixes the output
  34  * of some (usually \linear_congruential) \uniform_random_number_generator
  35  * to get better statistical properties.
  36  * The algorithm is described in
  37  *
  38  *  @blockquote
  39  *  "Improving a poor random number generator", Carter Bays
  40  *  and S.D. Durham, ACM Transactions on Mathematical Software,
  41  *  Vol 2, No. 1, March 1976, pp. 59-64.
  42  *  http://doi.acm.org/10.1145/355666.355670
  43  *  @endblockquote
  44  *
  45  * The output of the base generator is buffered in an array of
  46  * length k. Every output X(n) has a second role: It gives an
  47  * index into the array where X(n+1) will be retrieved. Used
  48  * array elements are replaced with fresh output from the base
  49  * generator.
  50  *
  51  * Template parameters are the base generator and the array
  52  * length k, which should be around 100. The template parameter
  53  * val is the validation value checked by validation.
  54  */
  55 template<class UniformRandomNumberGenerator, int k,
  56 #ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
  57   typename UniformRandomNumberGenerator::result_type
  58 #else
  59   uint32_t
  60 #endif
  61   val = 0>
  62 class shuffle_output
  63 {
  64 public:
  65   typedef UniformRandomNumberGenerator base_type;
  66   typedef typename base_type::result_type result_type;
  67
  68   BOOST_STATIC_CONSTANT(bool, has_fixed_range = false);
  69   BOOST_STATIC_CONSTANT(int, buffer_size = k);
  70
  71   /**
  72    * Constructs a @c shuffle_output generator by invoking the
  73    * default constructor of the base generator.
  74    *
  75    * Complexity: Exactly k+1 invocations of the base generator.
  76    */
  77   shuffle_output() : _rng() { init(); }
  78 #if defined(BOOST_MSVC) && _MSC_VER < 1300
  79   // MSVC does not implicitly generate the copy constructor here
  80   shuffle_output(const shuffle_output & x)
  81     : _rng(x._rng), y(x.y) { std::copy(x.v, x.v+k, v); }
  82 #endif
  83   /**
  84    * Constructs a shuffle_output generator by invoking the one-argument
  85    * constructor of the base generator with the parameter seed.
  86    *
  87    * Complexity: Exactly k+1 invocations of the base generator.
  88    */
  89   template<class T>
  90   explicit shuffle_output(T s) : _rng(s) { init(); }
  91   /**
  92    * Constructs a shuffle_output generator by using a copy
  93    * of the provided generator.
  94    *
  95    * Precondition: The template argument UniformRandomNumberGenerator
  96    * shall denote a CopyConstructible type.
  97    *
  98    * Complexity: Exactly k+1 invocations of the base generator.
  99    */
 100   explicit shuffle_output(const base_type & rng) : _rng(rng) { init(); }
 101   template<class It> shuffle_output(It& first, It last)
 102     : _rng(first, last) { init(); }
 103   void seed() { _rng.seed(); init(); }
 104   /**
 105    * Invokes the one-argument seed method of the base generator
 106    * with the parameter seed and re-initializes the internal buffer array.
 107    *
 108    * Complexity: Exactly k+1 invocations of the base generator.
 109    */
 110   template<class T>
 111   void seed(T s) { _rng.seed(s); init(); }
 112   template<class It> void seed(It& first, It last)
 113   {
 114     _rng.seed(first, last);
 115     init();
 116   }
 117
 118   const base_type& base() const { return _rng; }
 119
 120   result_type operator()() {
 121     // calculating the range every time may seem wasteful.  However, this
 122     // makes the information locally available for the optimizer.
 123     result_type range = (max)()-(min)()+1;
 124     int j = k*(y-(min)())/range;
 125     // assert(0 <= j && j < k);
 126     y = v[j];
 127     v[j] = _rng();
 128     return y;
 129   }
 130
 131   result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (_rng.min)(); }
 132   result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (_rng.max)(); }
 133   static bool validation(result_type x) { return val == x; }
 134
 135 #ifndef BOOST_NO_OPERATORS_IN_NAMESPACE
 136
 137 #ifndef BOOST_RANDOM_NO_STREAM_OPERATORS
 138   template<class CharT, class Traits>
 139   friend std::basic_ostream<CharT,Traits>&
 140   operator<<(std::basic_ostream<CharT,Traits>& os, const shuffle_output& s)
 141   {
 142     os << s._rng << " " << s.y << " ";
 143     for(int i = 0; i < s.buffer_size; ++i)
 144       os << s.v[i] << " ";
 145     return os;
 146   }
 147
 148   template<class CharT, class Traits>
 149   friend std::basic_istream<CharT,Traits>&
 150   operator>>(std::basic_istream<CharT,Traits>& is, shuffle_output& s)
 151   {
 152     is >> s._rng >> std::ws >> s.y >> std::ws;
 153     for(int i = 0; i < s.buffer_size; ++i)
 154       is >> s.v[i] >> std::ws;
 155     return is;
 156   }
 157 #endif
 158
 159   friend bool operator==(const shuffle_output& x, const shuffle_output& y)
 160   { return x._rng == y._rng && x.y == y.y && std::equal(x.v, x.v+k, y.v); }
 161   friend bool operator!=(const shuffle_output& x, const shuffle_output& y)
 162   { return !(x == y); }
 163 #else
 164   // Use a member function; Streamable concept not supported.
 165   bool operator==(const shuffle_output& rhs) const
 166   { return _rng == rhs._rng && y == rhs.y && std::equal(v, v+k, rhs.v); }
 167   bool operator!=(const shuffle_output& rhs) const
 168   { return !(*this == rhs); }
 169 #endif
 170 private:
 171   void init()
 172   {
 173 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
 174     BOOST_STATIC_ASSERT(std::numeric_limits<result_type>::is_integer);
 175 #endif
 176     result_type range = (max)()-(min)();
 177     assert(range > 0);      // otherwise there would be little choice
 178     if(static_cast<unsigned long>(k * range) <
 179        static_cast<unsigned long>(range))  // not a sufficient condition
 180       // likely overflow with bucket number computation
 181       assert(!"overflow will occur");
 182
 183     // we cannot use std::generate, because it uses pass-by-value for _rng
 184     for(result_type * p = v; p != v+k; ++p)
 185       *p = _rng();
 186     y = _rng();
 187   }
 188
 189   base_type _rng;
 190   result_type v[k];
 191   result_type y;
 192 };
 193
 194 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 195 //  A definition is required even for integral static constants
 196 template<class UniformRandomNumberGenerator, int k,
 197 #ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
 198   typename UniformRandomNumberGenerator::result_type
 199 #else
 200   uint32_t
 201 #endif
 202   val>
 203 const bool shuffle_output<UniformRandomNumberGenerator, k, val>::has_fixed_range;
 204
 205 template<class UniformRandomNumberGenerator, int k,
 206 #ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
 207   typename UniformRandomNumberGenerator::result_type
 208 #else
 209   uint32_t
 210 #endif
 211   val>
 212 const int shuffle_output<UniformRandomNumberGenerator, k, val>::buffer_size;
 213 #endif
 214
 215 } // namespace random
 216
 217 // validation by experiment from Harry Erwin's generator.h (private e-mail)
 218 /**
 219  * According to Harry Erwin (private e-mail), the specialization
 220  * @c kreutzer1986 was suggested in:
 221  *
 222  * @blockquote
 223  * "System Simulation: Programming Styles and Languages (International
 224  * Computer Science Series)", Wolfgang Kreutzer, Addison-Wesley, December 1986.
 225  * @endblockquote
 226  */
 227 typedef random::shuffle_output<
 228     random::linear_congruential<uint32_t, 1366, 150889, 714025, 0>,
 229   97, 139726> kreutzer1986;
 230
 231
 232 } // namespace boost
 233
 234 #endif // BOOST_RANDOM_SHUFFLE_OUTPUT_HPP