contrib/libstdc++/include/tr1/random

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