random

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

Generated on Thu Nov 1 13:12:21 2007 for libstdc++ by  doxygen 1.5.1