tr1_impl/random

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

Generated on Thu Jul 23 21:16:13 2009 for libstdc++ by  doxygen 1.5.8