libstdc++-v3/include/tr1/random

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