Home | History | Annotate | Download | only in tr1
      1 // random number generation -*- C++ -*-
      2 
      3 // Copyright (C) 2009, 2010 Free Software Foundation, Inc.
      4 //
      5 // This file is part of the GNU ISO C++ Library.  This library is free
      6 // software; you can redistribute it and/or modify it under the
      7 // terms of the GNU General Public License as published by the
      8 // Free Software Foundation; either version 3, or (at your option)
      9 // any later version.
     10 
     11 // This library is distributed in the hope that it will be useful,
     12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
     13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     14 // GNU General Public License for more details.
     15 
     16 // Under Section 7 of GPL version 3, you are granted additional
     17 // permissions described in the GCC Runtime Library Exception, version
     18 // 3.1, as published by the Free Software Foundation.
     19 
     20 // You should have received a copy of the GNU General Public License and
     21 // a copy of the GCC Runtime Library Exception along with this program;
     22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
     23 // <http://www.gnu.org/licenses/>.
     24 
     25 /**
     26  * @file tr1/random.h
     27  *  This is an internal header file, included by other library headers.
     28  *  Do not attempt to use it directly. @headername{tr1/random}
     29  */
     30 
     31 #ifndef _GLIBCXX_TR1_RANDOM_H
     32 #define _GLIBCXX_TR1_RANDOM_H 1
     33 
     34 #pragma GCC system_header
     35 
     36 namespace std _GLIBCXX_VISIBILITY(default)
     37 {
     38 namespace tr1
     39 {
     40   // [5.1] Random number generation
     41 
     42   /**
     43    * @addtogroup tr1_random Random Number Generation
     44    * A facility for generating random numbers on selected distributions.
     45    * @{
     46    */
     47 
     48   /*
     49    * Implementation-space details.
     50    */
     51   namespace __detail
     52   {
     53   _GLIBCXX_BEGIN_NAMESPACE_VERSION
     54 
     55     template<typename _UIntType, int __w,
     56 	     bool = __w < std::numeric_limits<_UIntType>::digits>
     57       struct _Shift
     58       { static const _UIntType __value = 0; };
     59 
     60     template<typename _UIntType, int __w>
     61       struct _Shift<_UIntType, __w, true>
     62       { static const _UIntType __value = _UIntType(1) << __w; };
     63 
     64     template<typename _Tp, _Tp __a, _Tp __c, _Tp __m, bool>
     65       struct _Mod;
     66 
     67     // Dispatch based on modulus value to prevent divide-by-zero compile-time
     68     // errors when m == 0.
     69     template<typename _Tp, _Tp __a, _Tp __c, _Tp __m>
     70       inline _Tp
     71       __mod(_Tp __x)
     72       { return _Mod<_Tp, __a, __c, __m, __m == 0>::__calc(__x); }
     73 
     74     typedef __gnu_cxx::__conditional_type<(sizeof(unsigned) == 4),
     75 		    unsigned, unsigned long>::__type _UInt32Type;
     76 
     77     /*
     78      * An adaptor class for converting the output of any Generator into
     79      * the input for a specific Distribution.
     80      */
     81     template<typename _Engine, typename _Distribution>
     82       struct _Adaptor
     83       {
     84 	typedef typename remove_reference<_Engine>::type _BEngine;
     85 	typedef typename _BEngine::result_type           _Engine_result_type;
     86 	typedef typename _Distribution::input_type       result_type;
     87 
     88       public:
     89 	_Adaptor(const _Engine& __g)
     90 	: _M_g(__g) { }
     91 
     92 	result_type
     93 	min() const
     94 	{
     95 	  result_type __return_value;
     96 	  if (is_integral<_Engine_result_type>::value
     97 	      && is_integral<result_type>::value)
     98 	    __return_value = _M_g.min();
     99 	  else
    100 	    __return_value = result_type(0);
    101 	  return __return_value;
    102 	}
    103 
    104 	result_type
    105 	max() const
    106 	{
    107 	  result_type __return_value;
    108 	  if (is_integral<_Engine_result_type>::value
    109 	      && is_integral<result_type>::value)
    110 	    __return_value = _M_g.max();
    111 	  else if (!is_integral<result_type>::value)
    112 	    __return_value = result_type(1);
    113 	  else
    114 	    __return_value = std::numeric_limits<result_type>::max() - 1;
    115 	  return __return_value;
    116 	}
    117 
    118 	/*
    119 	 * Converts a value generated by the adapted random number generator
    120 	 * into a value in the input domain for the dependent random number
    121 	 * distribution.
    122 	 *
    123 	 * Because the type traits are compile time constants only the
    124 	 * appropriate clause of the if statements will actually be emitted
    125 	 * by the compiler.
    126 	 */
    127 	result_type
    128 	operator()()
    129 	{
    130 	  result_type __return_value;
    131 	  if (is_integral<_Engine_result_type>::value
    132 	      && is_integral<result_type>::value)
    133 	    __return_value = _M_g();
    134 	  else if (!is_integral<_Engine_result_type>::value
    135 		   && !is_integral<result_type>::value)
    136 	    __return_value = result_type(_M_g() - _M_g.min())
    137 	      / result_type(_M_g.max() - _M_g.min());
    138 	  else if (is_integral<_Engine_result_type>::value
    139 		   && !is_integral<result_type>::value)
    140 	    __return_value = result_type(_M_g() - _M_g.min())
    141 	      / result_type(_M_g.max() - _M_g.min() + result_type(1));
    142 	  else
    143 	    __return_value = (((_M_g() - _M_g.min())
    144 			       / (_M_g.max() - _M_g.min()))
    145 			      * std::numeric_limits<result_type>::max());
    146 	  return __return_value;
    147 	}
    148 
    149       private:
    150 	_Engine _M_g;
    151       };
    152 
    153     // Specialization for _Engine*.
    154     template<typename _Engine, typename _Distribution>
    155       struct _Adaptor<_Engine*, _Distribution>
    156       {
    157 	typedef typename _Engine::result_type      _Engine_result_type;
    158 	typedef typename _Distribution::input_type result_type;
    159 
    160       public:
    161 	_Adaptor(_Engine* __g)
    162 	: _M_g(__g) { }
    163 
    164 	result_type
    165 	min() const
    166 	{
    167 	  result_type __return_value;
    168 	  if (is_integral<_Engine_result_type>::value
    169 	      && is_integral<result_type>::value)
    170 	    __return_value = _M_g->min();
    171 	  else
    172 	    __return_value = result_type(0);
    173 	  return __return_value;
    174 	}
    175 
    176 	result_type
    177 	max() const
    178 	{
    179 	  result_type __return_value;
    180 	  if (is_integral<_Engine_result_type>::value
    181 	      && is_integral<result_type>::value)
    182 	    __return_value = _M_g->max();
    183 	  else if (!is_integral<result_type>::value)
    184 	    __return_value = result_type(1);
    185 	  else
    186 	    __return_value = std::numeric_limits<result_type>::max() - 1;
    187 	  return __return_value;
    188 	}
    189 
    190 	result_type
    191 	operator()()
    192 	{
    193 	  result_type __return_value;
    194 	  if (is_integral<_Engine_result_type>::value
    195 	      && is_integral<result_type>::value)
    196 	    __return_value = (*_M_g)();
    197 	  else if (!is_integral<_Engine_result_type>::value
    198 		   && !is_integral<result_type>::value)
    199 	    __return_value = result_type((*_M_g)() - _M_g->min())
    200 	      / result_type(_M_g->max() - _M_g->min());
    201 	  else if (is_integral<_Engine_result_type>::value
    202 		   && !is_integral<result_type>::value)
    203 	    __return_value = result_type((*_M_g)() - _M_g->min())
    204 	      / result_type(_M_g->max() - _M_g->min() + result_type(1));
    205 	  else
    206 	    __return_value = ((((*_M_g)() - _M_g->min())
    207 			       / (_M_g->max() - _M_g->min()))
    208 			      * std::numeric_limits<result_type>::max());
    209 	  return __return_value;
    210 	}
    211 
    212       private:
    213 	_Engine* _M_g;
    214       };
    215 
    216   _GLIBCXX_END_NAMESPACE_VERSION
    217   } // namespace __detail
    218 
    219 _GLIBCXX_BEGIN_NAMESPACE_VERSION
    220 
    221   /**
    222    * Produces random numbers on a given distribution function using a
    223    * non-uniform random number generation engine.
    224    *
    225    * @todo the engine_value_type needs to be studied more carefully.
    226    */
    227   template<typename _Engine, typename _Dist>
    228     class variate_generator
    229     {
    230       // Concept requirements.
    231       __glibcxx_class_requires(_Engine, _CopyConstructibleConcept)
    232       //  __glibcxx_class_requires(_Engine, _EngineConcept)
    233       //  __glibcxx_class_requires(_Dist, _EngineConcept)
    234 
    235     public:
    236       typedef _Engine                                engine_type;
    237       typedef __detail::_Adaptor<_Engine, _Dist>     engine_value_type;
    238       typedef _Dist                                  distribution_type;
    239       typedef typename _Dist::result_type            result_type;
    240 
    241       // tr1:5.1.1 table 5.1 requirement
    242       typedef typename __gnu_cxx::__enable_if<
    243 	is_arithmetic<result_type>::value, result_type>::__type _IsValidType;
    244 
    245       /**
    246        * Constructs a variate generator with the uniform random number
    247        * generator @p __eng for the random distribution @p __dist.
    248        *
    249        * @throws Any exceptions which may thrown by the copy constructors of
    250        * the @p _Engine or @p _Dist objects.
    251        */
    252       variate_generator(engine_type __eng, distribution_type __dist)
    253       : _M_engine(__eng), _M_dist(__dist) { }
    254 
    255       /**
    256        * Gets the next generated value on the distribution.
    257        */
    258       result_type
    259       operator()()
    260       { return _M_dist(_M_engine); }
    261 
    262       /**
    263        * WTF?
    264        */
    265       template<typename _Tp>
    266         result_type
    267         operator()(_Tp __value)
    268         { return _M_dist(_M_engine, __value); }
    269 
    270       /**
    271        * Gets a reference to the underlying uniform random number generator
    272        * object.
    273        */
    274       engine_value_type&
    275       engine()
    276       { return _M_engine; }
    277 
    278       /**
    279        * Gets a const reference to the underlying uniform random number
    280        * generator object.
    281        */
    282       const engine_value_type&
    283       engine() const
    284       { return _M_engine; }
    285 
    286       /**
    287        * Gets a reference to the underlying random distribution.
    288        */
    289       distribution_type&
    290       distribution()
    291       { return _M_dist; }
    292 
    293       /**
    294        * Gets a const reference to the underlying random distribution.
    295        */
    296       const distribution_type&
    297       distribution() const
    298       { return _M_dist; }
    299 
    300       /**
    301        * Gets the closed lower bound of the distribution interval.
    302        */
    303       result_type
    304       min() const
    305       { return this->distribution().min(); }
    306 
    307       /**
    308        * Gets the closed upper bound of the distribution interval.
    309        */
    310       result_type
    311       max() const
    312       { return this->distribution().max(); }
    313 
    314     private:
    315       engine_value_type _M_engine;
    316       distribution_type _M_dist;
    317     };
    318 
    319 
    320   /**
    321    * @addtogroup tr1_random_generators Random Number Generators
    322    * @ingroup tr1_random
    323    *
    324    * These classes define objects which provide random or pseudorandom
    325    * numbers, either from a discrete or a continuous interval.  The
    326    * random number generator supplied as a part of this library are
    327    * all uniform random number generators which provide a sequence of
    328    * random number uniformly distributed over their range.
    329    *
    330    * A number generator is a function object with an operator() that
    331    * takes zero arguments and returns a number.
    332    *
    333    * A compliant random number generator must satisfy the following
    334    * requirements.  <table border=1 cellpadding=10 cellspacing=0>
    335    * <caption align=top>Random Number Generator Requirements</caption>
    336    * <tr><td>To be documented.</td></tr> </table>
    337    *
    338    * @{
    339    */
    340 
    341   /**
    342    * @brief A model of a linear congruential random number generator.
    343    *
    344    * A random number generator that produces pseudorandom numbers using the
    345    * linear function @f$x_{i+1}\leftarrow(ax_{i} + c) \bmod m @f$.
    346    *
    347    * The template parameter @p _UIntType must be an unsigned integral type
    348    * large enough to store values up to (__m-1). If the template parameter
    349    * @p __m is 0, the modulus @p __m used is
    350    * std::numeric_limits<_UIntType>::max() plus 1. Otherwise, the template
    351    * parameters @p __a and @p __c must be less than @p __m.
    352    *
    353    * The size of the state is @f$ 1 @f$.
    354    */
    355   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
    356     class linear_congruential
    357     {
    358       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
    359       //  __glibcpp_class_requires(__a < __m && __c < __m)
    360 
    361     public:
    362       /** The type of the generated random value. */
    363       typedef _UIntType result_type;
    364 
    365       /** The multiplier. */
    366       static const _UIntType multiplier = __a;
    367       /** An increment. */
    368       static const _UIntType increment = __c;
    369       /** The modulus. */
    370       static const _UIntType modulus = __m;
    371 
    372       /**
    373        * Constructs a %linear_congruential random number generator engine with
    374        * seed @p __s.  The default seed value is 1.
    375        *
    376        * @param __s The initial seed value.
    377        */
    378       explicit
    379       linear_congruential(unsigned long __x0 = 1)
    380       { this->seed(__x0); }
    381 
    382       /**
    383        * Constructs a %linear_congruential random number generator engine
    384        * seeded from the generator function @p __g.
    385        *
    386        * @param __g The seed generator function.
    387        */
    388       template<class _Gen>
    389         linear_congruential(_Gen& __g)
    390         { this->seed(__g); }
    391 
    392       /**
    393        * Reseeds the %linear_congruential random number generator engine
    394        * sequence to the seed @g __s.
    395        *
    396        * @param __s The new seed.
    397        */
    398       void
    399       seed(unsigned long __s = 1);
    400 
    401       /**
    402        * Reseeds the %linear_congruential random number generator engine
    403        * sequence using values from the generator function @p __g.
    404        *
    405        * @param __g the seed generator function.
    406        */
    407       template<class _Gen>
    408         void
    409         seed(_Gen& __g)
    410         { seed(__g, typename is_fundamental<_Gen>::type()); }
    411 
    412       /**
    413        * Gets the smallest possible value in the output range.
    414        *
    415        * The minimum depends on the @p __c parameter: if it is zero, the
    416        * minimum generated must be > 0, otherwise 0 is allowed.
    417        */
    418       result_type
    419       min() const
    420       { return (__detail::__mod<_UIntType, 1, 0, __m>(__c) == 0) ? 1 : 0; }
    421 
    422       /**
    423        * Gets the largest possible value in the output range.
    424        */
    425       result_type
    426       max() const
    427       { return __m - 1; }
    428 
    429       /**
    430        * Gets the next random number in the sequence.
    431        */
    432       result_type
    433       operator()();
    434 
    435       /**
    436        * Compares two linear congruential random number generator
    437        * objects of the same type for equality.
    438        *
    439        * @param __lhs A linear congruential random number generator object.
    440        * @param __rhs Another linear congruential random number generator obj.
    441        *
    442        * @returns true if the two objects are equal, false otherwise.
    443        */
    444       friend bool
    445       operator==(const linear_congruential& __lhs,
    446 		 const linear_congruential& __rhs)
    447       { return __lhs._M_x == __rhs._M_x; }
    448 
    449       /**
    450        * Compares two linear congruential random number generator
    451        * objects of the same type for inequality.
    452        *
    453        * @param __lhs A linear congruential random number generator object.
    454        * @param __rhs Another linear congruential random number generator obj.
    455        *
    456        * @returns true if the two objects are not equal, false otherwise.
    457        */
    458       friend bool
    459       operator!=(const linear_congruential& __lhs,
    460 		 const linear_congruential& __rhs)
    461       { return !(__lhs == __rhs); }
    462 
    463       /**
    464        * Writes the textual representation of the state x(i) of x to @p __os.
    465        *
    466        * @param __os  The output stream.
    467        * @param __lcr A % linear_congruential random number generator.
    468        * @returns __os.
    469        */
    470       template<class _UIntType1, _UIntType1 __a1, _UIntType1 __c1,
    471 	       _UIntType1 __m1,
    472 	       typename _CharT, typename _Traits>
    473         friend std::basic_ostream<_CharT, _Traits>&
    474         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    475 		   const linear_congruential<_UIntType1, __a1, __c1,
    476 		   __m1>& __lcr);
    477 
    478       /**
    479        * Sets the state of the engine by reading its textual
    480        * representation from @p __is.
    481        *
    482        * The textual representation must have been previously written using an
    483        * output stream whose imbued locale and whose type's template
    484        * specialization arguments _CharT and _Traits were the same as those of
    485        * @p __is.
    486        *
    487        * @param __is  The input stream.
    488        * @param __lcr A % linear_congruential random number generator.
    489        * @returns __is.
    490        */
    491       template<class _UIntType1, _UIntType1 __a1, _UIntType1 __c1,
    492 	       _UIntType1 __m1,
    493 	       typename _CharT, typename _Traits>
    494         friend std::basic_istream<_CharT, _Traits>&
    495         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    496 		   linear_congruential<_UIntType1, __a1, __c1, __m1>& __lcr);
    497 
    498     private:
    499       template<class _Gen>
    500         void
    501         seed(_Gen& __g, true_type)
    502         { return seed(static_cast<unsigned long>(__g)); }
    503 
    504       template<class _Gen>
    505         void
    506         seed(_Gen& __g, false_type);
    507 
    508       _UIntType _M_x;
    509     };
    510 
    511   /**
    512    * The classic Minimum Standard rand0 of Lewis, Goodman, and Miller.
    513    */
    514   typedef linear_congruential<unsigned long, 16807, 0, 2147483647> minstd_rand0;
    515 
    516   /**
    517    * An alternative LCR (Lehmer Generator function) .
    518    */
    519   typedef linear_congruential<unsigned long, 48271, 0, 2147483647> minstd_rand;
    520 
    521 
    522   /**
    523    * A generalized feedback shift register discrete random number generator.
    524    *
    525    * This algorithm avoids multiplication and division and is designed to be
    526    * friendly to a pipelined architecture.  If the parameters are chosen
    527    * correctly, this generator will produce numbers with a very long period and
    528    * fairly good apparent entropy, although still not cryptographically strong.
    529    *
    530    * The best way to use this generator is with the predefined mt19937 class.
    531    *
    532    * This algorithm was originally invented by Makoto Matsumoto and
    533    * Takuji Nishimura.
    534    *
    535    * @var word_size   The number of bits in each element of the state vector.
    536    * @var state_size  The degree of recursion.
    537    * @var shift_size  The period parameter.
    538    * @var mask_bits   The separation point bit index.
    539    * @var parameter_a The last row of the twist matrix.
    540    * @var output_u    The first right-shift tempering matrix parameter.
    541    * @var output_s    The first left-shift tempering matrix parameter.
    542    * @var output_b    The first left-shift tempering matrix mask.
    543    * @var output_t    The second left-shift tempering matrix parameter.
    544    * @var output_c    The second left-shift tempering matrix mask.
    545    * @var output_l    The second right-shift tempering matrix parameter.
    546    */
    547   template<class _UIntType, int __w, int __n, int __m, int __r,
    548 	   _UIntType __a, int __u, int __s, _UIntType __b, int __t,
    549 	   _UIntType __c, int __l>
    550     class mersenne_twister
    551     {
    552       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
    553 
    554     public:
    555       // types
    556       typedef _UIntType result_type;
    557 
    558       // parameter values
    559       static const int       word_size   = __w;
    560       static const int       state_size  = __n;
    561       static const int       shift_size  = __m;
    562       static const int       mask_bits   = __r;
    563       static const _UIntType parameter_a = __a;
    564       static const int       output_u    = __u;
    565       static const int       output_s    = __s;
    566       static const _UIntType output_b    = __b;
    567       static const int       output_t    = __t;
    568       static const _UIntType output_c    = __c;
    569       static const int       output_l    = __l;
    570 
    571       // constructors and member function
    572       mersenne_twister()
    573       { seed(); }
    574 
    575       explicit
    576       mersenne_twister(unsigned long __value)
    577       { seed(__value); }
    578 
    579       template<class _Gen>
    580         mersenne_twister(_Gen& __g)
    581         { seed(__g); }
    582 
    583       void
    584       seed()
    585       { seed(5489UL); }
    586 
    587       void
    588       seed(unsigned long __value);
    589 
    590       template<class _Gen>
    591         void
    592         seed(_Gen& __g)
    593         { seed(__g, typename is_fundamental<_Gen>::type()); }
    594 
    595       result_type
    596       min() const
    597       { return 0; };
    598 
    599       result_type
    600       max() const
    601       { return __detail::_Shift<_UIntType, __w>::__value - 1; }
    602 
    603       result_type
    604       operator()();
    605 
    606       /**
    607        * Compares two % mersenne_twister random number generator objects of
    608        * the same type for equality.
    609        *
    610        * @param __lhs A % mersenne_twister random number generator object.
    611        * @param __rhs Another % mersenne_twister random number generator
    612        *              object.
    613        *
    614        * @returns true if the two objects are equal, false otherwise.
    615        */
    616       friend bool
    617       operator==(const mersenne_twister& __lhs,
    618 		 const mersenne_twister& __rhs)
    619       { return std::equal(__lhs._M_x, __lhs._M_x + state_size, __rhs._M_x); }
    620 
    621       /**
    622        * Compares two % mersenne_twister random number generator objects of
    623        * the same type for inequality.
    624        *
    625        * @param __lhs A % mersenne_twister random number generator object.
    626        * @param __rhs Another % mersenne_twister random number generator
    627        *              object.
    628        *
    629        * @returns true if the two objects are not equal, false otherwise.
    630        */
    631       friend bool
    632       operator!=(const mersenne_twister& __lhs,
    633 		 const mersenne_twister& __rhs)
    634       { return !(__lhs == __rhs); }
    635 
    636       /**
    637        * Inserts the current state of a % mersenne_twister random number
    638        * generator engine @p __x into the output stream @p __os.
    639        *
    640        * @param __os An output stream.
    641        * @param __x  A % mersenne_twister random number generator engine.
    642        *
    643        * @returns The output stream with the state of @p __x inserted or in
    644        * an error state.
    645        */
    646       template<class _UIntType1, int __w1, int __n1, int __m1, int __r1,
    647 	       _UIntType1 __a1, int __u1, int __s1, _UIntType1 __b1, int __t1,
    648 	       _UIntType1 __c1, int __l1,
    649 	       typename _CharT, typename _Traits>
    650         friend std::basic_ostream<_CharT, _Traits>&
    651         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    652 		   const mersenne_twister<_UIntType1, __w1, __n1, __m1, __r1,
    653 		   __a1, __u1, __s1, __b1, __t1, __c1, __l1>& __x);
    654 
    655       /**
    656        * Extracts the current state of a % mersenne_twister random number
    657        * generator engine @p __x from the input stream @p __is.
    658        *
    659        * @param __is An input stream.
    660        * @param __x  A % mersenne_twister random number generator engine.
    661        *
    662        * @returns The input stream with the state of @p __x extracted or in
    663        * an error state.
    664        */
    665       template<class _UIntType1, int __w1, int __n1, int __m1, int __r1,
    666 	       _UIntType1 __a1, int __u1, int __s1, _UIntType1 __b1, int __t1,
    667 	       _UIntType1 __c1, int __l1,
    668 	       typename _CharT, typename _Traits>
    669         friend std::basic_istream<_CharT, _Traits>&
    670         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    671 		   mersenne_twister<_UIntType1, __w1, __n1, __m1, __r1,
    672 		   __a1, __u1, __s1, __b1, __t1, __c1, __l1>& __x);
    673 
    674     private:
    675       template<class _Gen>
    676         void
    677         seed(_Gen& __g, true_type)
    678         { return seed(static_cast<unsigned long>(__g)); }
    679 
    680       template<class _Gen>
    681         void
    682         seed(_Gen& __g, false_type);
    683 
    684       _UIntType _M_x[state_size];
    685       int       _M_p;
    686     };
    687 
    688   /**
    689    * The classic Mersenne Twister.
    690    *
    691    * Reference:
    692    * M. Matsumoto and T. Nishimura, Mersenne Twister: A 623-Dimensionally
    693    * Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions
    694    * on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
    695    */
    696   typedef mersenne_twister<
    697     unsigned long, 32, 624, 397, 31,
    698     0x9908b0dful, 11, 7,
    699     0x9d2c5680ul, 15,
    700     0xefc60000ul, 18
    701     > mt19937;
    702 
    703 
    704   /**
    705    * @brief The Marsaglia-Zaman generator.
    706    *
    707    * This is a model of a Generalized Fibonacci discrete random number
    708    * generator, sometimes referred to as the SWC generator.
    709    *
    710    * A discrete random number generator that produces pseudorandom
    711    * numbers using @f$x_{i}\leftarrow(x_{i - s} - x_{i - r} -
    712    * carry_{i-1}) \bmod m @f$.
    713    *
    714    * The size of the state is @f$ r @f$
    715    * and the maximum period of the generator is @f$ m^r - m^s -1 @f$.
    716    *
    717    * N1688[4.13] says <em>the template parameter _IntType shall denote
    718    * an integral type large enough to store values up to m</em>.
    719    *
    720    * @var _M_x     The state of the generator.  This is a ring buffer.
    721    * @var _M_carry The carry.
    722    * @var _M_p     Current index of x(i - r).
    723    */
    724   template<typename _IntType, _IntType __m, int __s, int __r>
    725     class subtract_with_carry
    726     {
    727       __glibcxx_class_requires(_IntType, _IntegerConcept)
    728 
    729     public:
    730       /** The type of the generated random value. */
    731       typedef _IntType result_type;
    732 
    733       // parameter values
    734       static const _IntType modulus   = __m;
    735       static const int      long_lag  = __r;
    736       static const int      short_lag = __s;
    737 
    738       /**
    739        * Constructs a default-initialized % subtract_with_carry random number
    740        * generator.
    741        */
    742       subtract_with_carry()
    743       { this->seed(); }
    744 
    745       /**
    746        * Constructs an explicitly seeded % subtract_with_carry random number
    747        * generator.
    748        */
    749       explicit
    750       subtract_with_carry(unsigned long __value)
    751       { this->seed(__value); }
    752 
    753       /**
    754        * Constructs a %subtract_with_carry random number generator engine
    755        * seeded from the generator function @p __g.
    756        *
    757        * @param __g The seed generator function.
    758        */
    759       template<class _Gen>
    760         subtract_with_carry(_Gen& __g)
    761         { this->seed(__g); }
    762 
    763       /**
    764        * Seeds the initial state @f$ x_0 @f$ of the random number generator.
    765        *
    766        * N1688[4.19] modifies this as follows.  If @p __value == 0,
    767        * sets value to 19780503.  In any case, with a linear
    768        * congruential generator lcg(i) having parameters @f$ m_{lcg} =
    769        * 2147483563, a_{lcg} = 40014, c_{lcg} = 0, and lcg(0) = value
    770        * @f$, sets @f$ x_{-r} \dots x_{-1} @f$ to @f$ lcg(1) \bmod m
    771        * \dots lcg(r) \bmod m @f$ respectively.  If @f$ x_{-1} = 0 @f$
    772        * set carry to 1, otherwise sets carry to 0.
    773        */
    774       void
    775       seed(unsigned long __value = 19780503);
    776 
    777       /**
    778        * Seeds the initial state @f$ x_0 @f$ of the % subtract_with_carry
    779        * random number generator.
    780        */
    781       template<class _Gen>
    782         void
    783         seed(_Gen& __g)
    784         { seed(__g, typename is_fundamental<_Gen>::type()); }
    785 
    786       /**
    787        * Gets the inclusive minimum value of the range of random integers
    788        * returned by this generator.
    789        */
    790       result_type
    791       min() const
    792       { return 0; }
    793 
    794       /**
    795        * Gets the inclusive maximum value of the range of random integers
    796        * returned by this generator.
    797        */
    798       result_type
    799       max() const
    800       { return this->modulus - 1; }
    801 
    802       /**
    803        * Gets the next random number in the sequence.
    804        */
    805       result_type
    806       operator()();
    807 
    808       /**
    809        * Compares two % subtract_with_carry random number generator objects of
    810        * the same type for equality.
    811        *
    812        * @param __lhs A % subtract_with_carry random number generator object.
    813        * @param __rhs Another % subtract_with_carry random number generator
    814        *              object.
    815        *
    816        * @returns true if the two objects are equal, false otherwise.
    817        */
    818       friend bool
    819       operator==(const subtract_with_carry& __lhs,
    820 		 const subtract_with_carry& __rhs)
    821       { return std::equal(__lhs._M_x, __lhs._M_x + long_lag, __rhs._M_x); }
    822 
    823       /**
    824        * Compares two % subtract_with_carry random number generator objects of
    825        * the same type for inequality.
    826        *
    827        * @param __lhs A % subtract_with_carry random number generator object.
    828        * @param __rhs Another % subtract_with_carry random number generator
    829        *              object.
    830        *
    831        * @returns true if the two objects are not equal, false otherwise.
    832        */
    833       friend bool
    834       operator!=(const subtract_with_carry& __lhs,
    835 		 const subtract_with_carry& __rhs)
    836       { return !(__lhs == __rhs); }
    837 
    838       /**
    839        * Inserts the current state of a % subtract_with_carry random number
    840        * generator engine @p __x into the output stream @p __os.
    841        *
    842        * @param __os An output stream.
    843        * @param __x  A % subtract_with_carry random number generator engine.
    844        *
    845        * @returns The output stream with the state of @p __x inserted or in
    846        * an error state.
    847        */
    848       template<typename _IntType1, _IntType1 __m1, int __s1, int __r1,
    849 	       typename _CharT, typename _Traits>
    850         friend std::basic_ostream<_CharT, _Traits>&
    851         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    852 		   const subtract_with_carry<_IntType1, __m1, __s1,
    853 		   __r1>& __x);
    854 
    855       /**
    856        * Extracts the current state of a % subtract_with_carry random number
    857        * generator engine @p __x from the input stream @p __is.
    858        *
    859        * @param __is An input stream.
    860        * @param __x  A % subtract_with_carry random number generator engine.
    861        *
    862        * @returns The input stream with the state of @p __x extracted or in
    863        * an error state.
    864        */
    865       template<typename _IntType1, _IntType1 __m1, int __s1, int __r1,
    866 	       typename _CharT, typename _Traits>
    867         friend std::basic_istream<_CharT, _Traits>&
    868         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    869 		   subtract_with_carry<_IntType1, __m1, __s1, __r1>& __x);
    870 
    871     private:
    872       template<class _Gen>
    873         void
    874         seed(_Gen& __g, true_type)
    875         { return seed(static_cast<unsigned long>(__g)); }
    876 
    877       template<class _Gen>
    878         void
    879         seed(_Gen& __g, false_type);
    880 
    881       typedef typename __gnu_cxx::__add_unsigned<_IntType>::__type _UIntType;
    882 
    883       _UIntType  _M_x[long_lag];
    884       _UIntType  _M_carry;
    885       int        _M_p;
    886     };
    887 
    888 
    889   /**
    890    * @brief The Marsaglia-Zaman generator (floats version).
    891    *
    892    * @var _M_x     The state of the generator.  This is a ring buffer.
    893    * @var _M_carry The carry.
    894    * @var _M_p     Current index of x(i - r).
    895    * @var _M_npows Precomputed negative powers of 2.
    896    */
    897   template<typename _RealType, int __w, int __s, int __r>
    898     class subtract_with_carry_01
    899     {
    900     public:
    901       /** The type of the generated random value. */
    902       typedef _RealType result_type;
    903 
    904       // parameter values
    905       static const int      word_size = __w;
    906       static const int      long_lag  = __r;
    907       static const int      short_lag = __s;
    908 
    909       /**
    910        * Constructs a default-initialized % subtract_with_carry_01 random
    911        * number generator.
    912        */
    913       subtract_with_carry_01()
    914       {
    915 	this->seed();
    916 	_M_initialize_npows();
    917       }
    918 
    919       /**
    920        * Constructs an explicitly seeded % subtract_with_carry_01 random number
    921        * generator.
    922        */
    923       explicit
    924       subtract_with_carry_01(unsigned long __value)
    925       {
    926 	this->seed(__value);
    927 	_M_initialize_npows();
    928       }
    929 
    930       /**
    931        * Constructs a % subtract_with_carry_01 random number generator engine
    932        * seeded from the generator function @p __g.
    933        *
    934        * @param __g The seed generator function.
    935        */
    936       template<class _Gen>
    937         subtract_with_carry_01(_Gen& __g)
    938         {
    939 	  this->seed(__g);
    940 	  _M_initialize_npows();
    941 	}
    942 
    943       /**
    944        * Seeds the initial state @f$ x_0 @f$ of the random number generator.
    945        */
    946       void
    947       seed(unsigned long __value = 19780503);
    948 
    949       /**
    950        * Seeds the initial state @f$ x_0 @f$ of the % subtract_with_carry_01
    951        * random number generator.
    952        */
    953       template<class _Gen>
    954         void
    955         seed(_Gen& __g)
    956         { seed(__g, typename is_fundamental<_Gen>::type()); }
    957 
    958       /**
    959        * Gets the minimum value of the range of random floats
    960        * returned by this generator.
    961        */
    962       result_type
    963       min() const
    964       { return 0.0; }
    965 
    966       /**
    967        * Gets the maximum value of the range of random floats
    968        * returned by this generator.
    969        */
    970       result_type
    971       max() const
    972       { return 1.0; }
    973 
    974       /**
    975        * Gets the next random number in the sequence.
    976        */
    977       result_type
    978       operator()();
    979 
    980       /**
    981        * Compares two % subtract_with_carry_01 random number generator objects
    982        * of the same type for equality.
    983        *
    984        * @param __lhs A % subtract_with_carry_01 random number
    985        *              generator object.
    986        * @param __rhs Another % subtract_with_carry_01 random number generator
    987        *              object.
    988        *
    989        * @returns true if the two objects are equal, false otherwise.
    990        */
    991       friend bool
    992       operator==(const subtract_with_carry_01& __lhs,
    993 		 const subtract_with_carry_01& __rhs)
    994       {
    995 	for (int __i = 0; __i < long_lag; ++__i)
    996 	  if (!std::equal(__lhs._M_x[__i], __lhs._M_x[__i] + __n,
    997 			  __rhs._M_x[__i]))
    998 	    return false;
    999 	return true;
   1000       }
   1001 
   1002       /**
   1003        * Compares two % subtract_with_carry_01 random number generator objects
   1004        * of the same type for inequality.
   1005        *
   1006        * @param __lhs A % subtract_with_carry_01 random number
   1007        *              generator object.
   1008        *
   1009        * @param __rhs Another % subtract_with_carry_01 random number generator
   1010        *              object.
   1011        *
   1012        * @returns true if the two objects are not equal, false otherwise.
   1013        */
   1014       friend bool
   1015       operator!=(const subtract_with_carry_01& __lhs,
   1016 		 const subtract_with_carry_01& __rhs)
   1017       { return !(__lhs == __rhs); }
   1018 
   1019       /**
   1020        * Inserts the current state of a % subtract_with_carry_01 random number
   1021        * generator engine @p __x into the output stream @p __os.
   1022        *
   1023        * @param __os An output stream.
   1024        * @param __x  A % subtract_with_carry_01 random number generator engine.
   1025        *
   1026        * @returns The output stream with the state of @p __x inserted or in
   1027        * an error state.
   1028        */
   1029       template<typename _RealType1, int __w1, int __s1, int __r1,
   1030 	       typename _CharT, typename _Traits>
   1031         friend std::basic_ostream<_CharT, _Traits>&
   1032         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   1033 		   const subtract_with_carry_01<_RealType1, __w1, __s1,
   1034 		   __r1>& __x);
   1035 
   1036       /**
   1037        * Extracts the current state of a % subtract_with_carry_01 random number
   1038        * generator engine @p __x from the input stream @p __is.
   1039        *
   1040        * @param __is An input stream.
   1041        * @param __x  A % subtract_with_carry_01 random number generator engine.
   1042        *
   1043        * @returns The input stream with the state of @p __x extracted or in
   1044        * an error state.
   1045        */
   1046       template<typename _RealType1, int __w1, int __s1, int __r1,
   1047 	       typename _CharT, typename _Traits>
   1048         friend std::basic_istream<_CharT, _Traits>&
   1049         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   1050 		   subtract_with_carry_01<_RealType1, __w1, __s1, __r1>& __x);
   1051 
   1052     private:
   1053       template<class _Gen>
   1054         void
   1055         seed(_Gen& __g, true_type)
   1056         { return seed(static_cast<unsigned long>(__g)); }
   1057 
   1058       template<class _Gen>
   1059         void
   1060         seed(_Gen& __g, false_type);
   1061 
   1062       void
   1063       _M_initialize_npows();
   1064 
   1065       static const int __n = (__w + 31) / 32;
   1066 
   1067       typedef __detail::_UInt32Type _UInt32Type;
   1068       _UInt32Type  _M_x[long_lag][__n];
   1069       _RealType    _M_npows[__n];
   1070       _UInt32Type  _M_carry;
   1071       int          _M_p;
   1072     };
   1073 
   1074   typedef subtract_with_carry_01<float, 24, 10, 24>   ranlux_base_01;
   1075 
   1076   // _GLIBCXX_RESOLVE_LIB_DEFECTS
   1077   // 508. Bad parameters for ranlux64_base_01.
   1078   typedef subtract_with_carry_01<double, 48, 5, 12> ranlux64_base_01;
   1079 
   1080 
   1081   /**
   1082    * Produces random numbers from some base engine by discarding blocks of
   1083    * data.
   1084    *
   1085    * 0 <= @p __r <= @p __p
   1086    */
   1087   template<class _UniformRandomNumberGenerator, int __p, int __r>
   1088     class discard_block
   1089     {
   1090       // __glibcxx_class_requires(typename base_type::result_type,
   1091       //                          ArithmeticTypeConcept)
   1092 
   1093     public:
   1094       /** The type of the underlying generator engine. */
   1095       typedef _UniformRandomNumberGenerator   base_type;
   1096       /** The type of the generated random value. */
   1097       typedef typename base_type::result_type result_type;
   1098 
   1099       // parameter values
   1100       static const int block_size = __p;
   1101       static const int used_block = __r;
   1102 
   1103       /**
   1104        * Constructs a default %discard_block engine.
   1105        *
   1106        * The underlying engine is default constructed as well.
   1107        */
   1108       discard_block()
   1109       : _M_n(0) { }
   1110 
   1111       /**
   1112        * Copy constructs a %discard_block engine.
   1113        *
   1114        * Copies an existing base class random number generator.
   1115        * @param rng An existing (base class) engine object.
   1116        */
   1117       explicit
   1118       discard_block(const base_type& __rng)
   1119       : _M_b(__rng), _M_n(0) { }
   1120 
   1121       /**
   1122        * Seed constructs a %discard_block engine.
   1123        *
   1124        * Constructs the underlying generator engine seeded with @p __s.
   1125        * @param __s A seed value for the base class engine.
   1126        */
   1127       explicit
   1128       discard_block(unsigned long __s)
   1129       : _M_b(__s), _M_n(0) { }
   1130 
   1131       /**
   1132        * Generator construct a %discard_block engine.
   1133        *
   1134        * @param __g A seed generator function.
   1135        */
   1136       template<class _Gen>
   1137         discard_block(_Gen& __g)
   1138 	: _M_b(__g), _M_n(0) { }
   1139 
   1140       /**
   1141        * Reseeds the %discard_block object with the default seed for the
   1142        * underlying base class generator engine.
   1143        */
   1144       void seed()
   1145       {
   1146 	_M_b.seed();
   1147 	_M_n = 0;
   1148       }
   1149 
   1150       /**
   1151        * Reseeds the %discard_block object with the given seed generator
   1152        * function.
   1153        * @param __g A seed generator function.
   1154        */
   1155       template<class _Gen>
   1156         void seed(_Gen& __g)
   1157         {
   1158 	  _M_b.seed(__g);
   1159 	  _M_n = 0;
   1160 	}
   1161 
   1162       /**
   1163        * Gets a const reference to the underlying generator engine object.
   1164        */
   1165       const base_type&
   1166       base() const
   1167       { return _M_b; }
   1168 
   1169       /**
   1170        * Gets the minimum value in the generated random number range.
   1171        */
   1172       result_type
   1173       min() const
   1174       { return _M_b.min(); }
   1175 
   1176       /**
   1177        * Gets the maximum value in the generated random number range.
   1178        */
   1179       result_type
   1180       max() const
   1181       { return _M_b.max(); }
   1182 
   1183       /**
   1184        * Gets the next value in the generated random number sequence.
   1185        */
   1186       result_type
   1187       operator()();
   1188 
   1189       /**
   1190        * Compares two %discard_block random number generator objects of
   1191        * the same type for equality.
   1192        *
   1193        * @param __lhs A %discard_block random number generator object.
   1194        * @param __rhs Another %discard_block random number generator
   1195        *              object.
   1196        *
   1197        * @returns true if the two objects are equal, false otherwise.
   1198        */
   1199       friend bool
   1200       operator==(const discard_block& __lhs, const discard_block& __rhs)
   1201       { return (__lhs._M_b == __rhs._M_b) && (__lhs._M_n == __rhs._M_n); }
   1202 
   1203       /**
   1204        * Compares two %discard_block random number generator objects of
   1205        * the same type for inequality.
   1206        *
   1207        * @param __lhs A %discard_block random number generator object.
   1208        * @param __rhs Another %discard_block random number generator
   1209        *              object.
   1210        *
   1211        * @returns true if the two objects are not equal, false otherwise.
   1212        */
   1213       friend bool
   1214       operator!=(const discard_block& __lhs, const discard_block& __rhs)
   1215       { return !(__lhs == __rhs); }
   1216 
   1217       /**
   1218        * Inserts the current state of a %discard_block random number
   1219        * generator engine @p __x into the output stream @p __os.
   1220        *
   1221        * @param __os An output stream.
   1222        * @param __x  A %discard_block random number generator engine.
   1223        *
   1224        * @returns The output stream with the state of @p __x inserted or in
   1225        * an error state.
   1226        */
   1227       template<class _UniformRandomNumberGenerator1, int __p1, int __r1,
   1228 	       typename _CharT, typename _Traits>
   1229         friend std::basic_ostream<_CharT, _Traits>&
   1230         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   1231 		   const discard_block<_UniformRandomNumberGenerator1,
   1232 		   __p1, __r1>& __x);
   1233 
   1234       /**
   1235        * Extracts the current state of a % subtract_with_carry random number
   1236        * generator engine @p __x from the input stream @p __is.
   1237        *
   1238        * @param __is An input stream.
   1239        * @param __x  A %discard_block random number generator engine.
   1240        *
   1241        * @returns The input stream with the state of @p __x extracted or in
   1242        * an error state.
   1243        */
   1244       template<class _UniformRandomNumberGenerator1, int __p1, int __r1,
   1245 	       typename _CharT, typename _Traits>
   1246         friend std::basic_istream<_CharT, _Traits>&
   1247         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   1248 		   discard_block<_UniformRandomNumberGenerator1,
   1249 		   __p1, __r1>& __x);
   1250 
   1251     private:
   1252       base_type _M_b;
   1253       int       _M_n;
   1254     };
   1255 
   1256 
   1257   /**
   1258    * James's luxury-level-3 integer adaptation of Luescher's generator.
   1259    */
   1260   typedef discard_block<
   1261     subtract_with_carry<unsigned long, (1UL << 24), 10, 24>,
   1262       223,
   1263       24
   1264       > ranlux3;
   1265 
   1266   /**
   1267    * James's luxury-level-4 integer adaptation of Luescher's generator.
   1268    */
   1269   typedef discard_block<
   1270     subtract_with_carry<unsigned long, (1UL << 24), 10, 24>,
   1271       389,
   1272       24
   1273       > ranlux4;
   1274 
   1275   typedef discard_block<
   1276     subtract_with_carry_01<float, 24, 10, 24>,
   1277       223,
   1278       24
   1279       > ranlux3_01;
   1280 
   1281   typedef discard_block<
   1282     subtract_with_carry_01<float, 24, 10, 24>,
   1283       389,
   1284       24
   1285       > ranlux4_01;
   1286 
   1287 
   1288   /**
   1289    * A random number generator adaptor class that combines two random number
   1290    * generator engines into a single output sequence.
   1291    */
   1292   template<class _UniformRandomNumberGenerator1, int __s1,
   1293 	   class _UniformRandomNumberGenerator2, int __s2>
   1294     class xor_combine
   1295     {
   1296       // __glibcxx_class_requires(typename _UniformRandomNumberGenerator1::
   1297       //                          result_type, ArithmeticTypeConcept)
   1298       // __glibcxx_class_requires(typename _UniformRandomNumberGenerator2::
   1299       //                          result_type, ArithmeticTypeConcept)
   1300 
   1301     public:
   1302       /** The type of the first underlying generator engine. */
   1303       typedef _UniformRandomNumberGenerator1   base1_type;
   1304       /** The type of the second underlying generator engine. */
   1305       typedef _UniformRandomNumberGenerator2   base2_type;
   1306 
   1307     private:
   1308       typedef typename base1_type::result_type _Result_type1;
   1309       typedef typename base2_type::result_type _Result_type2;
   1310 
   1311     public:
   1312       /** The type of the generated random value. */
   1313       typedef typename __gnu_cxx::__conditional_type<(sizeof(_Result_type1)
   1314 						      > sizeof(_Result_type2)),
   1315 	_Result_type1, _Result_type2>::__type result_type;
   1316 
   1317       // parameter values
   1318       static const int shift1 = __s1;
   1319       static const int shift2 = __s2;
   1320 
   1321       // constructors and member function
   1322       xor_combine()
   1323       : _M_b1(), _M_b2()
   1324       { _M_initialize_max(); }
   1325 
   1326       xor_combine(const base1_type& __rng1, const base2_type& __rng2)
   1327       : _M_b1(__rng1), _M_b2(__rng2)
   1328       { _M_initialize_max(); }
   1329 
   1330       xor_combine(unsigned long __s)
   1331       : _M_b1(__s), _M_b2(__s + 1)
   1332       { _M_initialize_max(); }
   1333 
   1334       template<class _Gen>
   1335         xor_combine(_Gen& __g)
   1336 	: _M_b1(__g), _M_b2(__g)
   1337         { _M_initialize_max(); }
   1338 
   1339       void
   1340       seed()
   1341       {
   1342 	_M_b1.seed();
   1343 	_M_b2.seed();
   1344       }
   1345 
   1346       template<class _Gen>
   1347         void
   1348         seed(_Gen& __g)
   1349         {
   1350 	  _M_b1.seed(__g);
   1351 	  _M_b2.seed(__g);
   1352 	}
   1353 
   1354       const base1_type&
   1355       base1() const
   1356       { return _M_b1; }
   1357 
   1358       const base2_type&
   1359       base2() const
   1360       { return _M_b2; }
   1361 
   1362       result_type
   1363       min() const
   1364       { return 0; }
   1365 
   1366       result_type
   1367       max() const
   1368       { return _M_max; }
   1369 
   1370       /**
   1371        * Gets the next random number in the sequence.
   1372        */
   1373       // NB: Not exactly the TR1 formula, per N2079 instead.
   1374       result_type
   1375       operator()()
   1376       {
   1377 	return ((result_type(_M_b1() - _M_b1.min()) << shift1)
   1378 		^ (result_type(_M_b2() - _M_b2.min()) << shift2));
   1379       }
   1380 
   1381       /**
   1382        * Compares two %xor_combine random number generator objects of
   1383        * the same type for equality.
   1384        *
   1385        * @param __lhs A %xor_combine random number generator object.
   1386        * @param __rhs Another %xor_combine random number generator
   1387        *              object.
   1388        *
   1389        * @returns true if the two objects are equal, false otherwise.
   1390        */
   1391       friend bool
   1392       operator==(const xor_combine& __lhs, const xor_combine& __rhs)
   1393       {
   1394 	return (__lhs.base1() == __rhs.base1())
   1395 	        && (__lhs.base2() == __rhs.base2());
   1396       }
   1397 
   1398       /**
   1399        * Compares two %xor_combine random number generator objects of
   1400        * the same type for inequality.
   1401        *
   1402        * @param __lhs A %xor_combine random number generator object.
   1403        * @param __rhs Another %xor_combine random number generator
   1404        *              object.
   1405        *
   1406        * @returns true if the two objects are not equal, false otherwise.
   1407        */
   1408       friend bool
   1409       operator!=(const xor_combine& __lhs, const xor_combine& __rhs)
   1410       { return !(__lhs == __rhs); }
   1411 
   1412       /**
   1413        * Inserts the current state of a %xor_combine random number
   1414        * generator engine @p __x into the output stream @p __os.
   1415        *
   1416        * @param __os An output stream.
   1417        * @param __x  A %xor_combine random number generator engine.
   1418        *
   1419        * @returns The output stream with the state of @p __x inserted or in
   1420        * an error state.
   1421        */
   1422       template<class _UniformRandomNumberGenerator11, int __s11,
   1423 	       class _UniformRandomNumberGenerator21, int __s21,
   1424 	       typename _CharT, typename _Traits>
   1425         friend std::basic_ostream<_CharT, _Traits>&
   1426         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   1427 		   const xor_combine<_UniformRandomNumberGenerator11, __s11,
   1428 		   _UniformRandomNumberGenerator21, __s21>& __x);
   1429 
   1430       /**
   1431        * Extracts the current state of a %xor_combine random number
   1432        * generator engine @p __x from the input stream @p __is.
   1433        *
   1434        * @param __is An input stream.
   1435        * @param __x  A %xor_combine random number generator engine.
   1436        *
   1437        * @returns The input stream with the state of @p __x extracted or in
   1438        * an error state.
   1439        */
   1440       template<class _UniformRandomNumberGenerator11, int __s11,
   1441 	       class _UniformRandomNumberGenerator21, int __s21,
   1442 	       typename _CharT, typename _Traits>
   1443         friend std::basic_istream<_CharT, _Traits>&
   1444         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   1445 		   xor_combine<_UniformRandomNumberGenerator11, __s11,
   1446 		   _UniformRandomNumberGenerator21, __s21>& __x);
   1447 
   1448     private:
   1449       void
   1450       _M_initialize_max();
   1451 
   1452       result_type
   1453       _M_initialize_max_aux(result_type, result_type, int);
   1454 
   1455       base1_type  _M_b1;
   1456       base2_type  _M_b2;
   1457       result_type _M_max;
   1458     };
   1459 
   1460 
   1461   /**
   1462    * A standard interface to a platform-specific non-deterministic
   1463    * random number generator (if any are available).
   1464    */
   1465   class random_device
   1466   {
   1467   public:
   1468     // types
   1469     typedef unsigned int result_type;
   1470 
   1471     // constructors, destructors and member functions
   1472 
   1473 #ifdef _GLIBCXX_USE_RANDOM_TR1
   1474 
   1475     explicit
   1476     random_device(const std::string& __token = "/dev/urandom")
   1477     {
   1478       if ((__token != "/dev/urandom" && __token != "/dev/random")
   1479 	  || !(_M_file = std::fopen(__token.c_str(), "rb")))
   1480 	std::__throw_runtime_error(__N("random_device::"
   1481 				       "random_device(const std::string&)"));
   1482     }
   1483 
   1484     ~random_device()
   1485     { std::fclose(_M_file); }
   1486 
   1487 #else
   1488 
   1489     explicit
   1490     random_device(const std::string& __token = "mt19937")
   1491     : _M_mt(_M_strtoul(__token)) { }
   1492 
   1493   private:
   1494     static unsigned long
   1495     _M_strtoul(const std::string& __str)
   1496     {
   1497       unsigned long __ret = 5489UL;
   1498       if (__str != "mt19937")
   1499 	{
   1500 	  const char* __nptr = __str.c_str();
   1501 	  char* __endptr;
   1502 	  __ret = std::strtoul(__nptr, &__endptr, 0);
   1503 	  if (*__nptr == '\0' || *__endptr != '\0')
   1504 	    std::__throw_runtime_error(__N("random_device::_M_strtoul"
   1505 					   "(const std::string&)"));
   1506 	}
   1507       return __ret;
   1508     }
   1509 
   1510   public:
   1511 
   1512 #endif
   1513 
   1514     result_type
   1515     min() const
   1516     { return std::numeric_limits<result_type>::min(); }
   1517 
   1518     result_type
   1519     max() const
   1520     { return std::numeric_limits<result_type>::max(); }
   1521 
   1522     double
   1523     entropy() const
   1524     { return 0.0; }
   1525 
   1526     result_type
   1527     operator()()
   1528     {
   1529 #ifdef _GLIBCXX_USE_RANDOM_TR1
   1530       result_type __ret;
   1531       std::fread(reinterpret_cast<void*>(&__ret), sizeof(result_type),
   1532 		 1, _M_file);
   1533       return __ret;
   1534 #else
   1535       return _M_mt();
   1536 #endif
   1537     }
   1538 
   1539   private:
   1540     random_device(const random_device&);
   1541     void operator=(const random_device&);
   1542 
   1543 #ifdef _GLIBCXX_USE_RANDOM_TR1
   1544     FILE*        _M_file;
   1545 #else
   1546     mt19937      _M_mt;
   1547 #endif
   1548   };
   1549 
   1550   /* @} */ // group tr1_random_generators
   1551 
   1552   /**
   1553    * @addtogroup tr1_random_distributions Random Number Distributions
   1554    * @ingroup tr1_random
   1555    * @{
   1556    */
   1557 
   1558   /**
   1559    * @addtogroup tr1_random_distributions_discrete Discrete Distributions
   1560    * @ingroup tr1_random_distributions
   1561    * @{
   1562    */
   1563 
   1564   /**
   1565    * @brief Uniform discrete distribution for random numbers.
   1566    * A discrete random distribution on the range @f$[min, max]@f$ with equal
   1567    * probability throughout the range.
   1568    */
   1569   template<typename _IntType = int>
   1570     class uniform_int
   1571     {
   1572       __glibcxx_class_requires(_IntType, _IntegerConcept)
   1573 
   1574     public:
   1575       /** The type of the parameters of the distribution. */
   1576       typedef _IntType input_type;
   1577       /** The type of the range of the distribution. */
   1578       typedef _IntType result_type;
   1579 
   1580     public:
   1581       /**
   1582        * Constructs a uniform distribution object.
   1583        */
   1584       explicit
   1585       uniform_int(_IntType __min = 0, _IntType __max = 9)
   1586       : _M_min(__min), _M_max(__max)
   1587       {
   1588 	_GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
   1589       }
   1590 
   1591       /**
   1592        * Gets the inclusive lower bound of the distribution range.
   1593        */
   1594       result_type
   1595       min() const
   1596       { return _M_min; }
   1597 
   1598       /**
   1599        * Gets the inclusive upper bound of the distribution range.
   1600        */
   1601       result_type
   1602       max() const
   1603       { return _M_max; }
   1604 
   1605       /**
   1606        * Resets the distribution state.
   1607        *
   1608        * Does nothing for the uniform integer distribution.
   1609        */
   1610       void
   1611       reset() { }
   1612 
   1613       /**
   1614        * Gets a uniformly distributed random number in the range
   1615        * @f$(min, max)@f$.
   1616        */
   1617       template<typename _UniformRandomNumberGenerator>
   1618         result_type
   1619         operator()(_UniformRandomNumberGenerator& __urng)
   1620         {
   1621 	  typedef typename _UniformRandomNumberGenerator::result_type
   1622 	    _UResult_type;
   1623 	  return _M_call(__urng, _M_min, _M_max,
   1624 			 typename is_integral<_UResult_type>::type());
   1625 	}
   1626 
   1627       /**
   1628        * Gets a uniform random number in the range @f$[0, n)@f$.
   1629        *
   1630        * This function is aimed at use with std::random_shuffle.
   1631        */
   1632       template<typename _UniformRandomNumberGenerator>
   1633         result_type
   1634         operator()(_UniformRandomNumberGenerator& __urng, result_type __n)
   1635         {
   1636 	  typedef typename _UniformRandomNumberGenerator::result_type
   1637 	    _UResult_type;
   1638 	  return _M_call(__urng, 0, __n - 1,
   1639 			 typename is_integral<_UResult_type>::type());
   1640 	}
   1641 
   1642       /**
   1643        * Inserts a %uniform_int random number distribution @p __x into the
   1644        * output stream @p os.
   1645        *
   1646        * @param __os An output stream.
   1647        * @param __x  A %uniform_int random number distribution.
   1648        *
   1649        * @returns The output stream with the state of @p __x inserted or in
   1650        * an error state.
   1651        */
   1652       template<typename _IntType1, typename _CharT, typename _Traits>
   1653         friend std::basic_ostream<_CharT, _Traits>&
   1654         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   1655 		   const uniform_int<_IntType1>& __x);
   1656 
   1657       /**
   1658        * Extracts a %uniform_int random number distribution
   1659        * @p __x from the input stream @p __is.
   1660        *
   1661        * @param __is An input stream.
   1662        * @param __x  A %uniform_int random number generator engine.
   1663        *
   1664        * @returns The input stream with @p __x extracted or in an error state.
   1665        */
   1666       template<typename _IntType1, typename _CharT, typename _Traits>
   1667         friend std::basic_istream<_CharT, _Traits>&
   1668         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   1669 		   uniform_int<_IntType1>& __x);
   1670 
   1671     private:
   1672       template<typename _UniformRandomNumberGenerator>
   1673         result_type
   1674         _M_call(_UniformRandomNumberGenerator& __urng,
   1675 		result_type __min, result_type __max, true_type);
   1676 
   1677       template<typename _UniformRandomNumberGenerator>
   1678         result_type
   1679         _M_call(_UniformRandomNumberGenerator& __urng,
   1680 		result_type __min, result_type __max, false_type)
   1681         {
   1682 	  return result_type((__urng() - __urng.min())
   1683 			     / (__urng.max() - __urng.min())
   1684 			     * (__max - __min + 1)) + __min;
   1685 	}
   1686 
   1687       _IntType _M_min;
   1688       _IntType _M_max;
   1689     };
   1690 
   1691 
   1692   /**
   1693    * @brief A Bernoulli random number distribution.
   1694    *
   1695    * Generates a sequence of true and false values with likelihood @f$ p @f$
   1696    * that true will come up and @f$ (1 - p) @f$ that false will appear.
   1697    */
   1698   class bernoulli_distribution
   1699   {
   1700   public:
   1701     typedef int  input_type;
   1702     typedef bool result_type;
   1703 
   1704   public:
   1705     /**
   1706      * Constructs a Bernoulli distribution with likelihood @p p.
   1707      *
   1708      * @param __p  [IN]  The likelihood of a true result being returned.  Must
   1709      * be in the interval @f$ [0, 1] @f$.
   1710      */
   1711     explicit
   1712     bernoulli_distribution(double __p = 0.5)
   1713     : _M_p(__p)
   1714     {
   1715       _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
   1716     }
   1717 
   1718     /**
   1719      * Gets the @p p parameter of the distribution.
   1720      */
   1721     double
   1722     p() const
   1723     { return _M_p; }
   1724 
   1725     /**
   1726      * Resets the distribution state.
   1727      *
   1728      * Does nothing for a Bernoulli distribution.
   1729      */
   1730     void
   1731     reset() { }
   1732 
   1733     /**
   1734      * Gets the next value in the Bernoullian sequence.
   1735      */
   1736     template<class _UniformRandomNumberGenerator>
   1737       result_type
   1738       operator()(_UniformRandomNumberGenerator& __urng)
   1739       {
   1740 	if ((__urng() - __urng.min()) < _M_p * (__urng.max() - __urng.min()))
   1741 	  return true;
   1742 	return false;
   1743       }
   1744 
   1745     /**
   1746      * Inserts a %bernoulli_distribution random number distribution
   1747      * @p __x into the output stream @p __os.
   1748      *
   1749      * @param __os An output stream.
   1750      * @param __x  A %bernoulli_distribution random number distribution.
   1751      *
   1752      * @returns The output stream with the state of @p __x inserted or in
   1753      * an error state.
   1754      */
   1755     template<typename _CharT, typename _Traits>
   1756       friend std::basic_ostream<_CharT, _Traits>&
   1757       operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   1758 		 const bernoulli_distribution& __x);
   1759 
   1760     /**
   1761      * Extracts a %bernoulli_distribution random number distribution
   1762      * @p __x from the input stream @p __is.
   1763      *
   1764      * @param __is An input stream.
   1765      * @param __x  A %bernoulli_distribution random number generator engine.
   1766      *
   1767      * @returns The input stream with @p __x extracted or in an error state.
   1768      */
   1769     template<typename _CharT, typename _Traits>
   1770       friend std::basic_istream<_CharT, _Traits>&
   1771       operator>>(std::basic_istream<_CharT, _Traits>& __is,
   1772 		 bernoulli_distribution& __x)
   1773       { return __is >> __x._M_p; }
   1774 
   1775   private:
   1776     double _M_p;
   1777   };
   1778 
   1779 
   1780   /**
   1781    * @brief A discrete geometric random number distribution.
   1782    *
   1783    * The formula for the geometric probability mass function is
   1784    * @f$ p(i) = (1 - p)p^{i-1} @f$ where @f$ p @f$ is the parameter of the
   1785    * distribution.
   1786    */
   1787   template<typename _IntType = int, typename _RealType = double>
   1788     class geometric_distribution
   1789     {
   1790     public:
   1791       // types
   1792       typedef _RealType input_type;
   1793       typedef _IntType  result_type;
   1794 
   1795       // constructors and member function
   1796       explicit
   1797       geometric_distribution(const _RealType& __p = _RealType(0.5))
   1798       : _M_p(__p)
   1799       {
   1800 	_GLIBCXX_DEBUG_ASSERT((_M_p > 0.0) && (_M_p < 1.0));
   1801 	_M_initialize();
   1802       }
   1803 
   1804       /**
   1805        * Gets the distribution parameter @p p.
   1806        */
   1807       _RealType
   1808       p() const
   1809       { return _M_p; }
   1810 
   1811       void
   1812       reset() { }
   1813 
   1814       template<class _UniformRandomNumberGenerator>
   1815         result_type
   1816         operator()(_UniformRandomNumberGenerator& __urng);
   1817 
   1818       /**
   1819        * Inserts a %geometric_distribution random number distribution
   1820        * @p __x into the output stream @p __os.
   1821        *
   1822        * @param __os An output stream.
   1823        * @param __x  A %geometric_distribution random number distribution.
   1824        *
   1825        * @returns The output stream with the state of @p __x inserted or in
   1826        * an error state.
   1827        */
   1828       template<typename _IntType1, typename _RealType1,
   1829 	       typename _CharT, typename _Traits>
   1830         friend std::basic_ostream<_CharT, _Traits>&
   1831         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   1832 		   const geometric_distribution<_IntType1, _RealType1>& __x);
   1833 
   1834       /**
   1835        * Extracts a %geometric_distribution random number distribution
   1836        * @p __x from the input stream @p __is.
   1837        *
   1838        * @param __is An input stream.
   1839        * @param __x  A %geometric_distribution random number generator engine.
   1840        *
   1841        * @returns The input stream with @p __x extracted or in an error state.
   1842        */
   1843       template<typename _CharT, typename _Traits>
   1844         friend std::basic_istream<_CharT, _Traits>&
   1845         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   1846 		   geometric_distribution& __x)
   1847         {
   1848 	  __is >> __x._M_p;
   1849 	  __x._M_initialize();
   1850 	  return __is;
   1851 	}
   1852 
   1853     private:
   1854       void
   1855       _M_initialize()
   1856       { _M_log_p = std::log(_M_p); }
   1857 
   1858       _RealType _M_p;
   1859       _RealType _M_log_p;
   1860     };
   1861 
   1862 
   1863   template<typename _RealType>
   1864     class normal_distribution;
   1865 
   1866   /**
   1867    * @brief A discrete Poisson random number distribution.
   1868    *
   1869    * The formula for the Poisson probability mass function is
   1870    * @f$ p(i) = \frac{mean^i}{i!} e^{-mean} @f$ where @f$ mean @f$ is the
   1871    * parameter of the distribution.
   1872    */
   1873   template<typename _IntType = int, typename _RealType = double>
   1874     class poisson_distribution
   1875     {
   1876     public:
   1877       // types
   1878       typedef _RealType input_type;
   1879       typedef _IntType  result_type;
   1880 
   1881       // constructors and member function
   1882       explicit
   1883       poisson_distribution(const _RealType& __mean = _RealType(1))
   1884       : _M_mean(__mean), _M_nd()
   1885       {
   1886 	_GLIBCXX_DEBUG_ASSERT(_M_mean > 0.0);
   1887 	_M_initialize();
   1888       }
   1889 
   1890       /**
   1891        * Gets the distribution parameter @p mean.
   1892        */
   1893       _RealType
   1894       mean() const
   1895       { return _M_mean; }
   1896 
   1897       void
   1898       reset()
   1899       { _M_nd.reset(); }
   1900 
   1901       template<class _UniformRandomNumberGenerator>
   1902         result_type
   1903         operator()(_UniformRandomNumberGenerator& __urng);
   1904 
   1905       /**
   1906        * Inserts a %poisson_distribution random number distribution
   1907        * @p __x into the output stream @p __os.
   1908        *
   1909        * @param __os An output stream.
   1910        * @param __x  A %poisson_distribution random number distribution.
   1911        *
   1912        * @returns The output stream with the state of @p __x inserted or in
   1913        * an error state.
   1914        */
   1915       template<typename _IntType1, typename _RealType1,
   1916 	       typename _CharT, typename _Traits>
   1917         friend std::basic_ostream<_CharT, _Traits>&
   1918         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   1919 		   const poisson_distribution<_IntType1, _RealType1>& __x);
   1920 
   1921       /**
   1922        * Extracts a %poisson_distribution random number distribution
   1923        * @p __x from the input stream @p __is.
   1924        *
   1925        * @param __is An input stream.
   1926        * @param __x  A %poisson_distribution random number generator engine.
   1927        *
   1928        * @returns The input stream with @p __x extracted or in an error state.
   1929        */
   1930       template<typename _IntType1, typename _RealType1,
   1931 	       typename _CharT, typename _Traits>
   1932         friend std::basic_istream<_CharT, _Traits>&
   1933         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   1934 		   poisson_distribution<_IntType1, _RealType1>& __x);
   1935 
   1936     private:
   1937       void
   1938       _M_initialize();
   1939 
   1940       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
   1941       normal_distribution<_RealType> _M_nd;
   1942 
   1943       _RealType _M_mean;
   1944 
   1945       // Hosts either log(mean) or the threshold of the simple method.
   1946       _RealType _M_lm_thr;
   1947 #if _GLIBCXX_USE_C99_MATH_TR1
   1948       _RealType _M_lfm, _M_sm, _M_d, _M_scx, _M_1cx, _M_c2b, _M_cb;
   1949 #endif
   1950     };
   1951 
   1952 
   1953   /**
   1954    * @brief A discrete binomial random number distribution.
   1955    *
   1956    * The formula for the binomial probability mass function is
   1957    * @f$ p(i) = \binom{n}{i} p^i (1 - p)^{t - i} @f$ where @f$ t @f$
   1958    * and @f$ p @f$ are the parameters of the distribution.
   1959    */
   1960   template<typename _IntType = int, typename _RealType = double>
   1961     class binomial_distribution
   1962     {
   1963     public:
   1964       // types
   1965       typedef _RealType input_type;
   1966       typedef _IntType  result_type;
   1967 
   1968       // constructors and member function
   1969       explicit
   1970       binomial_distribution(_IntType __t = 1,
   1971 			    const _RealType& __p = _RealType(0.5))
   1972       : _M_t(__t), _M_p(__p), _M_nd()
   1973       {
   1974 	_GLIBCXX_DEBUG_ASSERT((_M_t >= 0) && (_M_p >= 0.0) && (_M_p <= 1.0));
   1975 	_M_initialize();
   1976       }
   1977 
   1978       /**
   1979        * Gets the distribution @p t parameter.
   1980        */
   1981       _IntType
   1982       t() const
   1983       { return _M_t; }
   1984 
   1985       /**
   1986        * Gets the distribution @p p parameter.
   1987        */
   1988       _RealType
   1989       p() const
   1990       { return _M_p; }
   1991 
   1992       void
   1993       reset()
   1994       { _M_nd.reset(); }
   1995 
   1996       template<class _UniformRandomNumberGenerator>
   1997         result_type
   1998         operator()(_UniformRandomNumberGenerator& __urng);
   1999 
   2000       /**
   2001        * Inserts a %binomial_distribution random number distribution
   2002        * @p __x into the output stream @p __os.
   2003        *
   2004        * @param __os An output stream.
   2005        * @param __x  A %binomial_distribution random number distribution.
   2006        *
   2007        * @returns The output stream with the state of @p __x inserted or in
   2008        * an error state.
   2009        */
   2010       template<typename _IntType1, typename _RealType1,
   2011 	       typename _CharT, typename _Traits>
   2012         friend std::basic_ostream<_CharT, _Traits>&
   2013         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   2014 		   const binomial_distribution<_IntType1, _RealType1>& __x);
   2015 
   2016       /**
   2017        * Extracts a %binomial_distribution random number distribution
   2018        * @p __x from the input stream @p __is.
   2019        *
   2020        * @param __is An input stream.
   2021        * @param __x  A %binomial_distribution random number generator engine.
   2022        *
   2023        * @returns The input stream with @p __x extracted or in an error state.
   2024        */
   2025       template<typename _IntType1, typename _RealType1,
   2026 	       typename _CharT, typename _Traits>
   2027         friend std::basic_istream<_CharT, _Traits>&
   2028         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   2029 		   binomial_distribution<_IntType1, _RealType1>& __x);
   2030 
   2031     private:
   2032       void
   2033       _M_initialize();
   2034 
   2035       template<class _UniformRandomNumberGenerator>
   2036         result_type
   2037         _M_waiting(_UniformRandomNumberGenerator& __urng, _IntType __t);
   2038 
   2039       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
   2040       normal_distribution<_RealType> _M_nd;
   2041 
   2042       _RealType _M_q;
   2043 #if _GLIBCXX_USE_C99_MATH_TR1
   2044       _RealType _M_d1, _M_d2, _M_s1, _M_s2, _M_c,
   2045 	        _M_a1, _M_a123, _M_s, _M_lf, _M_lp1p;
   2046 #endif
   2047       _RealType _M_p;
   2048       _IntType  _M_t;
   2049 
   2050       bool      _M_easy;
   2051     };
   2052 
   2053   /* @} */ // group tr1_random_distributions_discrete
   2054 
   2055   /**
   2056    * @addtogroup tr1_random_distributions_continuous Continuous Distributions
   2057    * @ingroup tr1_random_distributions
   2058    * @{
   2059    */
   2060 
   2061   /**
   2062    * @brief Uniform continuous distribution for random numbers.
   2063    *
   2064    * A continuous random distribution on the range [min, max) with equal
   2065    * probability throughout the range.  The URNG should be real-valued and
   2066    * deliver number in the range [0, 1).
   2067    */
   2068   template<typename _RealType = double>
   2069     class uniform_real
   2070     {
   2071     public:
   2072       // types
   2073       typedef _RealType input_type;
   2074       typedef _RealType result_type;
   2075 
   2076     public:
   2077       /**
   2078        * Constructs a uniform_real object.
   2079        *
   2080        * @param __min [IN]  The lower bound of the distribution.
   2081        * @param __max [IN]  The upper bound of the distribution.
   2082        */
   2083       explicit
   2084       uniform_real(_RealType __min = _RealType(0),
   2085 		   _RealType __max = _RealType(1))
   2086       : _M_min(__min), _M_max(__max)
   2087       {
   2088 	_GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
   2089       }
   2090 
   2091       result_type
   2092       min() const
   2093       { return _M_min; }
   2094 
   2095       result_type
   2096       max() const
   2097       { return _M_max; }
   2098 
   2099       void
   2100       reset() { }
   2101 
   2102       template<class _UniformRandomNumberGenerator>
   2103         result_type
   2104         operator()(_UniformRandomNumberGenerator& __urng)
   2105         { return (__urng() * (_M_max - _M_min)) + _M_min; }
   2106 
   2107       /**
   2108        * Inserts a %uniform_real random number distribution @p __x into the
   2109        * output stream @p __os.
   2110        *
   2111        * @param __os An output stream.
   2112        * @param __x  A %uniform_real random number distribution.
   2113        *
   2114        * @returns The output stream with the state of @p __x inserted or in
   2115        * an error state.
   2116        */
   2117       template<typename _RealType1, typename _CharT, typename _Traits>
   2118         friend std::basic_ostream<_CharT, _Traits>&
   2119         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   2120 		   const uniform_real<_RealType1>& __x);
   2121 
   2122       /**
   2123        * Extracts a %uniform_real random number distribution
   2124        * @p __x from the input stream @p __is.
   2125        *
   2126        * @param __is An input stream.
   2127        * @param __x  A %uniform_real random number generator engine.
   2128        *
   2129        * @returns The input stream with @p __x extracted or in an error state.
   2130        */
   2131       template<typename _RealType1, typename _CharT, typename _Traits>
   2132         friend std::basic_istream<_CharT, _Traits>&
   2133         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   2134 		   uniform_real<_RealType1>& __x);
   2135 
   2136     private:
   2137       _RealType _M_min;
   2138       _RealType _M_max;
   2139     };
   2140 
   2141 
   2142   /**
   2143    * @brief An exponential continuous distribution for random numbers.
   2144    *
   2145    * The formula for the exponential probability mass function is
   2146    * @f$ p(x) = \lambda e^{-\lambda x} @f$.
   2147    *
   2148    * <table border=1 cellpadding=10 cellspacing=0>
   2149    * <caption align=top>Distribution Statistics</caption>
   2150    * <tr><td>Mean</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
   2151    * <tr><td>Median</td><td>@f$ \frac{\ln 2}{\lambda} @f$</td></tr>
   2152    * <tr><td>Mode</td><td>@f$ zero @f$</td></tr>
   2153    * <tr><td>Range</td><td>@f$[0, \infty]@f$</td></tr>
   2154    * <tr><td>Standard Deviation</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
   2155    * </table>
   2156    */
   2157   template<typename _RealType = double>
   2158     class exponential_distribution
   2159     {
   2160     public:
   2161       // types
   2162       typedef _RealType input_type;
   2163       typedef _RealType result_type;
   2164 
   2165     public:
   2166       /**
   2167        * Constructs an exponential distribution with inverse scale parameter
   2168        * @f$ \lambda @f$.
   2169        */
   2170       explicit
   2171       exponential_distribution(const result_type& __lambda = result_type(1))
   2172       : _M_lambda(__lambda)
   2173       {
   2174 	_GLIBCXX_DEBUG_ASSERT(_M_lambda > 0);
   2175       }
   2176 
   2177       /**
   2178        * Gets the inverse scale parameter of the distribution.
   2179        */
   2180       _RealType
   2181       lambda() const
   2182       { return _M_lambda; }
   2183 
   2184       /**
   2185        * Resets the distribution.
   2186        *
   2187        * Has no effect on exponential distributions.
   2188        */
   2189       void
   2190       reset() { }
   2191 
   2192       template<class _UniformRandomNumberGenerator>
   2193         result_type
   2194         operator()(_UniformRandomNumberGenerator& __urng)
   2195         { return -std::log(__urng()) / _M_lambda; }
   2196 
   2197       /**
   2198        * Inserts a %exponential_distribution random number distribution
   2199        * @p __x into the output stream @p __os.
   2200        *
   2201        * @param __os An output stream.
   2202        * @param __x  A %exponential_distribution random number distribution.
   2203        *
   2204        * @returns The output stream with the state of @p __x inserted or in
   2205        * an error state.
   2206        */
   2207       template<typename _RealType1, typename _CharT, typename _Traits>
   2208         friend std::basic_ostream<_CharT, _Traits>&
   2209         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   2210 		   const exponential_distribution<_RealType1>& __x);
   2211 
   2212       /**
   2213        * Extracts a %exponential_distribution random number distribution
   2214        * @p __x from the input stream @p __is.
   2215        *
   2216        * @param __is An input stream.
   2217        * @param __x A %exponential_distribution random number
   2218        *            generator engine.
   2219        *
   2220        * @returns The input stream with @p __x extracted or in an error state.
   2221        */
   2222       template<typename _CharT, typename _Traits>
   2223         friend std::basic_istream<_CharT, _Traits>&
   2224         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   2225 		   exponential_distribution& __x)
   2226         { return __is >> __x._M_lambda; }
   2227 
   2228     private:
   2229       result_type _M_lambda;
   2230     };
   2231 
   2232 
   2233   /**
   2234    * @brief A normal continuous distribution for random numbers.
   2235    *
   2236    * The formula for the normal probability mass function is
   2237    * @f$ p(x) = \frac{1}{\sigma \sqrt{2 \pi}}
   2238    *            e^{- \frac{{x - mean}^ {2}}{2 \sigma ^ {2}} } @f$.
   2239    */
   2240   template<typename _RealType = double>
   2241     class normal_distribution
   2242     {
   2243     public:
   2244       // types
   2245       typedef _RealType input_type;
   2246       typedef _RealType result_type;
   2247 
   2248     public:
   2249       /**
   2250        * Constructs a normal distribution with parameters @f$ mean @f$ and
   2251        * @f$ \sigma @f$.
   2252        */
   2253       explicit
   2254       normal_distribution(const result_type& __mean = result_type(0),
   2255 			  const result_type& __sigma = result_type(1))
   2256       : _M_mean(__mean), _M_sigma(__sigma), _M_saved_available(false)
   2257       {
   2258 	_GLIBCXX_DEBUG_ASSERT(_M_sigma > 0);
   2259       }
   2260 
   2261       /**
   2262        * Gets the mean of the distribution.
   2263        */
   2264       _RealType
   2265       mean() const
   2266       { return _M_mean; }
   2267 
   2268       /**
   2269        * Gets the @f$ \sigma @f$ of the distribution.
   2270        */
   2271       _RealType
   2272       sigma() const
   2273       { return _M_sigma; }
   2274 
   2275       /**
   2276        * Resets the distribution.
   2277        */
   2278       void
   2279       reset()
   2280       { _M_saved_available = false; }
   2281 
   2282       template<class _UniformRandomNumberGenerator>
   2283         result_type
   2284         operator()(_UniformRandomNumberGenerator& __urng);
   2285 
   2286       /**
   2287        * Inserts a %normal_distribution random number distribution
   2288        * @p __x into the output stream @p __os.
   2289        *
   2290        * @param __os An output stream.
   2291        * @param __x  A %normal_distribution random number distribution.
   2292        *
   2293        * @returns The output stream with the state of @p __x inserted or in
   2294        * an error state.
   2295        */
   2296       template<typename _RealType1, typename _CharT, typename _Traits>
   2297         friend std::basic_ostream<_CharT, _Traits>&
   2298         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   2299 		   const normal_distribution<_RealType1>& __x);
   2300 
   2301       /**
   2302        * Extracts a %normal_distribution random number distribution
   2303        * @p __x from the input stream @p __is.
   2304        *
   2305        * @param __is An input stream.
   2306        * @param __x  A %normal_distribution random number generator engine.
   2307        *
   2308        * @returns The input stream with @p __x extracted or in an error state.
   2309        */
   2310       template<typename _RealType1, typename _CharT, typename _Traits>
   2311         friend std::basic_istream<_CharT, _Traits>&
   2312         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   2313 		   normal_distribution<_RealType1>& __x);
   2314 
   2315     private:
   2316       result_type _M_mean;
   2317       result_type _M_sigma;
   2318       result_type _M_saved;
   2319       bool        _M_saved_available;
   2320     };
   2321 
   2322 
   2323   /**
   2324    * @brief A gamma continuous distribution for random numbers.
   2325    *
   2326    * The formula for the gamma probability mass function is
   2327    * @f$ p(x) = \frac{1}{\Gamma(\alpha)} x^{\alpha - 1} e^{-x} @f$.
   2328    */
   2329   template<typename _RealType = double>
   2330     class gamma_distribution
   2331     {
   2332     public:
   2333       // types
   2334       typedef _RealType input_type;
   2335       typedef _RealType result_type;
   2336 
   2337     public:
   2338       /**
   2339        * Constructs a gamma distribution with parameters @f$ \alpha @f$.
   2340        */
   2341       explicit
   2342       gamma_distribution(const result_type& __alpha_val = result_type(1))
   2343       : _M_alpha(__alpha_val)
   2344       {
   2345 	_GLIBCXX_DEBUG_ASSERT(_M_alpha > 0);
   2346 	_M_initialize();
   2347       }
   2348 
   2349       /**
   2350        * Gets the @f$ \alpha @f$ of the distribution.
   2351        */
   2352       _RealType
   2353       alpha() const
   2354       { return _M_alpha; }
   2355 
   2356       /**
   2357        * Resets the distribution.
   2358        */
   2359       void
   2360       reset() { }
   2361 
   2362       template<class _UniformRandomNumberGenerator>
   2363         result_type
   2364         operator()(_UniformRandomNumberGenerator& __urng);
   2365 
   2366       /**
   2367        * Inserts a %gamma_distribution random number distribution
   2368        * @p __x into the output stream @p __os.
   2369        *
   2370        * @param __os An output stream.
   2371        * @param __x  A %gamma_distribution random number distribution.
   2372        *
   2373        * @returns The output stream with the state of @p __x inserted or in
   2374        * an error state.
   2375        */
   2376       template<typename _RealType1, typename _CharT, typename _Traits>
   2377         friend std::basic_ostream<_CharT, _Traits>&
   2378         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
   2379 		   const gamma_distribution<_RealType1>& __x);
   2380 
   2381       /**
   2382        * Extracts a %gamma_distribution random number distribution
   2383        * @p __x from the input stream @p __is.
   2384        *
   2385        * @param __is An input stream.
   2386        * @param __x  A %gamma_distribution random number generator engine.
   2387        *
   2388        * @returns The input stream with @p __x extracted or in an error state.
   2389        */
   2390       template<typename _CharT, typename _Traits>
   2391         friend std::basic_istream<_CharT, _Traits>&
   2392         operator>>(std::basic_istream<_CharT, _Traits>& __is,
   2393 		   gamma_distribution& __x)
   2394         {
   2395 	  __is >> __x._M_alpha;
   2396 	  __x._M_initialize();
   2397 	  return __is;
   2398 	}
   2399 
   2400     private:
   2401       void
   2402       _M_initialize();
   2403 
   2404       result_type _M_alpha;
   2405 
   2406       // Hosts either lambda of GB or d of modified Vaduva's.
   2407       result_type _M_l_d;
   2408     };
   2409 
   2410   /* @} */ // group tr1_random_distributions_continuous
   2411   /* @} */ // group tr1_random_distributions
   2412   /* @} */ // group tr1_random
   2413 _GLIBCXX_END_NAMESPACE_VERSION
   2414 }
   2415 }
   2416 
   2417 #endif // _GLIBCXX_TR1_RANDOM_H
   2418