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       typedef typename __gnu_cxx::__add_unsigned<typename
01623         _UniformRandomNumberGenerator::result_type>::__type __utype;
01624       return result_type(__utype(__urng()) % (__max - __min + 1)) + __min;
01625     }
01626 
01627       template<typename _UniformRandomNumberGenerator>
01628         result_type
01629         _M_call(_UniformRandomNumberGenerator& __urng,
01630         result_type __min, result_type __max, false_type)
01631         {
01632       return result_type((__urng() - __urng.min())
01633                  / (__urng.max() - __urng.min())
01634                  * (__max - __min + 1)) + __min;
01635     }
01636 
01637       _IntType _M_min;
01638       _IntType _M_max;
01639     };
01640 
01641 
01642   /**
01643    * @brief A Bernoulli random number distribution.
01644    *
01645    * Generates a sequence of true and false values with likelihood @f$ p @f$
01646    * that true will come up and @f$ (1 - p) @f$ that false will appear.
01647    */
01648   class bernoulli_distribution
01649   {
01650   public:
01651     typedef int  input_type;
01652     typedef bool result_type;
01653 
01654   public:
01655     /**
01656      * Constructs a Bernoulli distribution with likelihood @p p.
01657      *
01658      * @param __p  [IN]  The likelihood of a true result being returned.  Must
01659      * be in the interval @f$ [0, 1] @f$.
01660      */
01661     explicit
01662     bernoulli_distribution(double __p = 0.5)
01663     : _M_p(__p)
01664     { 
01665       _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
01666     }
01667 
01668     /**
01669      * Gets the @p p parameter of the distribution.
01670      */
01671     double
01672     p() const
01673     { return _M_p; }
01674 
01675     /**
01676      * Resets the distribution state.
01677      *
01678      * Does nothing for a bernoulli distribution.
01679      */
01680     void
01681     reset() { }
01682 
01683     /**
01684      * Gets the next value in the Bernoullian sequence.
01685      */
01686     template<class _UniformRandomNumberGenerator>
01687       result_type
01688       operator()(_UniformRandomNumberGenerator& __urng)
01689       {
01690     if ((__urng() - __urng.min()) < _M_p * (__urng.max() - __urng.min()))
01691       return true;
01692     return false;
01693       }
01694 
01695     /**
01696      * Inserts a %bernoulli_distribution random number distribution
01697      * @p __x into the output stream @p __os.
01698      *
01699      * @param __os An output stream.
01700      * @param __x  A %bernoulli_distribution random number distribution.
01701      *
01702      * @returns The output stream with the state of @p __x inserted or in
01703      * an error state.
01704      */
01705     template<typename _CharT, typename _Traits>
01706       friend std::basic_ostream<_CharT, _Traits>&
01707       operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01708          const bernoulli_distribution& __x);
01709 
01710     /**
01711      * Extracts a %bernoulli_distribution random number distribution
01712      * @p __x from the input stream @p __is.
01713      *
01714      * @param __is An input stream.
01715      * @param __x  A %bernoulli_distribution random number generator engine.
01716      *
01717      * @returns The input stream with @p __x extracted or in an error state.
01718      */
01719     template<typename _CharT, typename _Traits>
01720       friend std::basic_istream<_CharT, _Traits>&
01721       operator>>(std::basic_istream<_CharT, _Traits>& __is,
01722          bernoulli_distribution& __x)
01723       { return __is >> __x._M_p; }
01724 
01725   private:
01726     double _M_p;
01727   };
01728 
01729 
01730   /**
01731    * @brief A discrete geometric random number distribution.
01732    *
01733    * The formula for the geometric probability mass function is 
01734    * @f$ p(i) = (1 - p)p^{i-1} @f$ where @f$ p @f$ is the parameter of the
01735    * distribution.
01736    */
01737   template<typename _IntType = int, typename _RealType = double>
01738     class geometric_distribution
01739     {
01740     public:
01741       // types
01742       typedef _RealType input_type;
01743       typedef _IntType  result_type;
01744 
01745       // constructors and member function
01746       explicit
01747       geometric_distribution(const _RealType& __p = _RealType(0.5))
01748       : _M_p(__p)
01749       {
01750     _GLIBCXX_DEBUG_ASSERT((_M_p > 0.0) && (_M_p < 1.0));
01751     _M_initialize();
01752       }
01753 
01754       /**
01755        * Gets the distribution parameter @p p.
01756        */
01757       _RealType
01758       p() const
01759       { return _M_p; }
01760 
01761       void
01762       reset() { }
01763 
01764       template<class _UniformRandomNumberGenerator>
01765         result_type
01766         operator()(_UniformRandomNumberGenerator& __urng);
01767 
01768       /**
01769        * Inserts a %geometric_distribution random number distribution
01770        * @p __x into the output stream @p __os.
01771        *
01772        * @param __os An output stream.
01773        * @param __x  A %geometric_distribution random number distribution.
01774        *
01775        * @returns The output stream with the state of @p __x inserted or in
01776        * an error state.
01777        */
01778       template<typename _IntType1, typename _RealType1,
01779            typename _CharT, typename _Traits>
01780         friend std::basic_ostream<_CharT, _Traits>&
01781         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01782            const geometric_distribution<_IntType1, _RealType1>& __x);
01783 
01784       /**
01785        * Extracts a %geometric_distribution random number distribution
01786        * @p __x from the input stream @p __is.
01787        *
01788        * @param __is An input stream.
01789        * @param __x  A %geometric_distribution random number generator engine.
01790        *
01791        * @returns The input stream with @p __x extracted or in an error state.
01792        */
01793       template<typename _CharT, typename _Traits>
01794         friend std::basic_istream<_CharT, _Traits>&
01795         operator>>(std::basic_istream<_CharT, _Traits>& __is,
01796            geometric_distribution& __x)
01797         {
01798       __is >> __x._M_p;
01799       __x._M_initialize();
01800       return __is;
01801     }
01802 
01803     private:
01804       void
01805       _M_initialize()
01806       { _M_log_p = std::log(_M_p); }
01807 
01808       _RealType _M_p;
01809       _RealType _M_log_p;
01810     };
01811 
01812 
01813   template<typename _RealType>
01814     class normal_distribution;
01815 
01816   /**
01817    * @brief A discrete Poisson random number distribution.
01818    *
01819    * The formula for the poisson probability mass function is 
01820    * @f$ p(i) = \frac{mean^i}{i!} e^{-mean} @f$ where @f$ mean @f$ is the
01821    * parameter of the distribution.
01822    */
01823   template<typename _IntType = int, typename _RealType = double>
01824     class poisson_distribution
01825     {
01826     public:
01827       // types
01828       typedef _RealType input_type;
01829       typedef _IntType  result_type;
01830 
01831       // constructors and member function
01832       explicit
01833       poisson_distribution(const _RealType& __mean = _RealType(1))
01834       : _M_mean(__mean), _M_nd()
01835       {
01836     _GLIBCXX_DEBUG_ASSERT(_M_mean > 0.0);
01837     _M_initialize();
01838       }
01839 
01840       /**
01841        * Gets the distribution parameter @p mean.
01842        */
01843       _RealType
01844       mean() const
01845       { return _M_mean; }
01846 
01847       void
01848       reset()
01849       { _M_nd.reset(); }
01850 
01851       template<class _UniformRandomNumberGenerator>
01852         result_type
01853         operator()(_UniformRandomNumberGenerator& __urng);
01854 
01855       /**
01856        * Inserts a %poisson_distribution random number distribution
01857        * @p __x into the output stream @p __os.
01858        *
01859        * @param __os An output stream.
01860        * @param __x  A %poisson_distribution random number distribution.
01861        *
01862        * @returns The output stream with the state of @p __x inserted or in
01863        * an error state.
01864        */
01865       template<typename _IntType1, typename _RealType1,
01866            typename _CharT, typename _Traits>
01867         friend std::basic_ostream<_CharT, _Traits>&
01868         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01869            const poisson_distribution<_IntType1, _RealType1>& __x);
01870 
01871       /**
01872        * Extracts a %poisson_distribution random number distribution
01873        * @p __x from the input stream @p __is.
01874        *
01875        * @param __is An input stream.
01876        * @param __x  A %poisson_distribution random number generator engine.
01877        *
01878        * @returns The input stream with @p __x extracted or in an error state.
01879        */
01880       template<typename _IntType1, typename _RealType1,
01881            typename _CharT, typename _Traits>
01882         friend std::basic_istream<_CharT, _Traits>&
01883         operator>>(std::basic_istream<_CharT, _Traits>& __is,
01884            poisson_distribution<_IntType1, _RealType1>& __x);
01885 
01886     private:
01887       void
01888       _M_initialize();
01889 
01890       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
01891       normal_distribution<_RealType> _M_nd;
01892 
01893       _RealType _M_mean;
01894 
01895       // Hosts either log(mean) or the threshold of the simple method.
01896       _RealType _M_lm_thr;
01897 #if _GLIBCXX_USE_C99_MATH_TR1
01898       _RealType _M_lfm, _M_sm, _M_d, _M_scx, _M_1cx, _M_c2b, _M_cb;
01899 #endif
01900     };
01901 
01902 
01903   /**
01904    * @brief A discrete binomial random number distribution.
01905    *
01906    * The formula for the binomial probability mass function is 
01907    * @f$ p(i) = \binom{n}{i} p^i (1 - p)^{t - i} @f$ where @f$ t @f$
01908    * and @f$ p @f$ are the parameters of the distribution.
01909    */
01910   template<typename _IntType = int, typename _RealType = double>
01911     class binomial_distribution
01912     {
01913     public:
01914       // types
01915       typedef _RealType input_type;
01916       typedef _IntType  result_type;
01917 
01918       // constructors and member function
01919       explicit
01920       binomial_distribution(_IntType __t = 1,
01921                 const _RealType& __p = _RealType(0.5))
01922       : _M_t(__t), _M_p(__p), _M_nd()
01923       {
01924     _GLIBCXX_DEBUG_ASSERT((_M_t >= 0) && (_M_p >= 0.0) && (_M_p <= 1.0));
01925     _M_initialize();
01926       }
01927 
01928       /**
01929        * Gets the distribution @p t parameter.
01930        */
01931       _IntType
01932       t() const
01933       { return _M_t; }
01934       
01935       /**
01936        * Gets the distribution @p p parameter.
01937        */
01938       _RealType
01939       p() const
01940       { return _M_p; }
01941 
01942       void
01943       reset()
01944       { _M_nd.reset(); }
01945 
01946       template<class _UniformRandomNumberGenerator>
01947         result_type
01948         operator()(_UniformRandomNumberGenerator& __urng);
01949 
01950       /**
01951        * Inserts a %binomial_distribution random number distribution
01952        * @p __x into the output stream @p __os.
01953        *
01954        * @param __os An output stream.
01955        * @param __x  A %binomial_distribution random number distribution.
01956        *
01957        * @returns The output stream with the state of @p __x inserted or in
01958        * an error state.
01959        */
01960       template<typename _IntType1, typename _RealType1,
01961            typename _CharT, typename _Traits>
01962         friend std::basic_ostream<_CharT, _Traits>&
01963         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
01964            const binomial_distribution<_IntType1, _RealType1>& __x);
01965 
01966       /**
01967        * Extracts a %binomial_distribution random number distribution
01968        * @p __x from the input stream @p __is.
01969        *
01970        * @param __is An input stream.
01971        * @param __x  A %binomial_distribution random number generator engine.
01972        *
01973        * @returns The input stream with @p __x extracted or in an error state.
01974        */
01975       template<typename _IntType1, typename _RealType1,
01976            typename _CharT, typename _Traits>
01977         friend std::basic_istream<_CharT, _Traits>&
01978         operator>>(std::basic_istream<_CharT, _Traits>& __is,
01979            binomial_distribution<_IntType1, _RealType1>& __x);
01980 
01981     private:
01982       void
01983       _M_initialize();
01984 
01985       template<class _UniformRandomNumberGenerator>
01986         result_type
01987         _M_waiting(_UniformRandomNumberGenerator& __urng, _IntType __t);
01988 
01989       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
01990       normal_distribution<_RealType> _M_nd;
01991 
01992       _RealType _M_q;
01993 #if _GLIBCXX_USE_C99_MATH_TR1
01994       _RealType _M_d1, _M_d2, _M_s1, _M_s2, _M_c,
01995             _M_a1, _M_a123, _M_s, _M_lf, _M_lp1p;
01996 #endif
01997       _RealType _M_p;
01998       _IntType  _M_t;
01999 
02000       bool      _M_easy;
02001     };
02002 
02003   /* @} */ // group tr1_random_distributions_discrete
02004 
02005   /**
02006    * @addtogroup tr1_random_distributions_continuous Continuous Distributions
02007    * @ingroup tr1_random_distributions
02008    * @{
02009    */
02010 
02011   /**
02012    * @brief Uniform continuous distribution for random numbers.
02013    *
02014    * A continuous random distribution on the range [min, max) with equal
02015    * probability throughout the range.  The URNG should be real-valued and
02016    * deliver number in the range [0, 1).
02017    */
02018   template<typename _RealType = double>
02019     class uniform_real
02020     {
02021     public:
02022       // types
02023       typedef _RealType input_type;
02024       typedef _RealType result_type;
02025 
02026     public:
02027       /**
02028        * Constructs a uniform_real object.
02029        *
02030        * @param __min [IN]  The lower bound of the distribution.
02031        * @param __max [IN]  The upper bound of the distribution.
02032        */
02033       explicit
02034       uniform_real(_RealType __min = _RealType(0),
02035            _RealType __max = _RealType(1))
02036       : _M_min(__min), _M_max(__max)
02037       {
02038     _GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
02039       }
02040 
02041       result_type
02042       min() const
02043       { return _M_min; }
02044 
02045       result_type
02046       max() const
02047       { return _M_max; }
02048 
02049       void
02050       reset() { }
02051 
02052       template<class _UniformRandomNumberGenerator>
02053         result_type
02054         operator()(_UniformRandomNumberGenerator& __urng)
02055         { return (__urng() * (_M_max - _M_min)) + _M_min; }
02056 
02057       /**
02058        * Inserts a %uniform_real random number distribution @p __x into the
02059        * output stream @p __os.
02060        *
02061        * @param __os An output stream.
02062        * @param __x  A %uniform_real random number distribution.
02063        *
02064        * @returns The output stream with the state of @p __x inserted or in
02065        * an error state.
02066        */
02067       template<typename _RealType1, typename _CharT, typename _Traits>
02068         friend std::basic_ostream<_CharT, _Traits>&
02069         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
02070            const uniform_real<_RealType1>& __x);
02071 
02072       /**
02073        * Extracts a %unform_real random number distribution
02074        * @p __x from the input stream @p __is.
02075        *
02076        * @param __is An input stream.
02077        * @param __x  A %uniform_real random number generator engine.
02078        *
02079        * @returns The input stream with @p __x extracted or in an error state.
02080        */
02081       template<typename _RealType1, typename _CharT, typename _Traits>
02082         friend std::basic_istream<_CharT, _Traits>&
02083         operator>>(std::basic_istream<_CharT, _Traits>& __is,
02084            uniform_real<_RealType1>& __x);
02085 
02086     private:
02087       _RealType _M_min;
02088       _RealType _M_max;
02089     };
02090 
02091 
02092   /**
02093    * @brief An exponential continuous distribution for random numbers.
02094    *
02095    * The formula for the exponential probability mass function is 
02096    * @f$ p(x) = \lambda e^{-\lambda x} @f$.
02097    *
02098    * <table border=1 cellpadding=10 cellspacing=0>
02099    * <caption align=top>Distribution Statistics</caption>
02100    * <tr><td>Mean</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
02101    * <tr><td>Median</td><td>@f$ \frac{\ln 2}{\lambda} @f$</td></tr>
02102    * <tr><td>Mode</td><td>@f$ zero @f$</td></tr>
02103    * <tr><td>Range</td><td>@f$[0, \infty]@f$</td></tr>
02104    * <tr><td>Standard Deviation</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
02105    * </table>
02106    */
02107   template<typename _RealType = double>
02108     class exponential_distribution
02109     {
02110     public:
02111       // types
02112       typedef _RealType input_type;
02113       typedef _RealType result_type;
02114 
02115     public:
02116       /**
02117        * Constructs an exponential distribution with inverse scale parameter
02118        * @f$ \lambda @f$.
02119        */
02120       explicit
02121       exponential_distribution(const result_type& __lambda = result_type(1))
02122       : _M_lambda(__lambda)
02123       { 
02124     _GLIBCXX_DEBUG_ASSERT(_M_lambda > 0);
02125       }
02126 
02127       /**
02128        * Gets the inverse scale parameter of the distribution.
02129        */
02130       _RealType
02131       lambda() const
02132       { return _M_lambda; }
02133 
02134       /**
02135        * Resets the distribution.
02136        *
02137        * Has no effect on exponential distributions.
02138        */
02139       void
02140       reset() { }
02141 
02142       template<class _UniformRandomNumberGenerator>
02143         result_type
02144         operator()(_UniformRandomNumberGenerator& __urng)
02145         { return -std::log(__urng()) / _M_lambda; }
02146 
02147       /**
02148        * Inserts a %exponential_distribution random number distribution
02149        * @p __x into the output stream @p __os.
02150        *
02151        * @param __os An output stream.
02152        * @param __x  A %exponential_distribution random number distribution.
02153        *
02154        * @returns The output stream with the state of @p __x inserted or in
02155        * an error state.
02156        */
02157       template<typename _RealType1, typename _CharT, typename _Traits>
02158         friend std::basic_ostream<_CharT, _Traits>&
02159         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
02160            const exponential_distribution<_RealType1>& __x);
02161 
02162       /**
02163        * Extracts a %exponential_distribution random number distribution
02164        * @p __x from the input stream @p __is.
02165        *
02166        * @param __is An input stream.
02167        * @param __x A %exponential_distribution random number
02168        *            generator engine.
02169        *
02170        * @returns The input stream with @p __x extracted or in an error state.
02171        */
02172       template<typename _CharT, typename _Traits>
02173         friend std::basic_istream<_CharT, _Traits>&
02174         operator>>(std::basic_istream<_CharT, _Traits>& __is,
02175            exponential_distribution& __x)
02176         { return __is >> __x._M_lambda; }
02177 
02178     private:
02179       result_type _M_lambda;
02180     };
02181 
02182 
02183   /**
02184    * @brief A normal continuous distribution for random numbers.
02185    *
02186    * The formula for the normal probability mass function is 
02187    * @f$ p(x) = \frac{1}{\sigma \sqrt{2 \pi}} 
02188    *            e^{- \frac{{x - mean}^ {2}}{2 \sigma ^ {2}} } @f$.
02189    */
02190   template<typename _RealType = double>
02191     class normal_distribution
02192     {
02193     public:
02194       // types
02195       typedef _RealType input_type;
02196       typedef _RealType result_type;
02197 
02198     public:
02199       /**
02200        * Constructs a normal distribution with parameters @f$ mean @f$ and
02201        * @f$ \sigma @f$.
02202        */
02203       explicit
02204       normal_distribution(const result_type& __mean = result_type(0),
02205               const result_type& __sigma = result_type(1))
02206       : _M_mean(__mean), _M_sigma(__sigma), _M_saved_available(false)
02207       { 
02208     _GLIBCXX_DEBUG_ASSERT(_M_sigma > 0);
02209       }
02210 
02211       /**
02212        * Gets the mean of the distribution.
02213        */
02214       _RealType
02215       mean() const
02216       { return _M_mean; }
02217 
02218       /**
02219        * Gets the @f$ \sigma @f$ of the distribution.
02220        */
02221       _RealType
02222       sigma() const
02223       { return _M_sigma; }
02224 
02225       /**
02226        * Resets the distribution.
02227        */
02228       void
02229       reset()
02230       { _M_saved_available = false; }
02231 
02232       template<class _UniformRandomNumberGenerator>
02233         result_type
02234         operator()(_UniformRandomNumberGenerator& __urng);
02235 
02236       /**
02237        * Inserts a %normal_distribution random number distribution
02238        * @p __x into the output stream @p __os.
02239        *
02240        * @param __os An output stream.
02241        * @param __x  A %normal_distribution random number distribution.
02242        *
02243        * @returns The output stream with the state of @p __x inserted or in
02244        * an error state.
02245        */
02246       template<typename _RealType1, typename _CharT, typename _Traits>
02247         friend std::basic_ostream<_CharT, _Traits>&
02248         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
02249            const normal_distribution<_RealType1>& __x);
02250 
02251       /**
02252        * Extracts a %normal_distribution random number distribution
02253        * @p __x from the input stream @p __is.
02254        *
02255        * @param __is An input stream.
02256        * @param __x  A %normal_distribution random number generator engine.
02257        *
02258        * @returns The input stream with @p __x extracted or in an error state.
02259        */
02260       template<typename _RealType1, typename _CharT, typename _Traits>
02261         friend std::basic_istream<_CharT, _Traits>&
02262         operator>>(std::basic_istream<_CharT, _Traits>& __is,
02263            normal_distribution<_RealType1>& __x);
02264 
02265     private:
02266       result_type _M_mean;
02267       result_type _M_sigma;
02268       result_type _M_saved;
02269       bool        _M_saved_available;     
02270     };
02271 
02272 
02273   /**
02274    * @brief A gamma continuous distribution for random numbers.
02275    *
02276    * The formula for the gamma probability mass function is 
02277    * @f$ p(x) = \frac{1}{\Gamma(\alpha)} x^{\alpha - 1} e^{-x} @f$.
02278    */
02279   template<typename _RealType = double>
02280     class gamma_distribution
02281     {
02282     public:
02283       // types
02284       typedef _RealType input_type;
02285       typedef _RealType result_type;
02286 
02287     public:
02288       /**
02289        * Constructs a gamma distribution with parameters @f$ \alpha @f$.
02290        */
02291       explicit
02292       gamma_distribution(const result_type& __alpha_val = result_type(1))
02293       : _M_alpha(__alpha_val)
02294       { 
02295     _GLIBCXX_DEBUG_ASSERT(_M_alpha > 0);
02296     _M_initialize();
02297       }
02298 
02299       /**
02300        * Gets the @f$ \alpha @f$ of the distribution.
02301        */
02302       _RealType
02303       alpha() const
02304       { return _M_alpha; }
02305 
02306       /**
02307        * Resets the distribution.
02308        */
02309       void
02310       reset() { }
02311 
02312       template<class _UniformRandomNumberGenerator>
02313         result_type
02314         operator()(_UniformRandomNumberGenerator& __urng);
02315 
02316       /**
02317        * Inserts a %gamma_distribution random number distribution
02318        * @p __x into the output stream @p __os.
02319        *
02320        * @param __os An output stream.
02321        * @param __x  A %gamma_distribution random number distribution.
02322        *
02323        * @returns The output stream with the state of @p __x inserted or in
02324        * an error state.
02325        */
02326       template<typename _RealType1, typename _CharT, typename _Traits>
02327         friend std::basic_ostream<_CharT, _Traits>&
02328         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
02329            const gamma_distribution<_RealType1>& __x);
02330 
02331       /**
02332        * Extracts a %gamma_distribution random number distribution
02333        * @p __x from the input stream @p __is.
02334        *
02335        * @param __is An input stream.
02336        * @param __x  A %gamma_distribution random number generator engine.
02337        *
02338        * @returns The input stream with @p __x extracted or in an error state.
02339        */
02340       template<typename _CharT, typename _Traits>
02341         friend std::basic_istream<_CharT, _Traits>&
02342         operator>>(std::basic_istream<_CharT, _Traits>& __is,
02343            gamma_distribution& __x)
02344         {
02345       __is >> __x._M_alpha;
02346       __x._M_initialize();
02347       return __is;
02348     }
02349 
02350     private:
02351       void
02352       _M_initialize();
02353 
02354       result_type _M_alpha;
02355 
02356       // Hosts either lambda of GB or d of modified Vaduva's.
02357       result_type _M_l_d;
02358     };
02359 
02360   /* @} */ // group tr1_random_distributions_continuous
02361   /* @} */ // group tr1_random_distributions
02362   /* @} */ // group tr1_random
02363 
02364 _GLIBCXX_END_NAMESPACE
02365 }
02366 
02367 #include <tr1/random.tcc>
02368 
02369 #endif // _TR1_RANDOM

Generated on Sat Sep 29 00:35:37 2007 for libstdc++ by  doxygen 1.5.3