# random

Go to the documentation of this file.

    00001 // random number generation -*- C++ -*-
    00002
    00003 // Copyright (C) 2006 Free Software Foundation, Inc.
    00004 //
    00005 // This file is part of the GNU ISO C++ Library.  This library is free
    00006 // software; you can redistribute it and/or modify it under the
    00007 // terms of the GNU General Public License as published by the
    00008 // Free Software Foundation; either version 2, or (at your option)
    00009 // any later version.
    00010
    00011 // This library is distributed in the hope that it will be useful,
    00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00014 // GNU General Public License for more details.
    00015
    00016 // You should have received a copy of the GNU General Public License along
    00017 // with this library; see the file COPYING.  If not, write to the Free
    00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00019 // USA.
    00020
    00021 // As a special exception, you may use this file as part of a free software
    00022 // library without restriction.  Specifically, if other files instantiate
    00023 // templates or use macros or inline functions from this file, or you compile
    00024 // this file and link it with other files to produce an executable, this
    00025 // file does not by itself cause the resulting executable to be covered by
    00026 // the GNU General Public License.  This exception does not however
    00027 // invalidate any other reasons why the executable file might be covered by
    00028 // the GNU General Public License.
    00029
    00030 /**
    00031  * @file tr1/random
    00032  * This is a TR1 C++ Library header.
    00033  */
    00034
    00035 #ifndef _TR1_RANDOM
    00036 #define _TR1_RANDOM 1
    00037
    00038 #include <cmath>
    00039 #include <cstdio>
    00040 #include <string>
    00041 #include <iosfwd>
    00042 #include <limits>
    00043 #include <tr1/type_traits>
    00044 #include <tr1/cmath>
    00045 #include <ext/type_traits.h>
    00046 #include <ext/numeric_traits.h>
    00047 #include <bits/concept_check.h>
    00048 #include <debug/debug.h>
    00049
    00050 namespace std
    00051 {
    00052 _GLIBCXX_BEGIN_NAMESPACE(tr1)
    00053
    00054   // [5.1] Random number generation
    00055
    00056   /**
    00057    * @addtogroup tr1_random Random Number Generation
    00058    * A facility for generating random numbers on selected distributions.
    00059    * @{
    00060    */
    00061
    00062   /*
    00063    * Implementation-space details.
    00064    */
    00065   namespace __detail
    00066   {
    00067     template<typename _UIntType, int __w,
    00068          bool = __w < std::numeric_limits<_UIntType>::digits>
    00069       struct _Shift
    00070       { static const _UIntType __value = 0; };
    00071
    00072     template<typename _UIntType, int __w>
    00073       struct _Shift<_UIntType, __w, true>
    00074       { static const _UIntType __value = _UIntType(1) << __w; };
    00075
    00076     template<typename _Tp, _Tp __a, _Tp __c, _Tp __m, bool>
    00077       struct _Mod;
    00078
    00079     // Dispatch based on modulus value to prevent divide-by-zero compile-time
    00080     // errors when m == 0.
    00081     template<typename _Tp, _Tp __a, _Tp __c, _Tp __m>
    00082       inline _Tp
    00083       __mod(_Tp __x)
    00084       { return _Mod<_Tp, __a, __c, __m, __m == 0>::__calc(__x); }
    00085
    00086     typedef __gnu_cxx::__conditional_type<(sizeof(unsigned) == 4),
    00087             unsigned, unsigned long>::__type _UInt32Type;
    00088
    00089     /*
    00090      * An adaptor class for converting the output of any Generator into
    00091      * the input for a specific Distribution.
    00092      */
    00093     template<typename _Engine, typename _Distribution>
    00094       struct _Adaptor
    00095       {
    00096     typedef typename _Engine::result_type        _Engine_result_type;
    00097     typedef typename _Distribution::input_type   result_type;
    00098
    00099       public:
    00100     _Adaptor(const _Engine& __g)
    00101     : _M_g(__g) { }
    00102
    00103     result_type
    00104     min() const
    00105     {
    00106       result_type __return_value = 0;
    00107       if (is_integral<_Engine_result_type>::value
    00108           && is_integral<result_type>::value)
    00109         __return_value = _M_g.min();
    00110       else if (!is_integral<result_type>::value)
    00111         __return_value = result_type(0);
    00112       return __return_value;
    00113     }
    00114
    00115     result_type
    00116     max() const
    00117     {
    00118       result_type __return_value = 0;
    00119       if (is_integral<_Engine_result_type>::value
    00120           && is_integral<result_type>::value)
    00121         __return_value = _M_g.max();
    00122       else if (!is_integral<result_type>::value)
    00123         __return_value = result_type(1);
    00124       return __return_value;
    00125     }
    00126
    00127     result_type
    00128     operator()();
    00129
    00130       private:
    00131     _Engine _M_g;
    00132       };
    00133
    00134     /*
    00135      * Converts a value generated by the adapted random number generator into a
    00136      * value in the input domain for the dependent random number distribution.
    00137      *
    00138      * Because the type traits are compile time constants only the appropriate
    00139      * clause of the if statements will actually be emitted by the compiler.
    00140      */
    00141     template<typename _Engine, typename _Distribution>
    00142       typename _Adaptor<_Engine, _Distribution>::result_type
    00143       _Adaptor<_Engine, _Distribution>::
    00144       operator()()
    00145       {
    00146     result_type __return_value = 0;
    00147     if (is_integral<_Engine_result_type>::value
    00148         && is_integral<result_type>::value)
    00149       __return_value = _M_g();
    00150         else if (is_integral<_Engine_result_type>::value
    00151          && !is_integral<result_type>::value)
    00152       __return_value = result_type(_M_g() - _M_g.min())
    00153         / result_type(_M_g.max() - _M_g.min() + result_type(1));
    00154     else if (!is_integral<_Engine_result_type>::value
    00155          && !is_integral<result_type>::value)
    00156       __return_value = result_type(_M_g() - _M_g.min())
    00157         / result_type(_M_g.max() - _M_g.min());
    00158         return __return_value;
    00159       }
    00160   } // namespace __detail
    00161
    00162   /**
    00163    * Produces random numbers on a given disribution function using a un uniform
    00164    * random number generation engine.
    00165    *
    00166    * @todo the engine_value_type needs to be studied more carefully.
    00167    */
    00168   template<typename _Engine, typename _Dist>
    00169     class variate_generator
    00170     {
    00171       // Concept requirements.
    00172       __glibcxx_class_requires(_Engine, _CopyConstructibleConcept)
    00173       //  __glibcxx_class_requires(_Engine, _EngineConcept)
    00174       //  __glibcxx_class_requires(_Dist, _EngineConcept)
    00175
    00176     public:
    00177       typedef _Engine                                engine_type;
    00178       typedef __detail::_Adaptor<_Engine, _Dist>     engine_value_type;
    00179       typedef _Dist                                  distribution_type;
    00180       typedef typename _Dist::result_type            result_type;
    00181
    00182       // tr1:5.1.1 table 5.1 requirement
    00183       typedef typename __gnu_cxx::__enable_if<
    00184     is_arithmetic<result_type>::value, result_type>::__type _IsValidType;
    00185
    00186       /**
    00187        * Constructs a variate generator with the uniform random number
    00188        * generator @p __eng for the random distribution @p __dist.
    00189        *
    00190        * @throws Any exceptions which may thrown by the copy constructors of
    00191        * the @p _Engine or @p _Dist objects.
    00192        */
    00193       variate_generator(engine_type __eng, distribution_type __dist)
    00194       : _M_engine(__eng), _M_dist(__dist) { }
    00195
    00196       /**
    00197        * Gets the next generated value on the distribution.
    00198        */
    00199       result_type
    00200       operator()()
    00201       { return _M_dist(_M_engine); }
    00202
    00203       /**
    00204        * WTF?
    00205        */
    00206       template<typename _Tp>
    00207         result_type
    00208         operator()(_Tp __value)
    00209         { return _M_dist(_M_engine, __value); }
    00210
    00211       /**
    00212        * Gets a reference to the underlying uniform random number generator
    00213        * object.
    00214        */
    00215       engine_value_type&
    00216       engine()
    00217       { return _M_engine; }
    00218
    00219       /**
    00220        * Gets a const reference to the underlying uniform random number
    00221        * generator object.
    00222        */
    00223       const engine_value_type&
    00224       engine() const
    00225       { return _M_engine; }
    00226
    00227       /**
    00228        * Gets a reference to the underlying random distribution.
    00229        */
    00230       distribution_type&
    00231       distribution()
    00232       { return _M_dist; }
    00233
    00234       /**
    00235        * Gets a const reference to the underlying random distribution.
    00236        */
    00237       const distribution_type&
    00238       distribution() const
    00239       { return _M_dist; }
    00240
    00241       /**
    00242        * Gets the closed lower bound of the distribution interval.
    00243        */
    00244       result_type
    00245       min() const
    00246       { return this->distribution().min(); }
    00247
    00248       /**
    00249        * Gets the closed upper bound of the distribution interval.
    00250        */
    00251       result_type
    00252       max() const
    00253       { return this->distribution().max(); }
    00254
    00255     private:
    00256       engine_value_type _M_engine;
    00257       distribution_type _M_dist;
    00258     };
    00259
    00260
    00261   /**
    00262    * @addtogroup tr1_random_generators Random Number Generators
    00263    * @ingroup tr1_random
    00264    *
    00265    * These classes define objects which provide random or pseudorandom
    00266    * numbers, either from a discrete or a continuous interval.  The
    00267    * random number generator supplied as a part of this library are
    00268    * all uniform random number generators which provide a sequence of
    00269    * random number uniformly distributed over their range.
    00270    *
    00271    * A number generator is a function object with an operator() that
    00272    * takes zero arguments and returns a number.
    00273    *
    00274    * A compliant random number generator must satisy the following
    00275    * requirements.  <table border=1 cellpadding=10 cellspacing=0>
    00276    * <caption align=top>Random Number Generator Requirements</caption>
    00277    * <tr><td>To be documented.</td></tr> </table>
    00278    *
    00279    * @{
    00280    */
    00281
    00282   /**
    00283    * @brief A model of a linear congruential random number generator.
    00284    *
    00285    * A random number generator that produces pseudorandom numbers using the
    00286    * linear function @f$x_{i+1}\leftarrow(ax_{i} + c) \bmod m @f$.
    00287    *
    00288    * The template parameter @p _UIntType must be an unsigned integral type
    00289    * large enough to store values up to (__m-1). If the template parameter
    00290    * @p __m is 0, the modulus @p __m used is
    00291    * std::numeric_limits<_UIntType>::max() plus 1. Otherwise, the template
    00292    * parameters @p __a and @p __c must be less than @p __m.
    00293    *
    00294    * The size of the state is @f$ 1 @f$.
    00295    */
    00296   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
    00297     class linear_congruential
    00298     {
    00299       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
    00300       //  __glibcpp_class_requires(__a < __m && __c < __m)
    00301
    00302     public:
    00303       /** The type of the generated random value. */
    00304       typedef _UIntType result_type;
    00305
    00306       /** The multiplier. */
    00307       static const _UIntType multiplier = __a;
    00308       /** An increment. */
    00309       static const _UIntType increment = __c;
    00310       /** The modulus. */
    00311       static const _UIntType modulus = __m;
    00312
    00313       /**
    00314        * Constructs a %linear_congruential random number generator engine with
    00315        * seed @p __s.  The default seed value is 1.
    00316        *
    00317        * @param __s The initial seed value.
    00318        */
    00319       explicit
    00320       linear_congruential(unsigned long __x0 = 1)
    00321       { this->seed(__x0); }
    00322
    00323       /**
    00324        * Constructs a %linear_congruential random number generator engine
    00325        * seeded from the generator function @p __g.
    00326        *
    00327        * @param __g The seed generator function.
    00328        */
    00329       template<class _Gen>
    00330         linear_congruential(_Gen& __g)
    00331         { this->seed(__g); }
    00332
    00333       /**
    00334        * Reseeds the %linear_congruential random number generator engine
    00335        * sequence to the seed @g __s.
    00336        *
    00337        * @param __s The new seed.
    00338        */
    00339       void
    00340       seed(unsigned long __s = 1);
    00341
    00342       /**
    00343        * Reseeds the %linear_congruential random number generator engine
    00344        * sequence using values from the generator function @p __g.
    00345        *
    00346        * @param __g the seed generator function.
    00347        */
    00348       template<class _Gen>
    00349         void
    00350         seed(_Gen& __g)
    00351         { seed(__g, typename is_fundamental<_Gen>::type()); }
    00352
    00353       /**
    00354        * Gets the smallest possible value in the output range.
    00355        *
    00356        * The minumum depends on the @p __c parameter: if it is zero, the
    00357        * minimum generated must be > 0, otherwise 0 is allowed.
    00358        */
    00359       result_type
    00360       min() const
    00361       { return (__detail::__mod<_UIntType, 1, 0, __m>(__c) == 0) ? 1 : 0; }
    00362
    00363       /**
    00364        * Gets the largest possible value in the output range.
    00365        */
    00366       result_type
    00367       max() const
    00368       { return __m - 1; }
    00369
    00370       /**
    00371        * Gets the next random number in the sequence.
    00372        */
    00373       result_type
    00374       operator()();
    00375
    00376       /**
    00377        * Compares two linear congruential random number generator
    00378        * objects of the same type for equality.
    00379        *
    00380        * @param __lhs A linear congruential random number generator object.
    00381        * @param __rhs Another linear congruential random number generator obj.
    00382        *
    00383        * @returns true if the two objects are equal, false otherwise.
    00384        */
    00385       friend bool
    00386       operator==(const linear_congruential& __lhs,
    00387          const linear_congruential& __rhs)
    00388       { return __lhs._M_x == __rhs._M_x; }
    00389
    00390       /**
    00391        * Compares two linear congruential random number generator
    00392        * objects of the same type for inequality.
    00393        *
    00394        * @param __lhs A linear congruential random number generator object.
    00395        * @param __rhs Another linear congruential random number generator obj.
    00396        *
    00397        * @returns true if the two objects are not equal, false otherwise.
    00398        */
    00399       friend bool
    00400       operator!=(const linear_congruential& __lhs,
    00401          const linear_congruential& __rhs)
    00402       { return !(__lhs == __rhs); }
    00403
    00404       /**
    00405        * Writes the textual representation of the state x(i) of x to @p __os.
    00406        *
    00407        * @param __os  The output stream.
    00408        * @param __lcr A % linear_congruential random number generator.
    00409        * @returns __os.
    00410        */
    00411       template<class _UIntType1, _UIntType1 __a1, _UIntType1 __c1,
    00412            _UIntType1 __m1,
    00413            typename _CharT, typename _Traits>
    00414         friend std::basic_ostream<_CharT, _Traits>&
    00415         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    00416            const linear_congruential<_UIntType1, __a1, __c1,
    00417            __m1>& __lcr);
    00418
    00419       /**
    00420        * Sets the state of the engine by reading its textual
    00421        * representation from @p __is.
    00422        *
    00423        * The textual representation must have been previously written using an
    00424        * output stream whose imbued locale and whose type's template
    00425        * specialization arguments _CharT and _Traits were the same as those of
    00426        * @p __is.
    00427        *
    00428        * @param __is  The input stream.
    00429        * @param __lcr A % linear_congruential random number generator.
    00430        * @returns __is.
    00431        */
    00432       template<class _UIntType1, _UIntType1 __a1, _UIntType1 __c1,
    00433            _UIntType1 __m1,
    00434            typename _CharT, typename _Traits>
    00435         friend std::basic_istream<_CharT, _Traits>&
    00436         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    00437            linear_congruential<_UIntType1, __a1, __c1, __m1>& __lcr);
    00438
    00439     private:
    00440       template<class _Gen>
    00441         void
    00442         seed(_Gen& __g, true_type)
    00443         { return seed(static_cast<unsigned long>(__g)); }
    00444
    00445       template<class _Gen>
    00446         void
    00447         seed(_Gen& __g, false_type);
    00448
    00449       _UIntType _M_x;
    00450     };
    00451
    00452   /**
    00453    * The classic Minimum Standard rand0 of Lewis, Goodman, and Miller.
    00454    */
    00455   typedef linear_congruential<unsigned long, 16807, 0, 2147483647> minstd_rand0;
    00456
    00457   /**
    00458    * An alternative LCR (Lehmer Generator function) .
    00459    */
    00460   typedef linear_congruential<unsigned long, 48271, 0, 2147483647> minstd_rand;
    00461
    00462
    00463   /**
    00464    * A generalized feedback shift register discrete random number generator.
    00465    *
    00466    * This algorithm avoind multiplication and division and is designed to be
    00467    * friendly to a pipelined architecture.  If the parameters are chosen
    00468    * correctly, this generator will produce numbers with a very long period and
    00469    * fairly good apparent entropy, although still not cryptographically strong.
    00470    *
    00471    * The best way to use this generator is with the predefined mt19937 class.
    00472    *
    00473    * This algorithm was originally invented by Makoto Matsumoto and
    00474    * Takuji Nishimura.
    00475    *
    00476    * @var word_size   The number of bits in each element of the state vector.
    00477    * @var state_size  The degree of recursion.
    00478    * @var shift_size  The period parameter.
    00479    * @var mask_bits   The separation point bit index.
    00480    * @var parameter_a The last row of the twist matrix.
    00481    * @var output_u    The first right-shift tempering matrix parameter.
    00482    * @var output_s    The first left-shift tempering matrix parameter.
    00483    * @var output_b    The first left-shift tempering matrix mask.
    00484    * @var output_t    The second left-shift tempering matrix parameter.
    00485    * @var output_c    The second left-shift tempering matrix mask.
    00486    * @var output_l    The second right-shift tempering matrix parameter.
    00487    */
    00488   template<class _UIntType, int __w, int __n, int __m, int __r,
    00489        _UIntType __a, int __u, int __s, _UIntType __b, int __t,
    00490        _UIntType __c, int __l>
    00491     class mersenne_twister
    00492     {
    00493       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
    00494
    00495     public:
    00496       // types
    00497       typedef _UIntType result_type;
    00498
    00499       // parameter values
    00500       static const int       word_size   = __w;
    00501       static const int       state_size  = __n;
    00502       static const int       shift_size  = __m;
    00503       static const int       mask_bits   = __r;
    00504       static const _UIntType parameter_a = __a;
    00505       static const int       output_u    = __u;
    00506       static const int       output_s    = __s;
    00507       static const _UIntType output_b    = __b;
    00508       static const int       output_t    = __t;
    00509       static const _UIntType output_c    = __c;
    00510       static const int       output_l    = __l;
    00511
    00512       // constructors and member function
    00513       mersenne_twister()
    00514       { seed(); }
    00515
    00516       explicit
    00517       mersenne_twister(unsigned long __value)
    00518       { seed(__value); }
    00519
    00520       template<class _Gen>
    00521         mersenne_twister(_Gen& __g)
    00522         { seed(__g); }
    00523
    00524       void
    00525       seed()
    00526       { seed(5489UL); }
    00527
    00528       void
    00529       seed(unsigned long __value);
    00530
    00531       template<class _Gen>
    00532         void
    00533         seed(_Gen& __g)
    00534         { seed(__g, typename is_fundamental<_Gen>::type()); }
    00535
    00536       result_type
    00537       min() const
    00538       { return 0; };
    00539
    00540       result_type
    00541       max() const
    00542       { return __detail::_Shift<_UIntType, __w>::__value - 1; }
    00543
    00544       result_type
    00545       operator()();
    00546
    00547       /**
    00548        * Compares two % mersenne_twister random number generator objects of
    00549        * the same type for equality.
    00550        *
    00551        * @param __lhs A % mersenne_twister random number generator object.
    00552        * @param __rhs Another % mersenne_twister random number generator
    00553        *              object.
    00554        *
    00555        * @returns true if the two objects are equal, false otherwise.
    00556        */
    00557       friend bool
    00558       operator==(const mersenne_twister& __lhs,
    00559          const mersenne_twister& __rhs)
    00560       { return std::equal(__lhs._M_x, __lhs._M_x + state_size, __rhs._M_x); }
    00561
    00562       /**
    00563        * Compares two % mersenne_twister random number generator objects of
    00564        * the same type for inequality.
    00565        *
    00566        * @param __lhs A % mersenne_twister random number generator object.
    00567        * @param __rhs Another % mersenne_twister random number generator
    00568        *              object.
    00569        *
    00570        * @returns true if the two objects are not equal, false otherwise.
    00571        */
    00572       friend bool
    00573       operator!=(const mersenne_twister& __lhs,
    00574          const mersenne_twister& __rhs)
    00575       { return !(__lhs == __rhs); }
    00576
    00577       /**
    00578        * Inserts the current state of a % mersenne_twister random number
    00579        * generator engine @p __x into the output stream @p __os.
    00580        *
    00581        * @param __os An output stream.
    00582        * @param __x  A % mersenne_twister random number generator engine.
    00583        *
    00584        * @returns The output stream with the state of @p __x inserted or in
    00585        * an error state.
    00586        */
    00587       template<class _UIntType1, int __w1, int __n1, int __m1, int __r1,
    00588            _UIntType1 __a1, int __u1, int __s1, _UIntType1 __b1, int __t1,
    00589            _UIntType1 __c1, int __l1,
    00590            typename _CharT, typename _Traits>
    00591         friend std::basic_ostream<_CharT, _Traits>&
    00592         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    00593            const mersenne_twister<_UIntType1, __w1, __n1, __m1, __r1,
    00594            __a1, __u1, __s1, __b1, __t1, __c1, __l1>& __x);
    00595
    00596       /**
    00597        * Extracts the current state of a % mersenne_twister random number
    00598        * generator engine @p __x from the input stream @p __is.
    00599        *
    00600        * @param __is An input stream.
    00601        * @param __x  A % mersenne_twister random number generator engine.
    00602        *
    00603        * @returns The input stream with the state of @p __x extracted or in
    00604        * an error state.
    00605        */
    00606       template<class _UIntType1, int __w1, int __n1, int __m1, int __r1,
    00607            _UIntType1 __a1, int __u1, int __s1, _UIntType1 __b1, int __t1,
    00608            _UIntType1 __c1, int __l1,
    00609            typename _CharT, typename _Traits>
    00610         friend std::basic_istream<_CharT, _Traits>&
    00611         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    00612            mersenne_twister<_UIntType1, __w1, __n1, __m1, __r1,
    00613            __a1, __u1, __s1, __b1, __t1, __c1, __l1>& __x);
    00614
    00615     private:
    00616       template<class _Gen>
    00617         void
    00618         seed(_Gen& __g, true_type)
    00619         { return seed(static_cast<unsigned long>(__g)); }
    00620
    00621       template<class _Gen>
    00622         void
    00623         seed(_Gen& __g, false_type);
    00624
    00625       _UIntType _M_x[state_size];
    00626       int       _M_p;
    00627     };
    00628
    00629   /**
    00630    * The classic Mersenne Twister.
    00631    *
    00632    * Reference:
    00633    * M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
    00634    * Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions
    00635    * on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
    00636    */
    00637   typedef mersenne_twister<
    00638     unsigned long, 32, 624, 397, 31,
    00639     0x9908b0dful, 11, 7,
    00640     0x9d2c5680ul, 15,
    00641     0xefc60000ul, 18
    00642     > mt19937;
    00643
    00644
    00645   /**
    00646    * @brief The Marsaglia-Zaman generator.
    00647    *
    00648    * This is a model of a Generalized Fibonacci discrete random number
    00649    * generator, sometimes referred to as the SWC generator.
    00650    *
    00651    * A discrete random number generator that produces pseudorandom
    00652    * numbers using @f$x_{i}\leftarrow(x_{i - s} - x_{i - r} -
    00653    * carry_{i-1}) \bmod m @f$.
    00654    *
    00655    * The size of the state is @f$ r @f$
    00656    * and the maximum period of the generator is @f$ m^r - m^s -1 @f$.
    00657    *
    00658    * N1688[4.13] says "the template parameter _IntType shall denote an integral
    00659    * type large enough to store values up to m."
    00660    *
    00661    * @if maint
    00662    * @var _M_x     The state of the generator.  This is a ring buffer.
    00663    * @var _M_carry The carry.
    00664    * @var _M_p     Current index of x(i - r).
    00665    * @endif
    00666    */
    00667   template<typename _IntType, _IntType __m, int __s, int __r>
    00668     class subtract_with_carry
    00669     {
    00670       __glibcxx_class_requires(_IntType, _IntegerConcept)
    00671
    00672     public:
    00673       /** The type of the generated random value. */
    00674       typedef _IntType result_type;
    00675
    00676       // parameter values
    00677       static const _IntType modulus   = __m;
    00678       static const int      long_lag  = __r;
    00679       static const int      short_lag = __s;
    00680
    00681       /**
    00682        * Constructs a default-initialized % subtract_with_carry random number
    00683        * generator.
    00684        */
    00685       subtract_with_carry()
    00686       { this->seed(); }
    00687
    00688       /**
    00689        * Constructs an explicitly seeded % subtract_with_carry random number
    00690        * generator.
    00691        */
    00692       explicit
    00693       subtract_with_carry(unsigned long __value)
    00694       { this->seed(__value); }
    00695
    00696       /**
    00697        * Constructs a %subtract_with_carry random number generator engine
    00698        * seeded from the generator function @p __g.
    00699        *
    00700        * @param __g The seed generator function.
    00701        */
    00702       template<class _Gen>
    00703         subtract_with_carry(_Gen& __g)
    00704         { this->seed(__g); }
    00705
    00706       /**
    00707        * Seeds the initial state @f$ x_0 @f$ of the random number generator.
    00708        *
    00709        * N1688[4.19] modifies this as follows.  If @p __value == 0,
    00710        * sets value to 19780503.  In any case, with a linear
    00711        * congruential generator lcg(i) having parameters @f$ m_{lcg} =
    00712        * 2147483563, a_{lcg} = 40014, c_{lcg} = 0, and lcg(0) = value
    00713        * @f$, sets @f$ x_{-r} \dots x_{-1} @f$ to @f$ lcg(1) \bmod m
    00714        * \dots lcg(r) \bmod m @f$ respectively.  If @f$ x_{-1} = 0 @f$
    00715        * set carry to 1, otherwise sets carry to 0.
    00716        */
    00717       void
    00718       seed(unsigned long __value = 19780503);
    00719
    00720       /**
    00721        * Seeds the initial state @f$ x_0 @f$ of the % subtract_with_carry
    00722        * random number generator.
    00723        */
    00724       template<class _Gen>
    00725         void
    00726         seed(_Gen& __g)
    00727         { seed(__g, typename is_fundamental<_Gen>::type()); }
    00728
    00729       /**
    00730        * Gets the inclusive minimum value of the range of random integers
    00731        * returned by this generator.
    00732        */
    00733       result_type
    00734       min() const
    00735       { return 0; }
    00736
    00737       /**
    00738        * Gets the inclusive maximum value of the range of random integers
    00739        * returned by this generator.
    00740        */
    00741       result_type
    00742       max() const
    00743       { return this->modulus - 1; }
    00744
    00745       /**
    00746        * Gets the next random number in the sequence.
    00747        */
    00748       result_type
    00749       operator()();
    00750
    00751       /**
    00752        * Compares two % subtract_with_carry random number generator objects of
    00753        * the same type for equality.
    00754        *
    00755        * @param __lhs A % subtract_with_carry random number generator object.
    00756        * @param __rhs Another % subtract_with_carry random number generator
    00757        *              object.
    00758        *
    00759        * @returns true if the two objects are equal, false otherwise.
    00760        */
    00761       friend bool
    00762       operator==(const subtract_with_carry& __lhs,
    00763          const subtract_with_carry& __rhs)
    00764       { return std::equal(__lhs._M_x, __lhs._M_x + long_lag, __rhs._M_x); }
    00765
    00766       /**
    00767        * Compares two % subtract_with_carry random number generator objects of
    00768        * the same type for inequality.
    00769        *
    00770        * @param __lhs A % subtract_with_carry random number generator object.
    00771        * @param __rhs Another % subtract_with_carry random number generator
    00772        *              object.
    00773        *
    00774        * @returns true if the two objects are not equal, false otherwise.
    00775        */
    00776       friend bool
    00777       operator!=(const subtract_with_carry& __lhs,
    00778          const subtract_with_carry& __rhs)
    00779       { return !(__lhs == __rhs); }
    00780
    00781       /**
    00782        * Inserts the current state of a % subtract_with_carry random number
    00783        * generator engine @p __x into the output stream @p __os.
    00784        *
    00785        * @param __os An output stream.
    00786        * @param __x  A % subtract_with_carry random number generator engine.
    00787        *
    00788        * @returns The output stream with the state of @p __x inserted or in
    00789        * an error state.
    00790        */
    00791       template<typename _IntType1, _IntType1 __m1, int __s1, int __r1,
    00792            typename _CharT, typename _Traits>
    00793         friend std::basic_ostream<_CharT, _Traits>&
    00794         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    00795            const subtract_with_carry<_IntType1, __m1, __s1,
    00796            __r1>& __x);
    00797
    00798       /**
    00799        * Extracts the current state of a % subtract_with_carry random number
    00800        * generator engine @p __x from the input stream @p __is.
    00801        *
    00802        * @param __is An input stream.
    00803        * @param __x  A % subtract_with_carry random number generator engine.
    00804        *
    00805        * @returns The input stream with the state of @p __x extracted or in
    00806        * an error state.
    00807        */
    00808       template<typename _IntType1, _IntType1 __m1, int __s1, int __r1,
    00809            typename _CharT, typename _Traits>
    00810         friend std::basic_istream<_CharT, _Traits>&
    00811         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    00812            subtract_with_carry<_IntType1, __m1, __s1, __r1>& __x);
    00813
    00814     private:
    00815       template<class _Gen>
    00816         void
    00817         seed(_Gen& __g, true_type)
    00818         { return seed(static_cast<unsigned long>(__g)); }
    00819
    00820       template<class _Gen>
    00821         void
    00822         seed(_Gen& __g, false_type);
    00823
    00824       typedef typename __gnu_cxx::__add_unsigned<_IntType>::__type _UIntType;
    00825
    00826       _UIntType  _M_x[long_lag];
    00827       _UIntType  _M_carry;
    00828       int        _M_p;
    00829     };
    00830
    00831
    00832   /**
    00833    * @brief The Marsaglia-Zaman generator (floats version).
    00834    *
    00835    * @if maint
    00836    * @var _M_x     The state of the generator.  This is a ring buffer.
    00837    * @var _M_carry The carry.
    00838    * @var _M_p     Current index of x(i - r).
    00839    * @var _M_npows Precomputed negative powers of 2.
    00840    * @endif
    00841    */
    00842   template<typename _RealType, int __w, int __s, int __r>
    00843     class subtract_with_carry_01
    00844     {
    00845     public:
    00846       /** The type of the generated random value. */
    00847       typedef _RealType result_type;
    00848
    00849       // parameter values
    00850       static const int      word_size = __w;
    00851       static const int      long_lag  = __r;
    00852       static const int      short_lag = __s;
    00853
    00854       /**
    00855        * Constructs a default-initialized % subtract_with_carry_01 random
    00856        * number generator.
    00857        */
    00858       subtract_with_carry_01()
    00859       {
    00860     this->seed();
    00861     _M_initialize_npows();
    00862       }
    00863
    00864       /**
    00865        * Constructs an explicitly seeded % subtract_with_carry_01 random number
    00866        * generator.
    00867        */
    00868       explicit
    00869       subtract_with_carry_01(unsigned long __value)
    00870       {
    00871     this->seed(__value);
    00872     _M_initialize_npows();
    00873       }
    00874
    00875       /**
    00876        * Constructs a % subtract_with_carry_01 random number generator engine
    00877        * seeded from the generator function @p __g.
    00878        *
    00879        * @param __g The seed generator function.
    00880        */
    00881       template<class _Gen>
    00882         subtract_with_carry_01(_Gen& __g)
    00883         {
    00884       this->seed(__g);
    00885       _M_initialize_npows();
    00886     }
    00887
    00888       /**
    00889        * Seeds the initial state @f$ x_0 @f$ of the random number generator.
    00890        */
    00891       void
    00892       seed(unsigned long __value = 19780503);
    00893
    00894       /**
    00895        * Seeds the initial state @f$ x_0 @f$ of the % subtract_with_carry_01
    00896        * random number generator.
    00897        */
    00898       template<class _Gen>
    00899         void
    00900         seed(_Gen& __g)
    00901         { seed(__g, typename is_fundamental<_Gen>::type()); }
    00902
    00903       /**
    00904        * Gets the minimum value of the range of random floats
    00905        * returned by this generator.
    00906        */
    00907       result_type
    00908       min() const
    00909       { return 0.0; }
    00910
    00911       /**
    00912        * Gets the maximum value of the range of random floats
    00913        * returned by this generator.
    00914        */
    00915       result_type
    00916       max() const
    00917       { return 1.0; }
    00918
    00919       /**
    00920        * Gets the next random number in the sequence.
    00921        */
    00922       result_type
    00923       operator()();
    00924
    00925       /**
    00926        * Compares two % subtract_with_carry_01 random number generator objects
    00927        * of the same type for equality.
    00928        *
    00929        * @param __lhs A % subtract_with_carry_01 random number
    00930        *              generator object.
    00931        * @param __rhs Another % subtract_with_carry_01 random number generator
    00932        *              object.
    00933        *
    00934        * @returns true if the two objects are equal, false otherwise.
    00935        */
    00936       friend bool
    00937       operator==(const subtract_with_carry_01& __lhs,
    00938          const subtract_with_carry_01& __rhs)
    00939       {
    00940     for (int __i = 0; __i < long_lag; ++__i)
    00941       if (!std::equal(__lhs._M_x[__i], __lhs._M_x[__i] + __n,
    00942               __rhs._M_x[__i]))
    00943         return false;
    00944     return true;
    00945       }
    00946
    00947       /**
    00948        * Compares two % subtract_with_carry_01 random number generator objects
    00949        * of the same type for inequality.
    00950        *
    00951        * @param __lhs A % subtract_with_carry_01 random number
    00952        *              generator object.
    00953        *
    00954        * @param __rhs Another % subtract_with_carry_01 random number generator
    00955        *              object.
    00956        *
    00957        * @returns true if the two objects are not equal, false otherwise.
    00958        */
    00959       friend bool
    00960       operator!=(const subtract_with_carry_01& __lhs,
    00961          const subtract_with_carry_01& __rhs)
    00962       { return !(__lhs == __rhs); }
    00963
    00964       /**
    00965        * Inserts the current state of a % subtract_with_carry_01 random number
    00966        * generator engine @p __x into the output stream @p __os.
    00967        *
    00968        * @param __os An output stream.
    00969        * @param __x  A % subtract_with_carry_01 random number generator engine.
    00970        *
    00971        * @returns The output stream with the state of @p __x inserted or in
    00972        * an error state.
    00973        */
    00974       template<typename _RealType1, int __w1, int __s1, int __r1,
    00975            typename _CharT, typename _Traits>
    00976         friend std::basic_ostream<_CharT, _Traits>&
    00977         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    00978            const subtract_with_carry_01<_RealType1, __w1, __s1,
    00979            __r1>& __x);
    00980
    00981       /**
    00982        * Extracts the current state of a % subtract_with_carry_01 random number
    00983        * generator engine @p __x from the input stream @p __is.
    00984        *
    00985        * @param __is An input stream.
    00986        * @param __x  A % subtract_with_carry_01 random number generator engine.
    00987        *
    00988        * @returns The input stream with the state of @p __x extracted or in
    00989        * an error state.
    00990        */
    00991       template<typename _RealType1, int __w1, int __s1, int __r1,
    00992            typename _CharT, typename _Traits>
    00993         friend std::basic_istream<_CharT, _Traits>&
    00994         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    00995            subtract_with_carry_01<_RealType1, __w1, __s1, __r1>& __x);
    00996
    00997     private:
    00998       template<class _Gen>
    00999         void
    01000         seed(_Gen& __g, true_type)
    01001         { return seed(static_cast<unsigned long>(__g)); }
    01002
    01003       template<class _Gen>
    01004         void
    01005         seed(_Gen& __g, false_type);
    01006
    01007       void
    01008       _M_initialize_npows();
    01009
    01010       static const int __n = (__w + 31) / 32;
    01011
    01012       typedef __detail::_UInt32Type _UInt32Type;
    01013       _UInt32Type  _M_x[long_lag][__n];
    01014       _RealType    _M_npows[__n];
    01015       _UInt32Type  _M_carry;
    01016       int          _M_p;
    01017     };
    01018
    01019   typedef subtract_with_carry_01<float, 24, 10, 24>   ranlux_base_01;
    01020
    01021   // _GLIBCXX_RESOLVE_LIB_DEFECTS
    01022   // 508. Bad parameters for ranlux64_base_01.
    01023   typedef subtract_with_carry_01<double, 48, 5, 12> ranlux64_base_01;
    01024
    01025
    01026   /**
    01027    * Produces random numbers from some base engine by discarding blocks of
    01028    * data.
    01029    *
    01030    * 0 <= @p __r <= @p __p
    01031    */
    01032   template<class _UniformRandomNumberGenerator, int __p, int __r>
    01033     class discard_block
    01034     {
    01035       // __glibcxx_class_requires(typename base_type::result_type,
    01036       //                          ArithmeticTypeConcept)
    01037
    01038     public:
    01039       /** The type of the underlying generator engine. */
    01040       typedef _UniformRandomNumberGenerator   base_type;
    01041       /** The type of the generated random value. */
    01042       typedef typename base_type::result_type result_type;
    01043
    01044       // parameter values
    01045       static const int block_size = __p;
    01046       static const int used_block = __r;
    01047
    01048       /**
    01049        * Constructs a default %discard_block engine.
    01050        *
    01051        * The underlying engine is default constructed as well.
    01052        */
    01053       discard_block()
    01054       : _M_n(0) { }
    01055
    01056       /**
    01057        * Copy constructs a %discard_block engine.
    01058        *
    01059        * Copies an existing base class random number geenerator.
    01060        * @param rng An existing (base class) engine object.
    01061        */
    01062       explicit
    01063       discard_block(const base_type& __rng)
    01064       : _M_b(__rng), _M_n(0) { }
    01065
    01066       /**
    01067        * Seed constructs a %discard_block engine.
    01068        *
    01069        * Constructs the underlying generator engine seeded with @p __s.
    01070        * @param __s A seed value for the base class engine.
    01071        */
    01072       explicit
    01073       discard_block(unsigned long __s)
    01074       : _M_b(__s), _M_n(0) { }
    01075
    01076       /**
    01077        * Generator construct a %discard_block engine.
    01078        *
    01079        * @param __g A seed generator function.
    01080        */
    01081       template<class _Gen>
    01082         discard_block(_Gen& __g)
    01083     : _M_b(__g), _M_n(0) { }
    01084
    01085       /**
    01086        * Reseeds the %discard_block object with the default seed for the
    01087        * underlying base class generator engine.
    01088        */
    01089       void seed()
    01090       {
    01091     _M_b.seed();
    01092     _M_n = 0;
    01093       }
    01094
    01095       /**
    01096        * Reseeds the %discard_block object with the given seed generator
    01097        * function.
    01098        * @param __g A seed generator function.
    01099        */
    01100       template<class _Gen>
    01101         void seed(_Gen& __g)
    01102         {
    01103       _M_b.seed(__g);
    01104       _M_n = 0;
    01105     }
    01106
    01107       /**
    01108        * Gets a const reference to the underlying generator engine object.
    01109        */
    01110       const base_type&
    01111       base() const
    01112       { return _M_b; }
    01113
    01114       /**
    01115        * Gets the minimum value in the generated random number range.
    01116        */
    01117       result_type
    01118       min() const
    01119       { return _M_b.min(); }
    01120
    01121       /**
    01122        * Gets the maximum value in the generated random number range.
    01123        */
    01124       result_type
    01125       max() const
    01126       { return _M_b.max(); }
    01127
    01128       /**
    01129        * Gets the next value in the generated random number sequence.
    01130        */
    01131       result_type
    01132       operator()();
    01133
    01134       /**
    01135        * Compares two %discard_block random number generator objects of
    01136        * the same type for equality.
    01137        *
    01138        * @param __lhs A %discard_block random number generator object.
    01139        * @param __rhs Another %discard_block random number generator
    01140        *              object.
    01141        *
    01142        * @returns true if the two objects are equal, false otherwise.
    01143        */
    01144       friend bool
    01145       operator==(const discard_block& __lhs, const discard_block& __rhs)
    01146       { return (__lhs._M_b == __rhs._M_b) && (__lhs._M_n == __rhs._M_n); }
    01147
    01148       /**
    01149        * Compares two %discard_block random number generator objects of
    01150        * the same type for inequality.
    01151        *
    01152        * @param __lhs A %discard_block random number generator object.
    01153        * @param __rhs Another %discard_block random number generator
    01154        *              object.
    01155        *
    01156        * @returns true if the two objects are not equal, false otherwise.
    01157        */
    01158       friend bool
    01159       operator!=(const discard_block& __lhs, const discard_block& __rhs)
    01160       { return !(__lhs == __rhs); }
    01161
    01162       /**
    01163        * Inserts the current state of a %discard_block random number
    01164        * generator engine @p __x into the output stream @p __os.
    01165        *
    01166        * @param __os An output stream.
    01167        * @param __x  A %discard_block random number generator engine.
    01168        *
    01169        * @returns The output stream with the state of @p __x inserted or in
    01170        * an error state.
    01171        */
    01172       template<class _UniformRandomNumberGenerator1, int __p1, int __r1,
    01173            typename _CharT, typename _Traits>
    01174         friend std::basic_ostream<_CharT, _Traits>&
    01175         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    01176            const discard_block<_UniformRandomNumberGenerator1,
    01177            __p1, __r1>& __x);
    01178
    01179       /**
    01180        * Extracts the current state of a % subtract_with_carry random number
    01181        * generator engine @p __x from the input stream @p __is.
    01182        *
    01183        * @param __is An input stream.
    01184        * @param __x  A %discard_block random number generator engine.
    01185        *
    01186        * @returns The input stream with the state of @p __x extracted or in
    01187        * an error state.
    01188        */
    01189       template<class _UniformRandomNumberGenerator1, int __p1, int __r1,
    01190            typename _CharT, typename _Traits>
    01191         friend std::basic_istream<_CharT, _Traits>&
    01192         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    01193            discard_block<_UniformRandomNumberGenerator1,
    01194            __p1, __r1>& __x);
    01195
    01196     private:
    01197       base_type _M_b;
    01198       int       _M_n;
    01199     };
    01200
    01201
    01202   /**
    01203    * James's luxury-level-3 integer adaptation of Luescher's generator.
    01204    */
    01205   typedef discard_block<
    01206     subtract_with_carry<unsigned long, (1UL << 24), 10, 24>,
    01207       223,
    01208       24
    01209       > ranlux3;
    01210
    01211   /**
    01212    * James's luxury-level-4 integer adaptation of Luescher's generator.
    01213    */
    01214   typedef discard_block<
    01215     subtract_with_carry<unsigned long, (1UL << 24), 10, 24>,
    01216       389,
    01217       24
    01218       > ranlux4;
    01219
    01220   typedef discard_block<
    01221     subtract_with_carry_01<float, 24, 10, 24>,
    01222       223,
    01223       24
    01224       > ranlux3_01;
    01225
    01226   typedef discard_block<
    01227     subtract_with_carry_01<float, 24, 10, 24>,
    01228       389,
    01229       24
    01230       > ranlux4_01;
    01231
    01232
    01233   /**
    01234    * A random number generator adaptor class that combines two random number
    01235    * generator engines into a single output sequence.
    01236    */
    01237   template<class _UniformRandomNumberGenerator1, int __s1,
    01238        class _UniformRandomNumberGenerator2, int __s2>
    01239     class xor_combine
    01240     {
    01241       // __glibcxx_class_requires(typename _UniformRandomNumberGenerator1::
    01242       //                          result_type, ArithmeticTypeConcept)
    01243       // __glibcxx_class_requires(typename _UniformRandomNumberGenerator2::
    01244       //                          result_type, ArithmeticTypeConcept)
    01245
    01246     public:
    01247       /** The type of the the first underlying generator engine. */
    01248       typedef _UniformRandomNumberGenerator1   base1_type;
    01249       /** The type of the the second underlying generator engine. */
    01250       typedef _UniformRandomNumberGenerator2   base2_type;
    01251
    01252     private:
    01253       typedef typename base1_type::result_type _Result_type1;
    01254       typedef typename base2_type::result_type _Result_type2;
    01255
    01256     public:
    01257       /** The type of the generated random value. */
    01258       typedef typename __gnu_cxx::__conditional_type<(sizeof(_Result_type1)
    01259                               > sizeof(_Result_type2)),
    01260     _Result_type1, _Result_type2>::__type result_type;
    01261
    01262       // parameter values
    01263       static const int shift1 = __s1;
    01264       static const int shift2 = __s2;
    01265
    01266       // constructors and member function
    01267       xor_combine()
    01268       : _M_b1(), _M_b2()
    01269       { _M_initialize_max(); }
    01270
    01271       xor_combine(const base1_type& __rng1, const base2_type& __rng2)
    01272       : _M_b1(__rng1), _M_b2(__rng2)
    01273       { _M_initialize_max(); }
    01274
    01275       xor_combine(unsigned long __s)
    01276       : _M_b1(__s), _M_b2(__s + 1)
    01277       { _M_initialize_max(); }
    01278
    01279       template<class _Gen>
    01280         xor_combine(_Gen& __g)
    01281     : _M_b1(__g), _M_b2(__g)
    01282         { _M_initialize_max(); }
    01283
    01284       void
    01285       seed()
    01286       {
    01287     _M_b1.seed();
    01288     _M_b2.seed();
    01289       }
    01290
    01291       template<class _Gen>
    01292         void
    01293         seed(_Gen& __g)
    01294         {
    01295       _M_b1.seed(__g);
    01296       _M_b2.seed(__g);
    01297     }
    01298
    01299       const base1_type&
    01300       base1() const
    01301       { return _M_b1; }
    01302
    01303       const base2_type&
    01304       base2() const
    01305       { return _M_b2; }
    01306
    01307       result_type
    01308       min() const
    01309       { return 0; }
    01310
    01311       result_type
    01312       max() const
    01313       { return _M_max; }
    01314
    01315       /**
    01316        * Gets the next random number in the sequence.
    01317        */
    01318       // NB: Not exactly the TR1 formula, per N2079 instead.
    01319       result_type
    01320       operator()()
    01321       {
    01322     return ((result_type(_M_b1() - _M_b1.min()) << shift1)
    01323         ^ (result_type(_M_b2() - _M_b2.min()) << shift2));
    01324       }
    01325
    01326       /**
    01327        * Compares two %xor_combine random number generator objects of
    01328        * the same type for equality.
    01329        *
    01330        * @param __lhs A %xor_combine random number generator object.
    01331        * @param __rhs Another %xor_combine random number generator
    01332        *              object.
    01333        *
    01334        * @returns true if the two objects are equal, false otherwise.
    01335        */
    01336       friend bool
    01337       operator==(const xor_combine& __lhs, const xor_combine& __rhs)
    01338       {
    01339     return (__lhs.base1() == __rhs.base1())
    01340             && (__lhs.base2() == __rhs.base2());
    01341       }
    01342
    01343       /**
    01344        * Compares two %xor_combine random number generator objects of
    01345        * the same type for inequality.
    01346        *
    01347        * @param __lhs A %xor_combine random number generator object.
    01348        * @param __rhs Another %xor_combine random number generator
    01349        *              object.
    01350        *
    01351        * @returns true if the two objects are not equal, false otherwise.
    01352        */
    01353       friend bool
    01354       operator!=(const xor_combine& __lhs, const xor_combine& __rhs)
    01355       { return !(__lhs == __rhs); }
    01356
    01357       /**
    01358        * Inserts the current state of a %xor_combine random number
    01359        * generator engine @p __x into the output stream @p __os.
    01360        *
    01361        * @param __os An output stream.
    01362        * @param __x  A %xor_combine random number generator engine.
    01363        *
    01364        * @returns The output stream with the state of @p __x inserted or in
    01365        * an error state.
    01366        */
    01367       template<class _UniformRandomNumberGenerator11, int __s11,
    01368            class _UniformRandomNumberGenerator21, int __s21,
    01369            typename _CharT, typename _Traits>
    01370         friend std::basic_ostream<_CharT, _Traits>&
    01371         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    01372            const xor_combine<_UniformRandomNumberGenerator11, __s11,
    01373            _UniformRandomNumberGenerator21, __s21>& __x);
    01374
    01375       /**
    01376        * Extracts the current state of a %xor_combine random number
    01377        * generator engine @p __x from the input stream @p __is.
    01378        *
    01379        * @param __is An input stream.
    01380        * @param __x  A %xor_combine random number generator engine.
    01381        *
    01382        * @returns The input stream with the state of @p __x extracted or in
    01383        * an error state.
    01384        */
    01385       template<class _UniformRandomNumberGenerator11, int __s11,
    01386            class _UniformRandomNumberGenerator21, int __s21,
    01387            typename _CharT, typename _Traits>
    01388         friend std::basic_istream<_CharT, _Traits>&
    01389         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    01390            xor_combine<_UniformRandomNumberGenerator11, __s11,
    01391            _UniformRandomNumberGenerator21, __s21>& __x);
    01392
    01393     private:
    01394       void
    01395       _M_initialize_max();
    01396
    01397       result_type
    01398       _M_initialize_max_aux(result_type, result_type, int);
    01399
    01400       base1_type  _M_b1;
    01401       base2_type  _M_b2;
    01402       result_type _M_max;
    01403     };
    01404
    01405
    01406   /**
    01407    * A standard interface to a platform-specific non-deterministic
    01408    * random number generator (if any are available).
    01409    */
    01410   class random_device
    01411   {
    01412   public:
    01413     // types
    01414     typedef unsigned int result_type;
    01415
    01416     // constructors, destructors and member functions
    01417
    01418 #ifdef _GLIBCXX_USE_RANDOM_TR1
    01419
    01420     explicit
    01421     random_device(const std::string& __token = "/dev/urandom")
    01422     {
    01423       if ((__token != "/dev/urandom" && __token != "/dev/random")
    01424       || !(_M_file = std::fopen(__token.c_str(), "rb")))
    01425     std::__throw_runtime_error(__N("random_device::"
    01426                        "random_device(const std::string&)"));
    01427     }
    01428
    01429     ~random_device()
    01430     { std::fclose(_M_file); }
    01431
    01432 #else
    01433
    01434     explicit
    01435     random_device(const std::string& __token = "mt19937")
    01436     : _M_mt(_M_strtoul(__token)) { }
    01437
    01438   private:
    01439     static unsigned long
    01440     _M_strtoul(const std::string& __str)
    01441     {
    01442       unsigned long __ret = 5489UL;
    01443       if (__str != "mt19937")
    01444     {
    01445       const char* __nptr = __str.c_str();
    01446       char* __endptr;
    01447       __ret = std::strtoul(__nptr, &__endptr, 0);
    01448       if (*__nptr == '\0' || *__endptr != '\0')
    01449         std::__throw_runtime_error(__N("random_device::_M_strtoul"
    01450                        "(const std::string&)"));
    01451     }
    01452       return __ret;
    01453     }
    01454
    01455   public:
    01456
    01457 #endif
    01458
    01459     result_type
    01460     min() const
    01461     { return std::numeric_limits<result_type>::min(); }
    01462
    01463     result_type
    01464     max() const
    01465     { return std::numeric_limits<result_type>::max(); }
    01466
    01467     double
    01468     entropy() const
    01469     { return 0.0; }
    01470
    01471     result_type
    01472     operator()()
    01473     {
    01474 #ifdef _GLIBCXX_USE_RANDOM_TR1
    01475       result_type __ret;
    01476       std::fread(reinterpret_cast<void*>(&__ret), sizeof(result_type),
    01477          1, _M_file);
    01478       return __ret;
    01479 #else
    01480       return _M_mt();
    01481 #endif
    01482     }
    01483
    01484   private:
    01485     random_device(const random_device&);
    01486     void operator=(const random_device&);
    01487
    01488 #ifdef _GLIBCXX_USE_RANDOM_TR1
    01489     FILE*        _M_file;
    01490 #else
    01491     mt19937      _M_mt;
    01492 #endif
    01493   };
    01494
    01495   /* @} */ // group tr1_random_generators
    01496
    01497   /**
    01498    * @addtogroup tr1_random_distributions Random Number Distributions
    01499    * @ingroup tr1_random
    01500    * @{
    01501    */
    01502
    01503   /**
    01504    * @addtogroup tr1_random_distributions_discrete Discrete Distributions
    01505    * @ingroup tr1_random_distributions
    01506    * @{
    01507    */
    01508
    01509   /**
    01510    * @brief Uniform discrete distribution for random numbers.
    01511    * A discrete random distribution on the range @f$[min, max]@f$ with equal
    01512    * probability throughout the range.
    01513    */
    01514   template<typename _IntType = int>
    01515     class uniform_int
    01516     {
    01517       __glibcxx_class_requires(_IntType, _IntegerConcept)
    01518
    01519     public:
    01520       /** The type of the parameters of the distribution. */
    01521       typedef _IntType input_type;
    01522       /** The type of the range of the distribution. */
    01523       typedef _IntType result_type;
    01524
    01525     public:
    01526       /**
    01527        * Constructs a uniform distribution object.
    01528        */
    01529       explicit
    01530       uniform_int(_IntType __min = 0, _IntType __max = 9)
    01531       : _M_min(__min), _M_max(__max)
    01532       {
    01533     _GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
    01534       }
    01535
    01536       /**
    01537        * Gets the inclusive lower bound of the distribution range.
    01538        */
    01539       result_type
    01540       min() const
    01541       { return _M_min; }
    01542
    01543       /**
    01544        * Gets the inclusive upper bound of the distribution range.
    01545        */
    01546       result_type
    01547       max() const
    01548       { return _M_max; }
    01549
    01550       /**
    01551        * Resets the distribution state.
    01552        *
    01553        * Does nothing for the uniform integer distribution.
    01554        */
    01555       void
    01556       reset() { }
    01557
    01558       /**
    01559        * Gets a uniformly distributed random number in the range
    01560        * @f$(min, max)@f$.
    01561        */
    01562       template<typename _UniformRandomNumberGenerator>
    01563         result_type
    01564         operator()(_UniformRandomNumberGenerator& __urng)
    01565         {
    01566       typedef typename _UniformRandomNumberGenerator::result_type
    01567         _UResult_type;
    01568       return _M_call(__urng, _M_min, _M_max,
    01569              typename is_integral<_UResult_type>::type());
    01570     }
    01571
    01572       /**
    01573        * Gets a uniform random number in the range @f$[0, n)@f$.
    01574        *
    01575        * This function is aimed at use with std::random_shuffle.
    01576        */
    01577       template<typename _UniformRandomNumberGenerator>
    01578         result_type
    01579         operator()(_UniformRandomNumberGenerator& __urng, result_type __n)
    01580         {
    01581       typedef typename _UniformRandomNumberGenerator::result_type
    01582         _UResult_type;
    01583       return _M_call(__urng, 0, __n - 1,
    01584              typename is_integral<_UResult_type>::type());
    01585     }
    01586
    01587       /**
    01588        * Inserts a %uniform_int random number distribution @p __x into the
    01589        * output stream @p os.
    01590        *
    01591        * @param __os An output stream.
    01592        * @param __x  A %uniform_int random number distribution.
    01593        *
    01594        * @returns The output stream with the state of @p __x inserted or in
    01595        * an error state.
    01596        */
    01597       template<typename _IntType1, typename _CharT, typename _Traits>
    01598         friend std::basic_ostream<_CharT, _Traits>&
    01599         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    01600            const uniform_int<_IntType1>& __x);
    01601
    01602       /**
    01603        * Extracts a %unform_int random number distribution
    01604        * @p __x from the input stream @p __is.
    01605        *
    01606        * @param __is An input stream.
    01607        * @param __x  A %uniform_int random number generator engine.
    01608        *
    01609        * @returns The input stream with @p __x extracted or in an error state.
    01610        */
    01611       template<typename _IntType1, typename _CharT, typename _Traits>
    01612         friend std::basic_istream<_CharT, _Traits>&
    01613         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    01614            uniform_int<_IntType1>& __x);
    01615
    01616     private:
    01617       template<typename _UniformRandomNumberGenerator>
    01618         result_type
    01619         _M_call(_UniformRandomNumberGenerator& __urng,
    01620         result_type __min, result_type __max, true_type)
    01621         {
    01622       // XXX Must be fixed to also work when __urng.max() - __urng.min()
    01623       // is smaller than __max - __min.
    01624       typedef typename __gnu_cxx::__add_unsigned<typename
    01625         _UniformRandomNumberGenerator::result_type>::__type __utype;
    01626       return result_type((__max - __min + 1.0L)
    01627                  * (__utype(__urng()) - __utype(__urng.min()))
    01628                  / (__utype(__urng.max())
    01629                 - __utype(__urng.min()) + 1.0L)) + __min;
    01630     }
    01631
    01632       template<typename _UniformRandomNumberGenerator>
    01633         result_type
    01634         _M_call(_UniformRandomNumberGenerator& __urng,
    01635         result_type __min, result_type __max, false_type)
    01636         {
    01637       return result_type((__urng() - __urng.min())
    01638                  / (__urng.max() - __urng.min())
    01639                  * (__max - __min + 1)) + __min;
    01640     }
    01641
    01642       _IntType _M_min;
    01643       _IntType _M_max;
    01644     };
    01645
    01646
    01647   /**
    01648    * @brief A Bernoulli random number distribution.
    01649    *
    01650    * Generates a sequence of true and false values with likelihood @f$ p @f$
    01651    * that true will come up and @f$ (1 - p) @f$ that false will appear.
    01652    */
    01653   class bernoulli_distribution
    01654   {
    01655   public:
    01656     typedef int  input_type;
    01657     typedef bool result_type;
    01658
    01659   public:
    01660     /**
    01661      * Constructs a Bernoulli distribution with likelihood @p p.
    01662      *
    01663      * @param __p  [IN]  The likelihood of a true result being returned.  Must
    01664      * be in the interval @f$ [0, 1] @f$.
    01665      */
    01666     explicit
    01667     bernoulli_distribution(double __p = 0.5)
    01668     : _M_p(__p)
    01669     {
    01670       _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
    01671     }
    01672
    01673     /**
    01674      * Gets the @p p parameter of the distribution.
    01675      */
    01676     double
    01677     p() const
    01678     { return _M_p; }
    01679
    01680     /**
    01681      * Resets the distribution state.
    01682      *
    01683      * Does nothing for a bernoulli distribution.
    01684      */
    01685     void
    01686     reset() { }
    01687
    01688     /**
    01689      * Gets the next value in the Bernoullian sequence.
    01690      */
    01691     template<class _UniformRandomNumberGenerator>
    01692       result_type
    01693       operator()(_UniformRandomNumberGenerator& __urng)
    01694       {
    01695     if ((__urng() - __urng.min()) < _M_p * (__urng.max() - __urng.min()))
    01696       return true;
    01697     return false;
    01698       }
    01699
    01700     /**
    01701      * Inserts a %bernoulli_distribution random number distribution
    01702      * @p __x into the output stream @p __os.
    01703      *
    01704      * @param __os An output stream.
    01705      * @param __x  A %bernoulli_distribution random number distribution.
    01706      *
    01707      * @returns The output stream with the state of @p __x inserted or in
    01708      * an error state.
    01709      */
    01710     template<typename _CharT, typename _Traits>
    01711       friend std::basic_ostream<_CharT, _Traits>&
    01712       operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    01713          const bernoulli_distribution& __x);
    01714
    01715     /**
    01716      * Extracts a %bernoulli_distribution random number distribution
    01717      * @p __x from the input stream @p __is.
    01718      *
    01719      * @param __is An input stream.
    01720      * @param __x  A %bernoulli_distribution random number generator engine.
    01721      *
    01722      * @returns The input stream with @p __x extracted or in an error state.
    01723      */
    01724     template<typename _CharT, typename _Traits>
    01725       friend std::basic_istream<_CharT, _Traits>&
    01726       operator>>(std::basic_istream<_CharT, _Traits>& __is,
    01727          bernoulli_distribution& __x)
    01728       { return __is >> __x._M_p; }
    01729
    01730   private:
    01731     double _M_p;
    01732   };
    01733
    01734
    01735   /**
    01736    * @brief A discrete geometric random number distribution.
    01737    *
    01738    * The formula for the geometric probability mass function is
    01739    * @f$ p(i) = (1 - p)p^{i-1} @f$ where @f$ p @f$ is the parameter of the
    01740    * distribution.
    01741    */
    01742   template<typename _IntType = int, typename _RealType = double>
    01743     class geometric_distribution
    01744     {
    01745     public:
    01746       // types
    01747       typedef _RealType input_type;
    01748       typedef _IntType  result_type;
    01749
    01750       // constructors and member function
    01751       explicit
    01752       geometric_distribution(const _RealType& __p = _RealType(0.5))
    01753       : _M_p(__p)
    01754       {
    01755     _GLIBCXX_DEBUG_ASSERT((_M_p > 0.0) && (_M_p < 1.0));
    01756     _M_initialize();
    01757       }
    01758
    01759       /**
    01760        * Gets the distribution parameter @p p.
    01761        */
    01762       _RealType
    01763       p() const
    01764       { return _M_p; }
    01765
    01766       void
    01767       reset() { }
    01768
    01769       template<class _UniformRandomNumberGenerator>
    01770         result_type
    01771         operator()(_UniformRandomNumberGenerator& __urng);
    01772
    01773       /**
    01774        * Inserts a %geometric_distribution random number distribution
    01775        * @p __x into the output stream @p __os.
    01776        *
    01777        * @param __os An output stream.
    01778        * @param __x  A %geometric_distribution random number distribution.
    01779        *
    01780        * @returns The output stream with the state of @p __x inserted or in
    01781        * an error state.
    01782        */
    01783       template<typename _IntType1, typename _RealType1,
    01784            typename _CharT, typename _Traits>
    01785         friend std::basic_ostream<_CharT, _Traits>&
    01786         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    01787            const geometric_distribution<_IntType1, _RealType1>& __x);
    01788
    01789       /**
    01790        * Extracts a %geometric_distribution random number distribution
    01791        * @p __x from the input stream @p __is.
    01792        *
    01793        * @param __is An input stream.
    01794        * @param __x  A %geometric_distribution random number generator engine.
    01795        *
    01796        * @returns The input stream with @p __x extracted or in an error state.
    01797        */
    01798       template<typename _CharT, typename _Traits>
    01799         friend std::basic_istream<_CharT, _Traits>&
    01800         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    01801            geometric_distribution& __x)
    01802         {
    01803       __is >> __x._M_p;
    01804       __x._M_initialize();
    01805       return __is;
    01806     }
    01807
    01808     private:
    01809       void
    01810       _M_initialize()
    01811       { _M_log_p = std::log(_M_p); }
    01812
    01813       _RealType _M_p;
    01814       _RealType _M_log_p;
    01815     };
    01816
    01817
    01818   template<typename _RealType>
    01819     class normal_distribution;
    01820
    01821   /**
    01822    * @brief A discrete Poisson random number distribution.
    01823    *
    01824    * The formula for the poisson probability mass function is
    01825    * @f$ p(i) = \frac{mean^i}{i!} e^{-mean} @f$ where @f$ mean @f$ is the
    01826    * parameter of the distribution.
    01827    */
    01828   template<typename _IntType = int, typename _RealType = double>
    01829     class poisson_distribution
    01830     {
    01831     public:
    01832       // types
    01833       typedef _RealType input_type;
    01834       typedef _IntType  result_type;
    01835
    01836       // constructors and member function
    01837       explicit
    01838       poisson_distribution(const _RealType& __mean = _RealType(1))
    01839       : _M_mean(__mean), _M_nd()
    01840       {
    01841     _GLIBCXX_DEBUG_ASSERT(_M_mean > 0.0);
    01842     _M_initialize();
    01843       }
    01844
    01845       /**
    01846        * Gets the distribution parameter @p mean.
    01847        */
    01848       _RealType
    01849       mean() const
    01850       { return _M_mean; }
    01851
    01852       void
    01853       reset()
    01854       { _M_nd.reset(); }
    01855
    01856       template<class _UniformRandomNumberGenerator>
    01857         result_type
    01858         operator()(_UniformRandomNumberGenerator& __urng);
    01859
    01860       /**
    01861        * Inserts a %poisson_distribution random number distribution
    01862        * @p __x into the output stream @p __os.
    01863        *
    01864        * @param __os An output stream.
    01865        * @param __x  A %poisson_distribution random number distribution.
    01866        *
    01867        * @returns The output stream with the state of @p __x inserted or in
    01868        * an error state.
    01869        */
    01870       template<typename _IntType1, typename _RealType1,
    01871            typename _CharT, typename _Traits>
    01872         friend std::basic_ostream<_CharT, _Traits>&
    01873         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    01874            const poisson_distribution<_IntType1, _RealType1>& __x);
    01875
    01876       /**
    01877        * Extracts a %poisson_distribution random number distribution
    01878        * @p __x from the input stream @p __is.
    01879        *
    01880        * @param __is An input stream.
    01881        * @param __x  A %poisson_distribution random number generator engine.
    01882        *
    01883        * @returns The input stream with @p __x extracted or in an error state.
    01884        */
    01885       template<typename _IntType1, typename _RealType1,
    01886            typename _CharT, typename _Traits>
    01887         friend std::basic_istream<_CharT, _Traits>&
    01888         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    01889            poisson_distribution<_IntType1, _RealType1>& __x);
    01890
    01891     private:
    01892       void
    01893       _M_initialize();
    01894
    01895       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
    01896       normal_distribution<_RealType> _M_nd;
    01897
    01898       _RealType _M_mean;
    01899
    01900       // Hosts either log(mean) or the threshold of the simple method.
    01901       _RealType _M_lm_thr;
    01902 #if _GLIBCXX_USE_C99_MATH_TR1
    01903       _RealType _M_lfm, _M_sm, _M_d, _M_scx, _M_1cx, _M_c2b, _M_cb;
    01904 #endif
    01905     };
    01906
    01907
    01908   /**
    01909    * @brief A discrete binomial random number distribution.
    01910    *
    01911    * The formula for the binomial probability mass function is
    01912    * @f$ p(i) = \binom{n}{i} p^i (1 - p)^{t - i} @f$ where @f$ t @f$
    01913    * and @f$ p @f$ are the parameters of the distribution.
    01914    */
    01915   template<typename _IntType = int, typename _RealType = double>
    01916     class binomial_distribution
    01917     {
    01918     public:
    01919       // types
    01920       typedef _RealType input_type;
    01921       typedef _IntType  result_type;
    01922
    01923       // constructors and member function
    01924       explicit
    01925       binomial_distribution(_IntType __t = 1,
    01926                 const _RealType& __p = _RealType(0.5))
    01927       : _M_t(__t), _M_p(__p), _M_nd()
    01928       {
    01929     _GLIBCXX_DEBUG_ASSERT((_M_t >= 0) && (_M_p >= 0.0) && (_M_p <= 1.0));
    01930     _M_initialize();
    01931       }
    01932
    01933       /**
    01934        * Gets the distribution @p t parameter.
    01935        */
    01936       _IntType
    01937       t() const
    01938       { return _M_t; }
    01939
    01940       /**
    01941        * Gets the distribution @p p parameter.
    01942        */
    01943       _RealType
    01944       p() const
    01945       { return _M_p; }
    01946
    01947       void
    01948       reset()
    01949       { _M_nd.reset(); }
    01950
    01951       template<class _UniformRandomNumberGenerator>
    01952         result_type
    01953         operator()(_UniformRandomNumberGenerator& __urng);
    01954
    01955       /**
    01956        * Inserts a %binomial_distribution random number distribution
    01957        * @p __x into the output stream @p __os.
    01958        *
    01959        * @param __os An output stream.
    01960        * @param __x  A %binomial_distribution random number distribution.
    01961        *
    01962        * @returns The output stream with the state of @p __x inserted or in
    01963        * an error state.
    01964        */
    01965       template<typename _IntType1, typename _RealType1,
    01966            typename _CharT, typename _Traits>
    01967         friend std::basic_ostream<_CharT, _Traits>&
    01968         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    01969            const binomial_distribution<_IntType1, _RealType1>& __x);
    01970
    01971       /**
    01972        * Extracts a %binomial_distribution random number distribution
    01973        * @p __x from the input stream @p __is.
    01974        *
    01975        * @param __is An input stream.
    01976        * @param __x  A %binomial_distribution random number generator engine.
    01977        *
    01978        * @returns The input stream with @p __x extracted or in an error state.
    01979        */
    01980       template<typename _IntType1, typename _RealType1,
    01981            typename _CharT, typename _Traits>
    01982         friend std::basic_istream<_CharT, _Traits>&
    01983         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    01984            binomial_distribution<_IntType1, _RealType1>& __x);
    01985
    01986     private:
    01987       void
    01988       _M_initialize();
    01989
    01990       template<class _UniformRandomNumberGenerator>
    01991         result_type
    01992         _M_waiting(_UniformRandomNumberGenerator& __urng, _IntType __t);
    01993
    01994       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
    01995       normal_distribution<_RealType> _M_nd;
    01996
    01997       _RealType _M_q;
    01998 #if _GLIBCXX_USE_C99_MATH_TR1
    01999       _RealType _M_d1, _M_d2, _M_s1, _M_s2, _M_c,
    02000             _M_a1, _M_a123, _M_s, _M_lf, _M_lp1p;
    02001 #endif
    02002       _RealType _M_p;
    02003       _IntType  _M_t;
    02004
    02005       bool      _M_easy;
    02006     };
    02007
    02008   /* @} */ // group tr1_random_distributions_discrete
    02009
    02010   /**
    02011    * @addtogroup tr1_random_distributions_continuous Continuous Distributions
    02012    * @ingroup tr1_random_distributions
    02013    * @{
    02014    */
    02015
    02016   /**
    02017    * @brief Uniform continuous distribution for random numbers.
    02018    *
    02019    * A continuous random distribution on the range [min, max) with equal
    02020    * probability throughout the range.  The URNG should be real-valued and
    02021    * deliver number in the range [0, 1).
    02022    */
    02023   template<typename _RealType = double>
    02024     class uniform_real
    02025     {
    02026     public:
    02027       // types
    02028       typedef _RealType input_type;
    02029       typedef _RealType result_type;
    02030
    02031     public:
    02032       /**
    02033        * Constructs a uniform_real object.
    02034        *
    02035        * @param __min [IN]  The lower bound of the distribution.
    02036        * @param __max [IN]  The upper bound of the distribution.
    02037        */
    02038       explicit
    02039       uniform_real(_RealType __min = _RealType(0),
    02040            _RealType __max = _RealType(1))
    02041       : _M_min(__min), _M_max(__max)
    02042       {
    02043     _GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
    02044       }
    02045
    02046       result_type
    02047       min() const
    02048       { return _M_min; }
    02049
    02050       result_type
    02051       max() const
    02052       { return _M_max; }
    02053
    02054       void
    02055       reset() { }
    02056
    02057       template<class _UniformRandomNumberGenerator>
    02058         result_type
    02059         operator()(_UniformRandomNumberGenerator& __urng)
    02060         { return (__urng() * (_M_max - _M_min)) + _M_min; }
    02061
    02062       /**
    02063        * Inserts a %uniform_real random number distribution @p __x into the
    02064        * output stream @p __os.
    02065        *
    02066        * @param __os An output stream.
    02067        * @param __x  A %uniform_real random number distribution.
    02068        *
    02069        * @returns The output stream with the state of @p __x inserted or in
    02070        * an error state.
    02071        */
    02072       template<typename _RealType1, typename _CharT, typename _Traits>
    02073         friend std::basic_ostream<_CharT, _Traits>&
    02074         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    02075            const uniform_real<_RealType1>& __x);
    02076
    02077       /**
    02078        * Extracts a %unform_real random number distribution
    02079        * @p __x from the input stream @p __is.
    02080        *
    02081        * @param __is An input stream.
    02082        * @param __x  A %uniform_real random number generator engine.
    02083        *
    02084        * @returns The input stream with @p __x extracted or in an error state.
    02085        */
    02086       template<typename _RealType1, typename _CharT, typename _Traits>
    02087         friend std::basic_istream<_CharT, _Traits>&
    02088         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    02089            uniform_real<_RealType1>& __x);
    02090
    02091     private:
    02092       _RealType _M_min;
    02093       _RealType _M_max;
    02094     };
    02095
    02096
    02097   /**
    02098    * @brief An exponential continuous distribution for random numbers.
    02099    *
    02100    * The formula for the exponential probability mass function is
    02101    * @f$ p(x) = \lambda e^{-\lambda x} @f$.
    02102    *
    02103    * <table border=1 cellpadding=10 cellspacing=0>
    02104    * <caption align=top>Distribution Statistics</caption>
    02105    * <tr><td>Mean</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
    02106    * <tr><td>Median</td><td>@f$ \frac{\ln 2}{\lambda} @f$</td></tr>
    02107    * <tr><td>Mode</td><td>@f$ zero @f$</td></tr>
    02108    * <tr><td>Range</td><td>@f$[0, \infty]@f$</td></tr>
    02109    * <tr><td>Standard Deviation</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
    02110    * </table>
    02111    */
    02112   template<typename _RealType = double>
    02113     class exponential_distribution
    02114     {
    02115     public:
    02116       // types
    02117       typedef _RealType input_type;
    02118       typedef _RealType result_type;
    02119
    02120     public:
    02121       /**
    02122        * Constructs an exponential distribution with inverse scale parameter
    02123        * @f$ \lambda @f$.
    02124        */
    02125       explicit
    02126       exponential_distribution(const result_type& __lambda = result_type(1))
    02127       : _M_lambda(__lambda)
    02128       {
    02129     _GLIBCXX_DEBUG_ASSERT(_M_lambda > 0);
    02130       }
    02131
    02132       /**
    02133        * Gets the inverse scale parameter of the distribution.
    02134        */
    02135       _RealType
    02136       lambda() const
    02137       { return _M_lambda; }
    02138
    02139       /**
    02140        * Resets the distribution.
    02141        *
    02142        * Has no effect on exponential distributions.
    02143        */
    02144       void
    02145       reset() { }
    02146
    02147       template<class _UniformRandomNumberGenerator>
    02148         result_type
    02149         operator()(_UniformRandomNumberGenerator& __urng)
    02150         { return -std::log(__urng()) / _M_lambda; }
    02151
    02152       /**
    02153        * Inserts a %exponential_distribution random number distribution
    02154        * @p __x into the output stream @p __os.
    02155        *
    02156        * @param __os An output stream.
    02157        * @param __x  A %exponential_distribution random number distribution.
    02158        *
    02159        * @returns The output stream with the state of @p __x inserted or in
    02160        * an error state.
    02161        */
    02162       template<typename _RealType1, typename _CharT, typename _Traits>
    02163         friend std::basic_ostream<_CharT, _Traits>&
    02164         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    02165            const exponential_distribution<_RealType1>& __x);
    02166
    02167       /**
    02168        * Extracts a %exponential_distribution random number distribution
    02169        * @p __x from the input stream @p __is.
    02170        *
    02171        * @param __is An input stream.
    02172        * @param __x A %exponential_distribution random number
    02173        *            generator engine.
    02174        *
    02175        * @returns The input stream with @p __x extracted or in an error state.
    02176        */
    02177       template<typename _CharT, typename _Traits>
    02178         friend std::basic_istream<_CharT, _Traits>&
    02179         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    02180            exponential_distribution& __x)
    02181         { return __is >> __x._M_lambda; }
    02182
    02183     private:
    02184       result_type _M_lambda;
    02185     };
    02186
    02187
    02188   /**
    02189    * @brief A normal continuous distribution for random numbers.
    02190    *
    02191    * The formula for the normal probability mass function is
    02192    * @f$ p(x) = \frac{1}{\sigma \sqrt{2 \pi}}
    02193    *            e^{- \frac{{x - mean}^ {2}}{2 \sigma ^ {2}} } @f$.
    02194    */
    02195   template<typename _RealType = double>
    02196     class normal_distribution
    02197     {
    02198     public:
    02199       // types
    02200       typedef _RealType input_type;
    02201       typedef _RealType result_type;
    02202
    02203     public:
    02204       /**
    02205        * Constructs a normal distribution with parameters @f$ mean @f$ and
    02206        * @f$ \sigma @f$.
    02207        */
    02208       explicit
    02209       normal_distribution(const result_type& __mean = result_type(0),
    02210               const result_type& __sigma = result_type(1))
    02211       : _M_mean(__mean), _M_sigma(__sigma), _M_saved_available(false)
    02212       {
    02213     _GLIBCXX_DEBUG_ASSERT(_M_sigma > 0);
    02214       }
    02215
    02216       /**
    02217        * Gets the mean of the distribution.
    02218        */
    02219       _RealType
    02220       mean() const
    02221       { return _M_mean; }
    02222
    02223       /**
    02224        * Gets the @f$ \sigma @f$ of the distribution.
    02225        */
    02226       _RealType
    02227       sigma() const
    02228       { return _M_sigma; }
    02229
    02230       /**
    02231        * Resets the distribution.
    02232        */
    02233       void
    02234       reset()
    02235       { _M_saved_available = false; }
    02236
    02237       template<class _UniformRandomNumberGenerator>
    02238         result_type
    02239         operator()(_UniformRandomNumberGenerator& __urng);
    02240
    02241       /**
    02242        * Inserts a %normal_distribution random number distribution
    02243        * @p __x into the output stream @p __os.
    02244        *
    02245        * @param __os An output stream.
    02246        * @param __x  A %normal_distribution random number distribution.
    02247        *
    02248        * @returns The output stream with the state of @p __x inserted or in
    02249        * an error state.
    02250        */
    02251       template<typename _RealType1, typename _CharT, typename _Traits>
    02252         friend std::basic_ostream<_CharT, _Traits>&
    02253         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    02254            const normal_distribution<_RealType1>& __x);
    02255
    02256       /**
    02257        * Extracts a %normal_distribution random number distribution
    02258        * @p __x from the input stream @p __is.
    02259        *
    02260        * @param __is An input stream.
    02261        * @param __x  A %normal_distribution random number generator engine.
    02262        *
    02263        * @returns The input stream with @p __x extracted or in an error state.
    02264        */
    02265       template<typename _RealType1, typename _CharT, typename _Traits>
    02266         friend std::basic_istream<_CharT, _Traits>&
    02267         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    02268            normal_distribution<_RealType1>& __x);
    02269
    02270     private:
    02271       result_type _M_mean;
    02272       result_type _M_sigma;
    02273       result_type _M_saved;
    02274       bool        _M_saved_available;
    02275     };
    02276
    02277
    02278   /**
    02279    * @brief A gamma continuous distribution for random numbers.
    02280    *
    02281    * The formula for the gamma probability mass function is
    02282    * @f$ p(x) = \frac{1}{\Gamma(\alpha)} x^{\alpha - 1} e^{-x} @f$.
    02283    */
    02284   template<typename _RealType = double>
    02285     class gamma_distribution
    02286     {
    02287     public:
    02288       // types
    02289       typedef _RealType input_type;
    02290       typedef _RealType result_type;
    02291
    02292     public:
    02293       /**
    02294        * Constructs a gamma distribution with parameters @f$ \alpha @f$.
    02295        */
    02296       explicit
    02297       gamma_distribution(const result_type& __alpha_val = result_type(1))
    02298       : _M_alpha(__alpha_val)
    02299       {
    02300     _GLIBCXX_DEBUG_ASSERT(_M_alpha > 0);
    02301     _M_initialize();
    02302       }
    02303
    02304       /**
    02305        * Gets the @f$ \alpha @f$ of the distribution.
    02306        */
    02307       _RealType
    02308       alpha() const
    02309       { return _M_alpha; }
    02310
    02311       /**
    02312        * Resets the distribution.
    02313        */
    02314       void
    02315       reset() { }
    02316
    02317       template<class _UniformRandomNumberGenerator>
    02318         result_type
    02319         operator()(_UniformRandomNumberGenerator& __urng);
    02320
    02321       /**
    02322        * Inserts a %gamma_distribution random number distribution
    02323        * @p __x into the output stream @p __os.
    02324        *
    02325        * @param __os An output stream.
    02326        * @param __x  A %gamma_distribution random number distribution.
    02327        *
    02328        * @returns The output stream with the state of @p __x inserted or in
    02329        * an error state.
    02330        */
    02331       template<typename _RealType1, typename _CharT, typename _Traits>
    02332         friend std::basic_ostream<_CharT, _Traits>&
    02333         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
    02334            const gamma_distribution<_RealType1>& __x);
    02335
    02336       /**
    02337        * Extracts a %gamma_distribution random number distribution
    02338        * @p __x from the input stream @p __is.
    02339        *
    02340        * @param __is An input stream.
    02341        * @param __x  A %gamma_distribution random number generator engine.
    02342        *
    02343        * @returns The input stream with @p __x extracted or in an error state.
    02344        */
    02345       template<typename _CharT, typename _Traits>
    02346         friend std::basic_istream<_CharT, _Traits>&
    02347         operator>>(std::basic_istream<_CharT, _Traits>& __is,
    02348            gamma_distribution& __x)
    02349         {
    02350       __is >> __x._M_alpha;
    02351       __x._M_initialize();
    02352       return __is;
    02353     }
    02354
    02355     private:
    02356       void
    02357       _M_initialize();
    02358
    02359       result_type _M_alpha;
    02360
    02361       // Hosts either lambda of GB or d of modified Vaduva's.
    02362       result_type _M_l_d;
    02363     };
    02364
    02365   /* @} */ // group tr1_random_distributions_continuous
    02366   /* @} */ // group tr1_random_distributions
    02367   /* @} */ // group tr1_random
    02368
    02369 _GLIBCXX_END_NAMESPACE
    02370 }
    02371
    02372 #include <tr1/random.tcc>
    02373
    02374 #endif // _TR1_RANDOM