libstdc++-v3/include/bits/random.h

   1 // random number generation -*- C++ -*-
   2
   3 // Copyright (C) 2009 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /**
  26  * @file bits/random.h
  27  *  This is an internal header file, included by other library headers.
  28  *  You should not attempt to use it directly.
  29  */
  30
  31 #include <vector>
  32
  33 namespace std
  34 {
  35
  36   // [26.4] Random number generation
  37
  38   /**
  39    * @addtogroup std_random Random Number Generation
  40    * A facility for generating random numbers on selected distributions.
  41    * @{
  42    */
  43
  44   /**
  45    * @brief A function template for converting the output of a (integral)
  46    * uniform random number generator to a floatng point result in the range
  47    * [0-1).
  48    */
  49   template<typename _RealType, size_t __bits,
  50            typename _UniformRandomNumberGenerator>
  51     _RealType
  52     generate_canonical(_UniformRandomNumberGenerator& __g);
  53
  54   class seed_seq;
  55
  56   /*
  57    * Implementation-space details.
  58    */
  59   namespace __detail
  60   {
  61     template<typename _UIntType, size_t __w,
  62              bool = __w < static_cast<size_t>
  63                           (std::numeric_limits<_UIntType>::digits)>
  64       struct _Shift
  65       { static const _UIntType __value = 0; };
  66
  67     template<typename _UIntType, size_t __w>
  68       struct _Shift<_UIntType, __w, true>
  69       { static const _UIntType __value = _UIntType(1) << __w; };
  70
  71     template<typename _Tp, _Tp __m, _Tp __a, _Tp __c, bool>
  72       struct _Mod;
  73
  74     // Dispatch based on modulus value to prevent divide-by-zero compile-time
  75     // errors when m == 0.
  76     template<typename _Tp, _Tp __m, _Tp __a = 1, _Tp __c = 0>
  77       inline _Tp
  78       __mod(_Tp __x)
  79       { return _Mod<_Tp, __m, __a, __c, __m == 0>::__calc(__x); }
  80
  81     /*
  82      * An adaptor class for converting the output of any Generator into
  83      * the input for a specific Distribution.
  84      */
  85     template<typename _Engine, typename _DInputType>
  86       struct _Adaptor
  87       {
  88
  89       public:
  90         _Adaptor(_Engine& __g)
  91         : _M_g(__g) { }
  92
  93         _DInputType
  94         min() const
  95         { return _DInputType(0); }
  96
  97         _DInputType
  98         max() const
  99         { return _DInputType(1); }
 100
 101         /*
 102          * Converts a value generated by the adapted random number generator
 103          * into a value in the input domain for the dependent random number
 104          * distribution.
 105          */
 106         _DInputType
 107         operator()()
 108         {
 109           return std::generate_canonical<_DInputType,
 110                                     std::numeric_limits<_DInputType>::digits,
 111                                     _Engine>(_M_g);
 112         }
 113
 114       private:
 115         _Engine& _M_g;
 116       };
 117   } // namespace __detail
 118
 119   /**
 120    * @addtogroup std_random_generators Random Number Generators
 121    * @ingroup std_random
 122    *
 123    * These classes define objects which provide random or pseudorandom
 124    * numbers, either from a discrete or a continuous interval.  The
 125    * random number generator supplied as a part of this library are
 126    * all uniform random number generators which provide a sequence of
 127    * random number uniformly distributed over their range.
 128    *
 129    * A number generator is a function object with an operator() that
 130    * takes zero arguments and returns a number.
 131    *
 132    * A compliant random number generator must satisfy the following
 133    * requirements.  <table border=1 cellpadding=10 cellspacing=0>
 134    * <caption align=top>Random Number Generator Requirements</caption>
 135    * <tr><td>To be documented.</td></tr> </table>
 136    *
 137    * @{
 138    */
 139
 140   /**
 141    * @brief A model of a linear congruential random number generator.
 142    *
 143    * A random number generator that produces pseudorandom numbers using the
 144    * linear function @f$x_{i+1}\leftarrow(ax_{i} + c) \bmod m @f$.
 145    *
 146    * The template parameter @p _UIntType must be an unsigned integral type
 147    * large enough to store values up to (__m-1). If the template parameter
 148    * @p __m is 0, the modulus @p __m used is
 149    * std::numeric_limits<_UIntType>::max() plus 1. Otherwise, the template
 150    * parameters @p __a and @p __c must be less than @p __m.
 151    *
 152    * The size of the state is @f$ 1 @f$.
 153    */
 154   template<typename _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 155     class linear_congruential_engine
 156     {
 157       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
 158       static_assert(__m == 0 || (__a < __m && __c < __m),
 159                     "template arguments out of bounds"
 160                     " in linear_congruential_engine");
 161
 162     public:
 163       /** The type of the generated random value. */
 164       typedef _UIntType result_type;
 165
 166       /** The multiplier. */
 167       static const result_type multiplier   = __a;
 168       /** An increment. */
 169       static const result_type increment    = __c;
 170       /** The modulus. */
 171       static const result_type modulus      = __m;
 172       static const result_type default_seed = 1u;
 173
 174       /**
 175        * @brief Constructs a %linear_congruential_engine random number
 176        *        generator engine with seed @p __s.  The default seed value
 177        *        is 1.
 178        *
 179        * @param __s The initial seed value.
 180        */
 181       explicit
 182       linear_congruential_engine(result_type __s = default_seed)
 183       { this->seed(__s); }
 184
 185       /**
 186        * @brief Constructs a %linear_congruential_engine random number
 187        *        generator engine seeded from the seed sequence @p __q.
 188        *
 189        * @param __q the seed sequence.
 190        */
 191       explicit
 192       linear_congruential_engine(seed_seq& __q)
 193       { this->seed(__q); }
 194
 195       /**
 196        * @brief Reseeds the %linear_congruential_engine random number generator
 197        *        engine sequence to the seed @p __s.
 198        *
 199        * @param __s The new seed.
 200        */
 201       void
 202       seed(result_type __s = default_seed);
 203
 204       /**
 205        * @brief Reseeds the %linear_congruential_engine random number generator
 206        *        engine
 207        * sequence using values from the seed sequence @p __q.
 208        *
 209        * @param __q the seed sequence.
 210        */
 211       void
 212       seed(seed_seq& __q);
 213
 214       /**
 215        * @brief Gets the smallest possible value in the output range.
 216        *
 217        * The minimum depends on the @p __c parameter: if it is zero, the
 218        * minimum generated must be > 0, otherwise 0 is allowed.
 219        *
 220        * @todo This should be constexpr.
 221        */
 222       result_type
 223       min() const
 224       { return __c == 0u ? 1u : 0u; }
 225
 226       /**
 227        * @brief Gets the largest possible value in the output range.
 228        *
 229        * @todo This should be constexpr.
 230        */
 231       result_type
 232       max() const
 233       { return __m - 1u; }
 234
 235       /**
 236        * @brief Discard a sequence of random numbers.
 237        *
 238        * @todo Look for a faster way to do discard.
 239        */
 240       void
 241       discard(unsigned long long __z)
 242       {
 243         for (; __z != 0ULL; --__z)
 244           (*this)();
 245       }
 246
 247       /**
 248        * @brief Gets the next random number in the sequence.
 249        */
 250       result_type
 251       operator()()
 252       {
 253         _M_x = __detail::__mod<_UIntType, __m, __a, __c>(_M_x);
 254         return _M_x;
 255       }
 256
 257       /**
 258        * @brief Compares two linear congruential random number generator
 259        * objects of the same type for equality.
 260        *
 261        * @param __lhs A linear congruential random number generator object.
 262        * @param __rhs Another linear congruential random number generator
 263        *              object.
 264        *
 265        * @returns true if the two objects are equal, false otherwise.
 266        */
 267       friend bool
 268       operator==(const linear_congruential_engine& __lhs,
 269                  const linear_congruential_engine& __rhs)
 270       { return __lhs._M_x == __rhs._M_x; }
 271
 272       /**
 273        * @brief Writes the textual representation of the state x(i) of x to
 274        *        @p __os.
 275        *
 276        * @param __os  The output stream.
 277        * @param __lcr A % linear_congruential_engine random number generator.
 278        * @returns __os.
 279        */
 280       template<typename _UIntType1, _UIntType1 __a1, _UIntType1 __c1,
 281                _UIntType1 __m1, typename _CharT, typename _Traits>
 282         friend std::basic_ostream<_CharT, _Traits>&
 283         operator<<(std::basic_ostream<_CharT, _Traits>&,
 284                    const std::linear_congruential_engine<_UIntType1,
 285                    __a1, __c1, __m1>&);
 286
 287       /**
 288        * @brief Sets the state of the engine by reading its textual
 289        *        representation from @p __is.
 290        *
 291        * The textual representation must have been previously written using
 292        * an output stream whose imbued locale and whose type's template
 293        * specialization arguments _CharT and _Traits were the same as those
 294        * of @p __is.
 295        *
 296        * @param __is  The input stream.
 297        * @param __lcr A % linear_congruential_engine random number generator.
 298        * @returns __is.
 299        */
 300       template<typename _UIntType1, _UIntType1 __a1, _UIntType1 __c1,
 301                _UIntType1 __m1, typename _CharT, typename _Traits>
 302         friend std::basic_istream<_CharT, _Traits>&
 303         operator>>(std::basic_istream<_CharT, _Traits>&,
 304                    std::linear_congruential_engine<_UIntType1, __a1,
 305                    __c1, __m1>&);
 306
 307     private:
 308       _UIntType _M_x;
 309     };
 310
 311
 312   /**
 313    * A generalized feedback shift register discrete random number generator.
 314    *
 315    * This algorithm avoids multiplication and division and is designed to be
 316    * friendly to a pipelined architecture.  If the parameters are chosen
 317    * correctly, this generator will produce numbers with a very long period and
 318    * fairly good apparent entropy, although still not cryptographically strong.
 319    *
 320    * The best way to use this generator is with the predefined mt19937 class.
 321    *
 322    * This algorithm was originally invented by Makoto Matsumoto and
 323    * Takuji Nishimura.
 324    *
 325    * @var word_size   The number of bits in each element of the state vector.
 326    * @var state_size  The degree of recursion.
 327    * @var shift_size  The period parameter.
 328    * @var mask_bits   The separation point bit index.
 329    * @var parameter_a The last row of the twist matrix.
 330    * @var output_u    The first right-shift tempering matrix parameter.
 331    * @var output_s    The first left-shift tempering matrix parameter.
 332    * @var output_b    The first left-shift tempering matrix mask.
 333    * @var output_t    The second left-shift tempering matrix parameter.
 334    * @var output_c    The second left-shift tempering matrix mask.
 335    * @var output_l    The second right-shift tempering matrix parameter.
 336    */
 337   template<typename _UIntType, size_t __w,
 338            size_t __n, size_t __m, size_t __r,
 339            _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 340            _UIntType __b, size_t __t,
 341            _UIntType __c, size_t __l, _UIntType __f>
 342     class mersenne_twister_engine
 343     {
 344       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
 345
 346       static_assert(__m >= 1U,
 347                     "mersenne_twister_engine template arguments out of bounds");
 348       static_assert(__n >= __m,
 349                     "mersenne_twister_engine template arguments out of bounds");
 350       static_assert(__w >= __r,
 351                     "mersenne_twister_engine template arguments out of bounds");
 352       static_assert(__w >= __u,
 353                     "mersenne_twister_engine template arguments out of bounds");
 354       static_assert(__w >= __s,
 355                     "mersenne_twister_engine template arguments out of bounds");
 356       static_assert(__w >= __t,
 357                     "mersenne_twister_engine template arguments out of bounds");
 358       static_assert(__w >= __l,
 359                     "mersenne_twister_engine template arguments out of bounds");
 360       static_assert(__w <=
 361                     static_cast<size_t>(std::numeric_limits<_UIntType>::digits),
 362                     "mersenne_twister_engine template arguments out of bounds");
 363       static_assert(__a <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 364                     "mersenne_twister_engine template arguments out of bounds");
 365       static_assert(__b <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 366                     "mersenne_twister_engine template arguments out of bounds");
 367       static_assert(__c <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 368                     "mersenne_twister_engine template arguments out of bounds");
 369       static_assert(__d <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 370                     "mersenne_twister_engine template arguments out of bounds");
 371       static_assert(__f <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 372                     "mersenne_twister_engine template arguments out of bounds");
 373
 374     public:
 375       /** The type of the generated random value. */
 376       typedef _UIntType result_type;
 377
 378       // parameter values
 379       static const size_t      word_size                 = __w;
 380       static const size_t      state_size                = __n;
 381       static const size_t      shift_size                = __m;
 382       static const size_t      mask_bits                 = __r;
 383       static const result_type xor_mask                  = __a;
 384       static const size_t      tempering_u               = __u;
 385       static const result_type tempering_d               = __d;
 386       static const size_t      tempering_s               = __s;
 387       static const result_type tempering_b               = __b;
 388       static const size_t      tempering_t               = __t;
 389       static const result_type tempering_c               = __c;
 390       static const size_t      tempering_l               = __l;
 391       static const result_type initialization_multiplier = __f;
 392       static const result_type default_seed = 5489u;
 393
 394       // constructors and member function
 395       explicit
 396       mersenne_twister_engine(result_type __sd = default_seed)
 397       { seed(__sd); }
 398
 399       /**
 400        * @brief Constructs a %mersenne_twister_engine random number generator
 401        *        engine seeded from the seed sequence @p __q.
 402        *
 403        * @param __q the seed sequence.
 404        */
 405       explicit
 406       mersenne_twister_engine(seed_seq& __q)
 407       { seed(__q); }
 408
 409       void
 410       seed(result_type __sd = default_seed);
 411
 412       void
 413       seed(seed_seq& __q);
 414
 415       /**
 416        * @brief Gets the smallest possible value in the output range.
 417        *
 418        * @todo This should be constexpr.
 419        */
 420       result_type
 421       min() const
 422       { return 0; };
 423
 424       /**
 425        * @brief Gets the largest possible value in the output range.
 426        *
 427        * @todo This should be constexpr.
 428        */
 429       result_type
 430       max() const
 431       { return __detail::_Shift<_UIntType, __w>::__value - 1; }
 432
 433       /**
 434        * @brief Discard a sequence of random numbers.
 435        *
 436        * @todo Look for a faster way to do discard.
 437        */
 438       void
 439       discard(unsigned long long __z)
 440       {
 441         for (; __z != 0ULL; --__z)
 442           (*this)();
 443       }
 444
 445       result_type
 446       operator()();
 447
 448       /**
 449        * @brief Compares two % mersenne_twister_engine random number generator
 450        *        objects of the same type for equality.
 451        *
 452        * @param __lhs A % mersenne_twister_engine random number generator
 453        *              object.
 454        * @param __rhs Another % mersenne_twister_engine random number
 455        *              generator object.
 456        *
 457        * @returns true if the two objects are equal, false otherwise.
 458        */
 459       friend bool
 460       operator==(const mersenne_twister_engine& __lhs,
 461                  const mersenne_twister_engine& __rhs)
 462       { return std::equal(__lhs._M_x, __lhs._M_x + state_size, __rhs._M_x); }
 463
 464       /**
 465        * @brief Inserts the current state of a % mersenne_twister_engine
 466        *        random number generator engine @p __x into the output stream
 467        *        @p __os.
 468        *
 469        * @param __os An output stream.
 470        * @param __x  A % mersenne_twister_engine random number generator
 471        *             engine.
 472        *
 473        * @returns The output stream with the state of @p __x inserted or in
 474        * an error state.
 475        */
 476       template<typename _UIntType1,
 477                size_t __w1, size_t __n1,
 478                size_t __m1, size_t __r1,
 479                _UIntType1 __a1, size_t __u1,
 480                _UIntType1 __d1, size_t __s1,
 481                _UIntType1 __b1, size_t __t1,
 482                _UIntType1 __c1, size_t __l1, _UIntType1 __f1,
 483                typename _CharT, typename _Traits>
 484         friend std::basic_ostream<_CharT, _Traits>&
 485         operator<<(std::basic_ostream<_CharT, _Traits>&,
 486                    const std::mersenne_twister_engine<_UIntType1, __w1, __n1,
 487                    __m1, __r1, __a1, __u1, __d1, __s1, __b1, __t1, __c1,
 488                    __l1, __f1>&);
 489
 490       /**
 491        * @brief Extracts the current state of a % mersenne_twister_engine
 492        *        random number generator engine @p __x from the input stream
 493        *        @p __is.
 494        *
 495        * @param __is An input stream.
 496        * @param __x  A % mersenne_twister_engine random number generator
 497        *             engine.
 498        *
 499        * @returns The input stream with the state of @p __x extracted or in
 500        * an error state.
 501        */
 502       template<typename _UIntType1,
 503                size_t __w1, size_t __n1,
 504                size_t __m1, size_t __r1,
 505                _UIntType1 __a1, size_t __u1,
 506                _UIntType1 __d1, size_t __s1,
 507                _UIntType1 __b1, size_t __t1,
 508                _UIntType1 __c1, size_t __l1, _UIntType1 __f1,
 509                typename _CharT, typename _Traits>
 510         friend std::basic_istream<_CharT, _Traits>&
 511         operator>>(std::basic_istream<_CharT, _Traits>&,
 512                    std::mersenne_twister_engine<_UIntType1, __w1, __n1, __m1,
 513                    __r1, __a1, __u1, __d1, __s1, __b1, __t1, __c1,
 514                    __l1, __f1>&);
 515
 516     private:
 517       _UIntType _M_x[state_size];
 518       size_t    _M_p;
 519     };
 520
 521   /**
 522    * @brief The Marsaglia-Zaman generator.
 523    *
 524    * This is a model of a Generalized Fibonacci discrete random number
 525    * generator, sometimes referred to as the SWC generator.
 526    *
 527    * A discrete random number generator that produces pseudorandom
 528    * numbers using @f$x_{i}\leftarrow(x_{i - s} - x_{i - r} -
 529    * carry_{i-1}) \bmod m @f$.
 530    *
 531    * The size of the state is @f$ r @f$
 532    * and the maximum period of the generator is @f$ m^r - m^s - 1 @f$.
 533    *
 534    * @var _M_x     The state of the generator.  This is a ring buffer.
 535    * @var _M_carry The carry.
 536    * @var _M_p     Current index of x(i - r).
 537    */
 538   template<typename _UIntType, size_t __w, size_t __s, size_t __r>
 539     class subtract_with_carry_engine
 540     {
 541       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
 542       static_assert(__s > 0U && __r > __s
 543                     && __w > 0U
 544                     && __w <= static_cast<size_t>
 545                     (std::numeric_limits<_UIntType>::digits),
 546                     "template arguments out of bounds"
 547                     " in subtract_with_carry_engine");
 548
 549     public:
 550       /** The type of the generated random value. */
 551       typedef _UIntType result_type;
 552
 553       // parameter values
 554       static const size_t      word_size    = __w;
 555       static const size_t      short_lag    = __s;
 556       static const size_t      long_lag     = __r;
 557       static const result_type default_seed = 19780503u;
 558
 559       /**
 560        * @brief Constructs an explicitly seeded % subtract_with_carry_engine
 561        *        random number generator.
 562        */
 563       explicit
 564       subtract_with_carry_engine(result_type __sd = default_seed)
 565       { this->seed(__sd); }
 566
 567       /**
 568        * @brief Constructs a %subtract_with_carry_engine random number engine
 569        *        seeded from the seed sequence @p __q.
 570        *
 571        * @param __q the seed sequence.
 572        */
 573       explicit
 574       subtract_with_carry_engine(seed_seq& __q)
 575       { this->seed(__q); }
 576
 577       /**
 578        * @brief Seeds the initial state @f$ x_0 @f$ of the random number
 579        *        generator.
 580        *
 581        * N1688[4.19] modifies this as follows.  If @p __value == 0,
 582        * sets value to 19780503.  In any case, with a linear
 583        * congruential generator lcg(i) having parameters @f$ m_{lcg} =
 584        * 2147483563, a_{lcg} = 40014, c_{lcg} = 0, and lcg(0) = value
 585        * @f$, sets @f$ x_{-r} \dots x_{-1} @f$ to @f$ lcg(1) \bmod m
 586        * \dots lcg(r) \bmod m @f$ respectively.  If @f$ x_{-1} = 0 @f$
 587        * set carry to 1, otherwise sets carry to 0.
 588        */
 589       void
 590       seed(result_type __sd = default_seed);
 591
 592       /**
 593        * @brief Seeds the initial state @f$ x_0 @f$ of the
 594        * % subtract_with_carry_engine random number generator.
 595        */
 596       void
 597       seed(seed_seq& __q);
 598
 599       /**
 600        * @brief Gets the inclusive minimum value of the range of random
 601        * integers returned by this generator.
 602        *
 603        * @todo This should be constexpr.
 604        */
 605       result_type
 606       min() const
 607       { return 0; }
 608
 609       /**
 610        * @brief Gets the inclusive maximum value of the range of random
 611        * integers returned by this generator.
 612        *
 613        * @todo This should be constexpr.
 614        */
 615       result_type
 616       max() const
 617       { return __detail::_Shift<_UIntType, __w>::__value - 1; }
 618
 619       /**
 620        * @brief Discard a sequence of random numbers.
 621        *
 622        * @todo Look for a faster way to do discard.
 623        */
 624       void
 625       discard(unsigned long long __z)
 626       {
 627         for (; __z != 0ULL; --__z)
 628           (*this)();
 629       }
 630
 631       /**
 632        * @brief Gets the next random number in the sequence.
 633        */
 634       result_type
 635       operator()();
 636
 637       /**
 638        * @brief Compares two % subtract_with_carry_engine random number
 639        *        generator objects of the same type for equality.
 640        *
 641        * @param __lhs A % subtract_with_carry_engine random number generator
 642        *              object.
 643        * @param __rhs Another % subtract_with_carry_engine random number
 644        *              generator object.
 645        *
 646        * @returns true if the two objects are equal, false otherwise.
 647        */
 648       friend bool
 649       operator==(const subtract_with_carry_engine& __lhs,
 650                  const subtract_with_carry_engine& __rhs)
 651       { return std::equal(__lhs._M_x, __lhs._M_x + long_lag, __rhs._M_x); }
 652
 653       /**
 654        * @brief Inserts the current state of a % subtract_with_carry_engine
 655        *        random number generator engine @p __x into the output stream
 656        *        @p __os.
 657        *
 658        * @param __os An output stream.
 659        * @param __x  A % subtract_with_carry_engine random number generator
 660        *             engine.
 661        *
 662        * @returns The output stream with the state of @p __x inserted or in
 663        * an error state.
 664        */
 665       template<typename _UIntType1, size_t __w1, size_t __s1, size_t __r1,
 666                typename _CharT, typename _Traits>
 667         friend std::basic_ostream<_CharT, _Traits>&
 668         operator<<(std::basic_ostream<_CharT, _Traits>&,
 669                    const std::subtract_with_carry_engine<_UIntType1, __w1,
 670                    __s1, __r1>&);
 671
 672       /**
 673        * @brief Extracts the current state of a % subtract_with_carry_engine
 674        *        random number generator engine @p __x from the input stream
 675        *        @p __is.
 676        *
 677        * @param __is An input stream.
 678        * @param __x  A % subtract_with_carry_engine random number generator engine.
 679        *
 680        * @returns The input stream with the state of @p __x extracted or in
 681        * an error state.
 682        */
 683       template<typename _UIntType1, size_t __w1, size_t __s1, size_t __r1,
 684                typename _CharT, typename _Traits>
 685         friend std::basic_istream<_CharT, _Traits>&
 686         operator>>(std::basic_istream<_CharT, _Traits>&,
 687                    std::subtract_with_carry_engine<_UIntType1, __w1,
 688                    __s1, __r1>&);
 689
 690     private:
 691       _UIntType  _M_x[long_lag];
 692       _UIntType  _M_carry;
 693       size_t     _M_p;
 694     };
 695
 696   /**
 697    * Produces random numbers from some base engine by discarding blocks of
 698    * data.
 699    *
 700    * 0 <= @p __r <= @p __p
 701    */
 702   template<typename _RandomNumberEngine, size_t __p, size_t __r>
 703     class discard_block_engine
 704     {
 705       static_assert(__r >= 1U && __p >= __r,
 706                     "template arguments out of bounds"
 707                     " in discard_block_engine");
 708
 709     public:
 710       /** The type of the generated random value. */
 711       typedef typename _RandomNumberEngine::result_type result_type;
 712
 713       // parameter values
 714       static const size_t block_size = __p;
 715       static const size_t used_block = __r;
 716
 717       /**
 718        * @brief Constructs a default %discard_block_engine engine.
 719        *
 720        * The underlying engine is default constructed as well.
 721        */
 722       discard_block_engine()
 723       : _M_b(), _M_n(0) { }
 724
 725       /**
 726        * @brief Copy constructs a %discard_block_engine engine.
 727        *
 728        * Copies an existing base class random number generator.
 729        * @param rng An existing (base class) engine object.
 730        */
 731       explicit
 732       discard_block_engine(const _RandomNumberEngine& __rne)
 733       : _M_b(__rne), _M_n(0) { }
 734
 735       /**
 736        * @brief Move constructs a %discard_block_engine engine.
 737        *
 738        * Copies an existing base class random number generator.
 739        * @param rng An existing (base class) engine object.
 740        */
 741       explicit
 742       discard_block_engine(_RandomNumberEngine&& __rne)
 743       : _M_b(std::move(__rne)), _M_n(0) { }
 744
 745       /**
 746        * @brief Seed constructs a %discard_block_engine engine.
 747        *
 748        * Constructs the underlying generator engine seeded with @p __s.
 749        * @param __s A seed value for the base class engine.
 750        */
 751       explicit
 752       discard_block_engine(result_type __s)
 753       : _M_b(__s), _M_n(0) { }
 754
 755       /**
 756        * @brief Generator construct a %discard_block_engine engine.
 757        *
 758        * @param __q A seed sequence.
 759        */
 760       explicit
 761       discard_block_engine(seed_seq& __q)
 762       : _M_b(__q), _M_n(0)
 763       { }
 764
 765       /**
 766        * @brief Reseeds the %discard_block_engine object with the default
 767        *        seed for the underlying base class generator engine.
 768        */
 769       void
 770       seed()
 771       {
 772         _M_b.seed();
 773         _M_n = 0;
 774       }
 775
 776       /**
 777        * @brief Reseeds the %discard_block_engine object with the default
 778        *        seed for the underlying base class generator engine.
 779        */
 780       void
 781       seed(result_type __s)
 782       {
 783         _M_b.seed(__s);
 784         _M_n = 0;
 785       }
 786
 787       /**
 788        * @brief Reseeds the %discard_block_engine object with the given seed
 789        *        sequence.
 790        * @param __q A seed generator function.
 791        */
 792       void
 793       seed(seed_seq& __q)
 794       {
 795         _M_b.seed(__q);
 796         _M_n = 0;
 797       }
 798
 799       /**
 800        * @brief Gets a const reference to the underlying generator engine
 801        *        object.
 802        */
 803       const _RandomNumberEngine&
 804       base() const
 805       { return _M_b; }
 806
 807       /**
 808        * @brief Gets the minimum value in the generated random number range.
 809        *
 810        * @todo This should be constexpr.
 811        */
 812       result_type
 813       min() const
 814       { return _M_b.min(); }
 815
 816       /**
 817        * @brief Gets the maximum value in the generated random number range.
 818        *
 819        * @todo This should be constexpr.
 820        */
 821       result_type
 822       max() const
 823       { return _M_b.max(); }
 824
 825       /**
 826        * @brief Discard a sequence of random numbers.
 827        *
 828        * @todo Look for a faster way to do discard.
 829        */
 830       void
 831       discard(unsigned long long __z)
 832       {
 833         for (; __z != 0ULL; --__z)
 834           (*this)();
 835       }
 836
 837       /**
 838        * @brief Gets the next value in the generated random number sequence.
 839        */
 840       result_type
 841       operator()();
 842
 843       /**
 844        * @brief Compares two %discard_block_engine random number generator
 845        *        objects of the same type for equality.
 846        *
 847        * @param __lhs A %discard_block_engine random number generator object.
 848        * @param __rhs Another %discard_block_engine random number generator
 849        *              object.
 850        *
 851        * @returns true if the two objects are equal, false otherwise.
 852        */
 853       friend bool
 854       operator==(const discard_block_engine& __lhs,
 855                  const discard_block_engine& __rhs)
 856       { return (__lhs._M_b == __rhs._M_b) && (__lhs._M_n == __rhs._M_n); }
 857
 858       /**
 859        * @brief Inserts the current state of a %discard_block_engine random
 860        *        number generator engine @p __x into the output stream
 861        *        @p __os.
 862        *
 863        * @param __os An output stream.
 864        * @param __x  A %discard_block_engine random number generator engine.
 865        *
 866        * @returns The output stream with the state of @p __x inserted or in
 867        * an error state.
 868        */
 869       template<typename _RandomNumberEngine1, size_t __p1, size_t __r1,
 870                typename _CharT, typename _Traits>
 871         friend std::basic_ostream<_CharT, _Traits>&
 872         operator<<(std::basic_ostream<_CharT, _Traits>&,
 873                    const std::discard_block_engine<_RandomNumberEngine1,
 874                    __p1, __r1>&);
 875
 876       /**
 877        * @brief Extracts the current state of a % subtract_with_carry_engine
 878        *        random number generator engine @p __x from the input stream
 879        *        @p __is.
 880        *
 881        * @param __is An input stream.
 882        * @param __x  A %discard_block_engine random number generator engine.
 883        *
 884        * @returns The input stream with the state of @p __x extracted or in
 885        * an error state.
 886        */
 887       template<typename _RandomNumberEngine1, size_t __p1, size_t __r1,
 888                typename _CharT, typename _Traits>
 889         friend std::basic_istream<_CharT, _Traits>&
 890         operator>>(std::basic_istream<_CharT, _Traits>&,
 891                    std::discard_block_engine<_RandomNumberEngine1,
 892                    __p1, __r1>&);
 893
 894     private:
 895       _RandomNumberEngine _M_b;
 896       size_t _M_n;
 897     };
 898
 899   /**
 900    * Produces random numbers by combining random numbers from some base
 901    * engine to produce random numbers with a specifies number of bits @p __w.
 902    */
 903   template<typename _RandomNumberEngine, size_t __w, typename _UIntType>
 904     class independent_bits_engine
 905     {
 906       static_assert(__w > 0U
 907                     && __w <=
 908                     static_cast<size_t>
 909                     (std::numeric_limits<_UIntType>::digits),
 910                     "template arguments out of bounds "
 911                     "in independent_bits_engine");
 912
 913     public:
 914       /** The type of the generated random value. */
 915       typedef _UIntType result_type;
 916
 917       /**
 918        * @brief Constructs a default %independent_bits_engine engine.
 919        *
 920        * The underlying engine is default constructed as well.
 921        */
 922       independent_bits_engine()
 923       : _M_b() { }
 924
 925       /**
 926        * @brief Copy constructs a %independent_bits_engine engine.
 927        *
 928        * Copies an existing base class random number generator.
 929        * @param rng An existing (base class) engine object.
 930        */
 931       explicit
 932       independent_bits_engine(const _RandomNumberEngine& __rne)
 933       : _M_b(__rne) { }
 934
 935       /**
 936        * @brief Move constructs a %independent_bits_engine engine.
 937        *
 938        * Copies an existing base class random number generator.
 939        * @param rng An existing (base class) engine object.
 940        */
 941       explicit
 942       independent_bits_engine(_RandomNumberEngine&& __rne)
 943       : _M_b(std::move(__rne)) { }
 944
 945       /**
 946        * @brief Seed constructs a %independent_bits_engine engine.
 947        *
 948        * Constructs the underlying generator engine seeded with @p __s.
 949        * @param __s A seed value for the base class engine.
 950        */
 951       explicit
 952       independent_bits_engine(result_type __s)
 953       : _M_b(__s) { }
 954
 955       /**
 956        * @brief Generator construct a %independent_bits_engine engine.
 957        *
 958        * @param __q A seed sequence.
 959        */
 960       explicit
 961       independent_bits_engine(seed_seq& __q)
 962       : _M_b(__q)
 963       { }
 964
 965       /**
 966        * @brief Reseeds the %independent_bits_engine object with the default
 967        *        seed for the underlying base class generator engine.
 968        */
 969       void
 970       seed()
 971       { _M_b.seed(); }
 972
 973       /**
 974        * @brief Reseeds the %independent_bits_engine object with the default
 975        *        seed for the underlying base class generator engine.
 976        */
 977       void
 978       seed(result_type __s)
 979       { _M_b.seed(__s); }
 980
 981       /**
 982        * @brief Reseeds the %independent_bits_engine object with the given
 983        *        seed sequence.
 984        * @param __q A seed generator function.
 985        */
 986       void
 987       seed(seed_seq& __q)
 988       { _M_b.seed(__q); }
 989
 990       /**
 991        * @brief Gets a const reference to the underlying generator engine
 992        *        object.
 993        */
 994       const _RandomNumberEngine&
 995       base() const
 996       { return _M_b; }
 997
 998       /**
 999        * @brief Gets the minimum value in the generated random number range.
1000        *
1001        * @todo This should be constexpr.
1002        */
1003       result_type
1004       min() const
1005       { return 0U; }
1006
1007       /**
1008        * @brief Gets the maximum value in the generated random number range.
1009        *
1010        * @todo This should be constexpr.
1011        */
1012       result_type
1013       max() const
1014       { return __detail::_Shift<_UIntType, __w>::__value - 1; }
1015
1016       /**
1017        * @brief Discard a sequence of random numbers.
1018        *
1019        * @todo Look for a faster way to do discard.
1020        */
1021       void
1022       discard(unsigned long long __z)
1023       {
1024         for (; __z != 0ULL; --__z)
1025           (*this)();
1026       }
1027
1028       /**
1029        * @brief Gets the next value in the generated random number sequence.
1030        */
1031       result_type
1032       operator()();
1033
1034       /**
1035        * @brief Compares two %independent_bits_engine random number generator
1036        * objects of the same type for equality.
1037        *
1038        * @param __lhs A %independent_bits_engine random number generator
1039        *              object.
1040        * @param __rhs Another %independent_bits_engine random number generator
1041        *              object.
1042        *
1043        * @returns true if the two objects are equal, false otherwise.
1044        */
1045       friend bool
1046       operator==(const independent_bits_engine& __lhs,
1047                  const independent_bits_engine& __rhs)
1048       { return __lhs._M_b == __rhs._M_b; }
1049
1050       /**
1051        * @brief Extracts the current state of a % subtract_with_carry_engine
1052        *        random number generator engine @p __x from the input stream
1053        *        @p __is.
1054        *
1055        * @param __is An input stream.
1056        * @param __x  A %independent_bits_engine random number generator
1057        *             engine.
1058        *
1059        * @returns The input stream with the state of @p __x extracted or in
1060        *          an error state.
1061        */
1062       template<typename _CharT, typename _Traits>
1063         friend std::basic_istream<_CharT, _Traits>&
1064         operator>>(std::basic_istream<_CharT, _Traits>& __is,
1065                    std::independent_bits_engine<_RandomNumberEngine,
1066                    __w, _UIntType>& __x)
1067         {
1068           __is >> __x._M_b;
1069           return __is;
1070         }
1071
1072     private:
1073       _RandomNumberEngine _M_b;
1074     };
1075
1076   /**
1077    * @brief Inserts the current state of a %independent_bits_engine random
1078    *        number generator engine @p __x into the output stream @p __os.
1079    *
1080    * @param __os An output stream.
1081    * @param __x  A %independent_bits_engine random number generator engine.
1082    *
1083    * @returns The output stream with the state of @p __x inserted or in
1084    *          an error state.
1085    */
1086   template<typename _RandomNumberEngine, size_t __w, typename _UIntType,
1087            typename _CharT, typename _Traits>
1088     std::basic_ostream<_CharT, _Traits>&
1089     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1090                const std::independent_bits_engine<_RandomNumberEngine,
1091                __w, _UIntType>& __x)
1092     {
1093       __os << __x.base();
1094       return __os;
1095     }
1096
1097   /**
1098    * @brief Produces random numbers by combining random numbers from some
1099    * base engine to produce random numbers with a specifies number of bits
1100    * @p __w.
1101    */
1102   template<typename _RandomNumberEngine, size_t __k>
1103     class shuffle_order_engine
1104     {
1105       static_assert(__k >= 1U,
1106                     "template arguments out of bounds"
1107                     " in shuffle_order_engine");
1108
1109     public:
1110       /** The type of the generated random value. */
1111       typedef typename _RandomNumberEngine::result_type result_type;
1112
1113       static const size_t table_size = __k;
1114
1115       /**
1116        * @brief Constructs a default %shuffle_order_engine engine.
1117        *
1118        * The underlying engine is default constructed as well.
1119        */
1120       shuffle_order_engine()
1121       : _M_b()
1122       { _M_initialize(); }
1123
1124       /**
1125        * @brief Copy constructs a %shuffle_order_engine engine.
1126        *
1127        * Copies an existing base class random number generator.
1128        * @param rng An existing (base class) engine object.
1129        */
1130       explicit
1131       shuffle_order_engine(const _RandomNumberEngine& __rne)
1132       : _M_b(__rne)
1133       { _M_initialize(); }
1134
1135       /**
1136        * @brief Move constructs a %shuffle_order_engine engine.
1137        *
1138        * Copies an existing base class random number generator.
1139        * @param rng An existing (base class) engine object.
1140        */
1141       explicit
1142       shuffle_order_engine(_RandomNumberEngine&& __rne)
1143       : _M_b(std::move(__rne))
1144       { _M_initialize(); }
1145
1146       /**
1147        * @brief Seed constructs a %shuffle_order_engine engine.
1148        *
1149        * Constructs the underlying generator engine seeded with @p __s.
1150        * @param __s A seed value for the base class engine.
1151        */
1152       explicit
1153       shuffle_order_engine(result_type __s)
1154       : _M_b(__s)
1155       { _M_initialize(); }
1156
1157       /**
1158        * @brief Generator construct a %shuffle_order_engine engine.
1159        *
1160        * @param __q A seed sequence.
1161        */
1162       explicit
1163       shuffle_order_engine(seed_seq& __q)
1164       : _M_b(__q)
1165       { _M_initialize(); }
1166
1167       /**
1168        * @brief Reseeds the %shuffle_order_engine object with the default seed
1169                 for the underlying base class generator engine.
1170        */
1171       void
1172       seed()
1173       {
1174         _M_b.seed();
1175         _M_initialize();
1176       }
1177
1178       /**
1179        * @brief Reseeds the %shuffle_order_engine object with the default seed
1180        *        for the underlying base class generator engine.
1181        */
1182       void
1183       seed(result_type __s)
1184       {
1185         _M_b.seed(__s);
1186         _M_initialize();
1187       }
1188
1189       /**
1190        * @brief Reseeds the %shuffle_order_engine object with the given seed
1191        *        sequence.
1192        * @param __q A seed generator function.
1193        */
1194       void
1195       seed(seed_seq& __q)
1196       {
1197         _M_b.seed(__q);
1198         _M_initialize();
1199       }
1200
1201       /**
1202        * Gets a const reference to the underlying generator engine object.
1203        */
1204       const _RandomNumberEngine&
1205       base() const
1206       { return _M_b; }
1207
1208       /**
1209        * Gets the minimum value in the generated random number range.
1210        *
1211        * @todo This should be constexpr.
1212        */
1213       result_type
1214       min() const
1215       { return _M_b.min(); }
1216
1217       /**
1218        * Gets the maximum value in the generated random number range.
1219        *
1220        * @todo This should be constexpr.
1221        */
1222       result_type
1223       max() const
1224       { return _M_b.max(); }
1225
1226       /**
1227        * Discard a sequence of random numbers.
1228        *
1229        * @todo Look for a faster way to do discard.
1230        */
1231       void
1232       discard(unsigned long long __z)
1233       {
1234         for (; __z != 0ULL; --__z)
1235           (*this)();
1236       }
1237
1238       /**
1239        * Gets the next value in the generated random number sequence.
1240        */
1241       result_type
1242       operator()();
1243
1244       /**
1245        * Compares two %shuffle_order_engine random number generator objects
1246        * of the same type for equality.
1247        *
1248        * @param __lhs A %shuffle_order_engine random number generator object.
1249        * @param __rhs Another %shuffle_order_engine random number generator
1250        *              object.
1251        *
1252        * @returns true if the two objects are equal, false otherwise.
1253        */
1254       friend bool
1255       operator==(const shuffle_order_engine& __lhs,
1256                  const shuffle_order_engine& __rhs)
1257       { return __lhs._M_b == __rhs._M_b; }
1258
1259       /**
1260        * @brief Inserts the current state of a %shuffle_order_engine random
1261        *        number generator engine @p __x into the output stream
1262         @p __os.
1263        *
1264        * @param __os An output stream.
1265        * @param __x  A %shuffle_order_engine random number generator engine.
1266        *
1267        * @returns The output stream with the state of @p __x inserted or in
1268        * an error state.
1269        */
1270       template<typename _RandomNumberEngine1, size_t __k1,
1271                typename _CharT, typename _Traits>
1272         friend std::basic_ostream<_CharT, _Traits>&
1273         operator<<(std::basic_ostream<_CharT, _Traits>&,
1274                    const std::shuffle_order_engine<_RandomNumberEngine1,
1275                    __k1>&);
1276
1277       /**
1278        * @brief Extracts the current state of a % subtract_with_carry_engine
1279        *        random number generator engine @p __x from the input stream
1280        *        @p __is.
1281        *
1282        * @param __is An input stream.
1283        * @param __x  A %shuffle_order_engine random number generator engine.
1284        *
1285        * @returns The input stream with the state of @p __x extracted or in
1286        * an error state.
1287        */
1288       template<typename _RandomNumberEngine1, size_t __k1,
1289                typename _CharT, typename _Traits>
1290         friend std::basic_istream<_CharT, _Traits>&
1291         operator>>(std::basic_istream<_CharT, _Traits>&,
1292                    std::shuffle_order_engine<_RandomNumberEngine1, __k1>&);
1293
1294     private:
1295       void _M_initialize()
1296       {
1297         for (size_t __i = 0; __i < __k; ++__i)
1298           _M_v[__i] = _M_b();
1299         _M_y = _M_b();
1300       }
1301
1302       _RandomNumberEngine _M_b;
1303       result_type _M_v[__k];
1304       result_type _M_y;
1305     };
1306
1307   /**
1308    * The classic Minimum Standard rand0 of Lewis, Goodman, and Miller.
1309    */
1310   typedef linear_congruential_engine<uint_fast32_t, 16807UL, 0UL, 2147483647UL>
1311   minstd_rand0;
1312
1313   /**
1314    * An alternative LCR (Lehmer Generator function) .
1315    */
1316   typedef linear_congruential_engine<uint_fast32_t, 48271UL, 0UL, 2147483647UL>
1317   minstd_rand;
1318
1319   /**
1320    * The classic Mersenne Twister.
1321    *
1322    * Reference:
1323    * M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
1324    * Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions
1325    * on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
1326    */
1327   typedef mersenne_twister_engine<
1328     uint_fast32_t,
1329     32, 624, 397, 31,
1330     0x9908b0dfUL, 11,
1331     0xffffffffUL, 7,
1332     0x9d2c5680UL, 15,
1333     0xefc60000UL, 18, 1812433253UL> mt19937;
1334
1335   /**
1336    * An alternative Mersenne Twister.
1337    */
1338   typedef mersenne_twister_engine<
1339     uint_fast64_t,
1340     64, 312, 156, 31,
1341     0xb5026f5aa96619e9ULL, 29,
1342     0x5555555555555555ULL, 17,
1343     0x71d67fffeda60000ULL, 37,
1344     0xfff7eee000000000ULL, 43,
1345     6364136223846793005ULL> mt19937_64;
1346
1347   /**
1348    * .
1349    */
1350   typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24>
1351     ranlux24_base;
1352
1353   typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12>
1354     ranlux48_base;
1355
1356   typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
1357
1358   typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
1359
1360   /**
1361    * .
1362    */
1363   typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
1364
1365   /**
1366    * .
1367    */
1368   typedef minstd_rand0 default_random_engine;
1369
1370   /**
1371    * A standard interface to a platform-specific non-deterministic
1372    * random number generator (if any are available).
1373    */
1374   class random_device
1375   {
1376   public:
1377     /** The type of the generated random value. */
1378     typedef unsigned int result_type;
1379
1380     // constructors, destructors and member functions
1381
1382 #ifdef _GLIBCXX_USE_RANDOM_TR1
1383
1384     explicit
1385     random_device(const std::string& __token = "/dev/urandom")
1386     {
1387       if ((__token != "/dev/urandom" && __token != "/dev/random")
1388           || !(_M_file = std::fopen(__token.c_str(), "rb")))
1389         std::__throw_runtime_error(__N("random_device::"
1390                                        "random_device(const std::string&)"));
1391     }
1392
1393     ~random_device()
1394     { std::fclose(_M_file); }
1395
1396 #else
1397
1398     explicit
1399     random_device(const std::string& __token = "mt19937")
1400     : _M_mt(_M_strtoul(__token)) { }
1401
1402   private:
1403     static unsigned long
1404     _M_strtoul(const std::string& __str)
1405     {
1406       unsigned long __ret = 5489UL;
1407       if (__str != "mt19937")
1408         {
1409           const char* __nptr = __str.c_str();
1410           char* __endptr;
1411           __ret = std::strtoul(__nptr, &__endptr, 0);
1412           if (*__nptr == '\0' || *__endptr != '\0')
1413             std::__throw_runtime_error(__N("random_device::_M_strtoul"
1414                                            "(const std::string&)"));
1415         }
1416       return __ret;
1417     }
1418
1419   public:
1420
1421 #endif
1422
1423     result_type
1424     min() const
1425     { return std::numeric_limits<result_type>::min(); }
1426
1427     result_type
1428     max() const
1429     { return std::numeric_limits<result_type>::max(); }
1430
1431     double
1432     entropy() const
1433     { return 0.0; }
1434
1435     result_type
1436     operator()()
1437     {
1438 #ifdef _GLIBCXX_USE_RANDOM_TR1
1439       result_type __ret;
1440       std::fread(reinterpret_cast<void*>(&__ret), sizeof(result_type),
1441                  1, _M_file);
1442       return __ret;
1443 #else
1444       return _M_mt();
1445 #endif
1446     }
1447
1448     // No copy functions.
1449     random_device(const random_device&) = delete;
1450     void operator=(const random_device&) = delete;
1451
1452   private:
1453
1454 #ifdef _GLIBCXX_USE_RANDOM_TR1
1455     FILE*        _M_file;
1456 #else
1457     mt19937      _M_mt;
1458 #endif
1459   };
1460
1461   /* @} */ // group std_random_generators
1462
1463   /**
1464    * @addtogroup std_random_distributions Random Number Distributions
1465    * @ingroup std_random
1466    * @{
1467    */
1468
1469   /**
1470    * @addtogroup std_random_distributions_uniform Uniform Distributions
1471    * @ingroup std_random_distributions
1472    * @{
1473    */
1474
1475   /**
1476    * @brief Uniform discrete distribution for random numbers.
1477    * A discrete random distribution on the range @f$[min, max]@f$ with equal
1478    * probability throughout the range.
1479    */
1480   template<typename _IntType = int>
1481     class uniform_int_distribution
1482     {
1483       __glibcxx_class_requires(_IntType, _IntegerConcept)
1484
1485     public:
1486       /** The type of the range of the distribution. */
1487       typedef _IntType result_type;
1488       /** Parameter type. */
1489       struct param_type
1490       {
1491         typedef uniform_int_distribution<_IntType> distribution_type;
1492
1493         explicit
1494         param_type(_IntType __a = 0,
1495                    _IntType __b = std::numeric_limits<_IntType>::max())
1496         : _M_a(__a), _M_b(__b)
1497         {
1498           _GLIBCXX_DEBUG_ASSERT(_M_a <= _M_b);
1499         }
1500
1501         result_type
1502         a() const
1503         { return _M_a; }
1504
1505         result_type
1506         b() const
1507         { return _M_b; }
1508
1509       private:
1510         _IntType _M_a;
1511         _IntType _M_b;
1512       };
1513
1514     public:
1515       /**
1516        * @brief Constructs a uniform distribution object.
1517        */
1518       explicit
1519       uniform_int_distribution(_IntType __a = 0,
1520                            _IntType __b = std::numeric_limits<_IntType>::max())
1521       : _M_param(__a, __b)
1522       { }
1523
1524       explicit
1525       uniform_int_distribution(const param_type& __p)
1526       : _M_param(__p)
1527       { }
1528
1529       /**
1530        * @brief Resets the distribution state.
1531        *
1532        * Does nothing for the uniform integer distribution.
1533        */
1534       void
1535       reset() { }
1536
1537       result_type
1538       a() const
1539       { return _M_param.a(); }
1540
1541       result_type
1542       b() const
1543       { return _M_param.b(); }
1544
1545       /**
1546        * @brief Returns the inclusive lower bound of the distribution range.
1547        */
1548       result_type
1549       min() const
1550       { return this->a(); }
1551
1552       /**
1553        * @brief Returns the inclusive upper bound of the distribution range.
1554        */
1555       result_type
1556       max() const
1557       { return this->b(); }
1558
1559       /**
1560        * @brief Returns the parameter set of the distribution.
1561        */
1562       param_type
1563       param() const
1564       { return _M_param; }
1565
1566       /**
1567        * @brief Sets the parameter set of the distribution.
1568        * @param __param The new parameter set of the distribution.
1569        */
1570       void
1571       param(const param_type& __param)
1572       { _M_param = __param; }
1573
1574       /**
1575        * Gets a uniformly distributed random number in the range
1576        * @f$(min, max)@f$.
1577        */
1578       template<typename _UniformRandomNumberGenerator>
1579         result_type
1580         operator()(_UniformRandomNumberGenerator& __urng)
1581         { return this->operator()(__urng, this->param()); }
1582
1583       /**
1584        * Gets a uniform random number in the range @f$[0, n)@f$.
1585        *
1586        * This function is aimed at use with std::random_shuffle.
1587        */
1588       template<typename _UniformRandomNumberGenerator>
1589         result_type
1590         operator()(_UniformRandomNumberGenerator& __urng,
1591                    const param_type& __p);
1592
1593       param_type _M_param;
1594     };
1595
1596   /**
1597    * @brief Inserts a %uniform_int_distribution random number
1598    *        distribution @p __x into the output stream @p os.
1599    *
1600    * @param __os An output stream.
1601    * @param __x  A %uniform_int_distribution random number distribution.
1602    *
1603    * @returns The output stream with the state of @p __x inserted or in
1604    * an error state.
1605    */
1606   template<typename _IntType, typename _CharT, typename _Traits>
1607     std::basic_ostream<_CharT, _Traits>&
1608     operator<<(std::basic_ostream<_CharT, _Traits>&,
1609                const std::uniform_int_distribution<_IntType>&);
1610
1611   /**
1612    * @brief Extracts a %uniform_int_distribution random number distribution
1613    * @p __x from the input stream @p __is.
1614    *
1615    * @param __is An input stream.
1616    * @param __x  A %uniform_int_distribution random number generator engine.
1617    *
1618    * @returns The input stream with @p __x extracted or in an error state.
1619    */
1620   template<typename _IntType, typename _CharT, typename _Traits>
1621     std::basic_istream<_CharT, _Traits>&
1622     operator>>(std::basic_istream<_CharT, _Traits>&,
1623                std::uniform_int_distribution<_IntType>&);
1624
1625
1626   /**
1627    * @brief Uniform continuous distribution for random numbers.
1628    *
1629    * A continuous random distribution on the range [min, max) with equal
1630    * probability throughout the range.  The URNG should be real-valued and
1631    * deliver number in the range [0, 1).
1632    */
1633   template<typename _RealType = double>
1634     class uniform_real_distribution
1635     {
1636     public:
1637       /** The type of the range of the distribution. */
1638       typedef _RealType result_type;
1639       /** Parameter type. */
1640       struct param_type
1641       {
1642         typedef uniform_real_distribution<_RealType> distribution_type;
1643
1644         explicit
1645         param_type(_RealType __a = _RealType(0),
1646                    _RealType __b = _RealType(1))
1647         : _M_a(__a), _M_b(__b)
1648         {
1649           _GLIBCXX_DEBUG_ASSERT(_M_a <= _M_b);
1650         }
1651
1652         result_type
1653         a() const
1654         { return _M_a; }
1655
1656         result_type
1657         b() const
1658         { return _M_b; }
1659
1660       private:
1661         _RealType _M_a;
1662         _RealType _M_b;
1663       };
1664
1665     public:
1666       /**
1667        * @brief Constructs a uniform_real_distribution object.
1668        *
1669        * @param __min [IN]  The lower bound of the distribution.
1670        * @param __max [IN]  The upper bound of the distribution.
1671        */
1672       explicit
1673       uniform_real_distribution(_RealType __a = _RealType(0),
1674                                 _RealType __b = _RealType(1))
1675       : _M_param(__a, __b)
1676       { }
1677
1678       explicit
1679       uniform_real_distribution(const param_type& __p)
1680       : _M_param(__p)
1681       { }
1682
1683       /**
1684        * @brief Resets the distribution state.
1685        *
1686        * Does nothing for the uniform real distribution.
1687        */
1688       void
1689       reset() { }
1690
1691       result_type
1692       a() const
1693       { return _M_param.a(); }
1694
1695       result_type
1696       b() const
1697       { return _M_param.b(); }
1698
1699       /**
1700        * @brief Returns the inclusive lower bound of the distribution range.
1701        */
1702       result_type
1703       min() const
1704       { return this->a(); }
1705
1706       /**
1707        * @brief Returns the inclusive upper bound of the distribution range.
1708        */
1709       result_type
1710       max() const
1711       { return this->b(); }
1712
1713       /**
1714        * @brief Returns the parameter set of the distribution.
1715        */
1716       param_type
1717       param() const
1718       { return _M_param; }
1719
1720       /**
1721        * @brief Sets the parameter set of the distribution.
1722        * @param __param The new parameter set of the distribution.
1723        */
1724       void
1725       param(const param_type& __param)
1726       { _M_param = __param; }
1727
1728       template<typename _UniformRandomNumberGenerator>
1729         result_type
1730         operator()(_UniformRandomNumberGenerator& __urng)
1731         { return this->operator()(__urng, this->param()); }
1732
1733       template<typename _UniformRandomNumberGenerator>
1734         result_type
1735         operator()(_UniformRandomNumberGenerator& __urng,
1736                    const param_type& __p)
1737         {
1738           __detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
1739             __aurng(__urng);
1740           return (__aurng() * (__p.b() - __p.a())) + __p.a();
1741         }
1742
1743     private:
1744       param_type _M_param;
1745     };
1746
1747   /**
1748    * @brief Inserts a %uniform_real_distribution random number
1749    *        distribution @p __x into the output stream @p __os.
1750    *
1751    * @param __os An output stream.
1752    * @param __x  A %uniform_real_distribution random number distribution.
1753    *
1754    * @returns The output stream with the state of @p __x inserted or in
1755    *          an error state.
1756    */
1757   template<typename _RealType, typename _CharT, typename _Traits>
1758     std::basic_ostream<_CharT, _Traits>&
1759     operator<<(std::basic_ostream<_CharT, _Traits>&,
1760                const std::uniform_real_distribution<_RealType>&);
1761
1762   /**
1763    * @brief Extracts a %uniform_real_distribution random number distribution
1764    * @p __x from the input stream @p __is.
1765    *
1766    * @param __is An input stream.
1767    * @param __x  A %uniform_real_distribution random number generator engine.
1768    *
1769    * @returns The input stream with @p __x extracted or in an error state.
1770    */
1771   template<typename _RealType, typename _CharT, typename _Traits>
1772     std::basic_istream<_CharT, _Traits>&
1773     operator>>(std::basic_istream<_CharT, _Traits>&,
1774                std::uniform_real_distribution<_RealType>&);
1775
1776   /* @} */ // group std_random_distributions_uniform
1777
1778   /**
1779    * @addtogroup std_random_distributions_normal Normal Distributions
1780    * @ingroup std_random_distributions
1781    * @{
1782    */
1783
1784   /**
1785    * @brief A normal continuous distribution for random numbers.
1786    *
1787    * The formula for the normal probability density function is
1788    * @f$ p(x|\mu,\sigma) = \frac{1}{\sigma \sqrt{2 \pi}}
1789    *            e^{- \frac{{x - \mu}^ {2}}{2 \sigma ^ {2}} } @f$.
1790    */
1791   template<typename _RealType = double>
1792     class normal_distribution
1793     {
1794     public:
1795       /** The type of the range of the distribution. */
1796       typedef _RealType result_type;
1797       /** Parameter type. */
1798       struct param_type
1799       {
1800         typedef normal_distribution<_RealType> distribution_type;
1801
1802         explicit
1803         param_type(_RealType __mean = _RealType(0),
1804                    _RealType __stddev = _RealType(1))
1805         : _M_mean(__mean), _M_stddev(__stddev)
1806         {
1807           _GLIBCXX_DEBUG_ASSERT(_M_stddev > _RealType(0));
1808         }
1809
1810         _RealType
1811         mean() const
1812         { return _M_mean; }
1813
1814         _RealType
1815         stddev() const
1816         { return _M_stddev; }
1817
1818       private:
1819         _RealType _M_mean;
1820         _RealType _M_stddev;
1821       };
1822
1823     public:
1824       /**
1825        * Constructs a normal distribution with parameters @f$ mean @f$ and
1826        * standard deviation.
1827        */
1828       explicit
1829       normal_distribution(result_type __mean = result_type(0),
1830                           result_type __stddev = result_type(1))
1831       : _M_param(__mean, __stddev), _M_saved_available(false)
1832       { }
1833
1834       explicit
1835       normal_distribution(const param_type& __p)
1836       : _M_param(__p), _M_saved_available(false)
1837       { }
1838
1839       /**
1840        * @brief Resets the distribution state.
1841        */
1842       void
1843       reset()
1844       { _M_saved_available = false; }
1845
1846       /**
1847        * @brief Returns the mean of the distribution.
1848        */
1849       _RealType
1850       mean() const
1851       { return _M_param.mean(); }
1852
1853       /**
1854        * @brief Returns the standard deviation of the distribution.
1855        */
1856       _RealType
1857       stddev() const
1858       { return _M_param.stddev(); }
1859
1860       /**
1861        * @brief Returns the parameter set of the distribution.
1862        */
1863       param_type
1864       param() const
1865       { return _M_param; }
1866
1867       /**
1868        * @brief Sets the parameter set of the distribution.
1869        * @param __param The new parameter set of the distribution.
1870        */
1871       void
1872       param(const param_type& __param)
1873       { _M_param = __param; }
1874
1875       /**
1876        * @brief Returns the greatest lower bound value of the distribution.
1877        */
1878       result_type
1879       min() const
1880       { return std::numeric_limits<result_type>::min(); }
1881
1882       /**
1883        * @brief Returns the least upper bound value of the distribution.
1884        */
1885       result_type
1886       max() const
1887       { return std::numeric_limits<result_type>::max(); }
1888
1889       template<typename _UniformRandomNumberGenerator>
1890         result_type
1891         operator()(_UniformRandomNumberGenerator& __urng)
1892         { return this->operator()(__urng, this->param()); }
1893
1894       template<typename _UniformRandomNumberGenerator>
1895         result_type
1896         operator()(_UniformRandomNumberGenerator& __urng,
1897                    const param_type& __p);
1898
1899       /**
1900        * @brief Inserts a %normal_distribution random number distribution
1901        * @p __x into the output stream @p __os.
1902        *
1903        * @param __os An output stream.
1904        * @param __x  A %normal_distribution random number distribution.
1905        *
1906        * @returns The output stream with the state of @p __x inserted or in
1907        * an error state.
1908        */
1909       template<typename _RealType1, typename _CharT, typename _Traits>
1910         friend std::basic_ostream<_CharT, _Traits>&
1911         operator<<(std::basic_ostream<_CharT, _Traits>&,
1912                    const std::normal_distribution<_RealType1>&);
1913
1914       /**
1915        * @brief Extracts a %normal_distribution random number distribution
1916        * @p __x from the input stream @p __is.
1917        *
1918        * @param __is An input stream.
1919        * @param __x  A %normal_distribution random number generator engine.
1920        *
1921        * @returns The input stream with @p __x extracted or in an error
1922        *          state.
1923        */
1924       template<typename _RealType1, typename _CharT, typename _Traits>
1925         friend std::basic_istream<_CharT, _Traits>&
1926         operator>>(std::basic_istream<_CharT, _Traits>&,
1927                    std::normal_distribution<_RealType1>&);
1928
1929     private:
1930       param_type  _M_param;
1931       result_type _M_saved;
1932       bool        _M_saved_available;
1933     };
1934
1935
1936   /**
1937    * @brief A lognormal_distribution random number distribution.
1938    *
1939    * The formula for the normal probability mass function is
1940    * @f$ p(x|m,s) = \frac{1}{sx\sqrt{2\pi}}
1941    *             \exp{-\frac{(\ln{x} - m)^2}{2s^2}} @f$
1942    */
1943   template<typename _RealType = double>
1944     class lognormal_distribution
1945     {
1946     public:
1947       /** The type of the range of the distribution. */
1948       typedef _RealType result_type;
1949       /** Parameter type. */
1950       struct param_type
1951       {
1952         typedef lognormal_distribution<_RealType> distribution_type;
1953
1954         explicit
1955         param_type(_RealType __m = _RealType(0),
1956                    _RealType __s = _RealType(1))
1957         : _M_m(__m), _M_s(__s)
1958         { }
1959
1960         _RealType
1961         m() const
1962         { return _M_m; }
1963
1964         _RealType
1965         s() const
1966         { return _M_s; }
1967
1968       private:
1969         _RealType _M_m;
1970         _RealType _M_s;
1971       };
1972
1973       explicit
1974       lognormal_distribution(_RealType __m = _RealType(0),
1975                              _RealType __s = _RealType(1))
1976       : _M_param(__m, __s), _M_nd()
1977       { }
1978
1979       explicit
1980       lognormal_distribution(const param_type& __p)
1981       : _M_param(__p), _M_nd()
1982       { }
1983
1984       /**
1985        * Resets the distribution state.
1986        */
1987       void
1988       reset()
1989       { _M_nd.reset(); }
1990
1991       /**
1992        *
1993        */
1994       _RealType
1995       m() const
1996       { return _M_param.m(); }
1997
1998       _RealType
1999       s() const
2000       { return _M_param.s(); }
2001
2002       /**
2003        * @brief Returns the parameter set of the distribution.
2004        */
2005       param_type
2006       param() const
2007       { return _M_param; }
2008
2009       /**
2010        * @brief Sets the parameter set of the distribution.
2011        * @param __param The new parameter set of the distribution.
2012        */
2013       void
2014       param(const param_type& __param)
2015       { _M_param = __param; }
2016
2017       /**
2018        * @brief Returns the greatest lower bound value of the distribution.
2019        */
2020       result_type
2021       min() const
2022       { return result_type(0); }
2023
2024       /**
2025        * @brief Returns the least upper bound value of the distribution.
2026        */
2027       result_type
2028       max() const
2029       { return std::numeric_limits<result_type>::max(); }
2030
2031       template<typename _UniformRandomNumberGenerator>
2032         result_type
2033         operator()(_UniformRandomNumberGenerator& __urng)
2034         { return this->operator()(__urng, this->param()); }
2035
2036       template<typename _UniformRandomNumberGenerator>
2037         result_type
2038         operator()(_UniformRandomNumberGenerator& __urng,
2039                    const param_type& __p)
2040         { return std::exp(__p.s() * _M_nd(__urng) + __p.m()); }
2041
2042       /**
2043        * @brief Inserts a %lognormal_distribution random number distribution
2044        * @p __x into the output stream @p __os.
2045        *
2046        * @param __os An output stream.
2047        * @param __x  A %lognormal_distribution random number distribution.
2048        *
2049        * @returns The output stream with the state of @p __x inserted or in
2050        * an error state.
2051        */
2052       template<typename _RealType1, typename _CharT, typename _Traits>
2053         friend std::basic_ostream<_CharT, _Traits>&
2054         operator<<(std::basic_ostream<_CharT, _Traits>&,
2055                    const std::lognormal_distribution<_RealType1>&);
2056
2057       /**
2058        * @brief Extracts a %lognormal_distribution random number distribution
2059        * @p __x from the input stream @p __is.
2060        *
2061        * @param __is An input stream.
2062        * @param __x A %lognormal_distribution random number
2063        *            generator engine.
2064        *
2065        * @returns The input stream with @p __x extracted or in an error state.
2066        */
2067       template<typename _RealType1, typename _CharT, typename _Traits>
2068         friend std::basic_istream<_CharT, _Traits>&
2069         operator>>(std::basic_istream<_CharT, _Traits>&,
2070                    std::lognormal_distribution<_RealType1>&);
2071
2072     private:
2073       param_type _M_param;
2074
2075       std::normal_distribution<result_type> _M_nd;
2076     };
2077
2078
2079   /**
2080    * @brief A gamma continuous distribution for random numbers.
2081    *
2082    * The formula for the gamma probability density function is
2083    * @f$ p(x|\alpha,\beta) = \frac{1}{\beta\Gamma(\alpha)}
2084    *                         (x/\beta)^{\alpha - 1} e^{-x/\beta} @f$.
2085    */
2086   template<typename _RealType = double>
2087     class gamma_distribution
2088     {
2089     public:
2090       /** The type of the range of the distribution. */
2091       typedef _RealType result_type;
2092       /** Parameter type. */
2093       struct param_type
2094       {
2095         typedef gamma_distribution<_RealType> distribution_type;
2096         friend class gamma_distribution<_RealType>;
2097
2098         explicit
2099         param_type(_RealType __alpha_val = _RealType(1),
2100                    _RealType __beta_val = _RealType(1))
2101         : _M_alpha(__alpha_val), _M_beta(__beta_val)
2102         {
2103           _GLIBCXX_DEBUG_ASSERT(_M_alpha > _RealType(0));
2104           _M_initialize();
2105         }
2106
2107         _RealType
2108         alpha() const
2109         { return _M_alpha; }
2110
2111         _RealType
2112         beta() const
2113         { return _M_beta; }
2114
2115       private:
2116         void
2117         _M_initialize();
2118
2119         _RealType _M_alpha;
2120         _RealType _M_beta;
2121
2122         _RealType _M_malpha, _M_a2;
2123       };
2124
2125     public:
2126       /**
2127        * @brief Constructs a gamma distribution with parameters
2128        * @f$ \alpha @f$ and @f$ \beta @f$.
2129        */
2130       explicit
2131       gamma_distribution(_RealType __alpha_val = _RealType(1),
2132                          _RealType __beta_val = _RealType(1))
2133       : _M_param(__alpha_val, __beta_val), _M_nd()
2134       { }
2135
2136       explicit
2137       gamma_distribution(const param_type& __p)
2138       : _M_param(__p), _M_nd()
2139       { }
2140
2141       /**
2142        * @brief Resets the distribution state.
2143        */
2144       void
2145       reset()
2146       { _M_nd.reset(); }
2147
2148       /**
2149        * @brief Returns the @f$ \alpha @f$ of the distribution.
2150        */
2151       _RealType
2152       alpha() const
2153       { return _M_param.alpha(); }
2154
2155       /**
2156        * @brief Returns the @f$ \beta @f$ of the distribution.
2157        */
2158       _RealType
2159       beta() const
2160       { return _M_param.beta(); }
2161
2162       /**
2163        * @brief Returns the parameter set of the distribution.
2164        */
2165       param_type
2166       param() const
2167       { return _M_param; }
2168
2169       /**
2170        * @brief Sets the parameter set of the distribution.
2171        * @param __param The new parameter set of the distribution.
2172        */
2173       void
2174       param(const param_type& __param)
2175       { _M_param = __param; }
2176
2177       /**
2178        * @brief Returns the greatest lower bound value of the distribution.
2179        */
2180       result_type
2181       min() const
2182       { return result_type(0); }
2183
2184       /**
2185        * @brief Returns the least upper bound value of the distribution.
2186        */
2187       result_type
2188       max() const
2189       { return std::numeric_limits<result_type>::max(); }
2190
2191       template<typename _UniformRandomNumberGenerator>
2192         result_type
2193         operator()(_UniformRandomNumberGenerator& __urng)
2194         { return this->operator()(__urng, this->param()); }
2195
2196       template<typename _UniformRandomNumberGenerator>
2197         result_type
2198         operator()(_UniformRandomNumberGenerator& __urng,
2199                    const param_type& __p);
2200
2201       /**
2202        * @brief Inserts a %gamma_distribution random number distribution
2203        * @p __x into the output stream @p __os.
2204        *
2205        * @param __os An output stream.
2206        * @param __x  A %gamma_distribution random number distribution.
2207        *
2208        * @returns The output stream with the state of @p __x inserted or in
2209        * an error state.
2210        */
2211       template<typename _RealType1, typename _CharT, typename _Traits>
2212         friend std::basic_ostream<_CharT, _Traits>&
2213         operator<<(std::basic_ostream<_CharT, _Traits>&,
2214                    const std::gamma_distribution<_RealType1>&);
2215
2216       /**
2217        * @brief Extracts a %gamma_distribution random number distribution
2218        * @p __x from the input stream @p __is.
2219        *
2220        * @param __is An input stream.
2221        * @param __x  A %gamma_distribution random number generator engine.
2222        *
2223        * @returns The input stream with @p __x extracted or in an error state.
2224        */
2225       template<typename _RealType1, typename _CharT, typename _Traits>
2226         friend std::basic_istream<_CharT, _Traits>&
2227         operator>>(std::basic_istream<_CharT, _Traits>&,
2228                    std::gamma_distribution<_RealType1>&);
2229
2230     private:
2231       param_type _M_param;
2232
2233       std::normal_distribution<result_type> _M_nd;
2234     };
2235
2236
2237   /**
2238    * @brief A chi_squared_distribution random number distribution.
2239    *
2240    * The formula for the normal probability mass function is
2241    * @f$ p(x|n) = \frac{x^{(n/2) - 1}e^{-x/2}}{\Gamma(n/2) 2^{n/2}} @f$
2242    */
2243   template<typename _RealType = double>
2244     class chi_squared_distribution
2245     {
2246     public:
2247       /** The type of the range of the distribution. */
2248       typedef _RealType result_type;
2249       /** Parameter type. */
2250       struct param_type
2251       {
2252         typedef chi_squared_distribution<_RealType> distribution_type;
2253
2254         explicit
2255         param_type(_RealType __n = _RealType(1))
2256         : _M_n(__n)
2257         { }
2258
2259         _RealType
2260         n() const
2261         { return _M_n; }
2262
2263       private:
2264         _RealType _M_n;
2265       };
2266
2267       explicit
2268       chi_squared_distribution(_RealType __n = _RealType(1))
2269       : _M_param(__n), _M_gd(__n / 2)
2270       { }
2271
2272       explicit
2273       chi_squared_distribution(const param_type& __p)
2274       : _M_param(__p), _M_gd(__p.n() / 2)
2275       { }
2276
2277       /**
2278        * @brief Resets the distribution state.
2279        */
2280       void
2281       reset()
2282       { _M_gd.reset(); }
2283
2284       /**
2285        *
2286        */
2287       _RealType
2288       n() const
2289       { return _M_param.n(); }
2290
2291       /**
2292        * @brief Returns the parameter set of the distribution.
2293        */
2294       param_type
2295       param() const
2296       { return _M_param; }
2297
2298       /**
2299        * @brief Sets the parameter set of the distribution.
2300        * @param __param The new parameter set of the distribution.
2301        */
2302       void
2303       param(const param_type& __param)
2304       { _M_param = __param; }
2305
2306       /**
2307        * @brief Returns the greatest lower bound value of the distribution.
2308        */
2309       result_type
2310       min() const
2311       { return result_type(0); }
2312
2313       /**
2314        * @brief Returns the least upper bound value of the distribution.
2315        */
2316       result_type
2317       max() const
2318       { return std::numeric_limits<result_type>::max(); }
2319
2320       template<typename _UniformRandomNumberGenerator>
2321         result_type
2322         operator()(_UniformRandomNumberGenerator& __urng)
2323         { return 2 * _M_gd(__urng); }
2324
2325       template<typename _UniformRandomNumberGenerator>
2326         result_type
2327         operator()(_UniformRandomNumberGenerator& __urng,
2328                    const param_type& __p)
2329         {
2330           typedef typename std::gamma_distribution<result_type>::param_type
2331             param_type;
2332           return 2 * _M_gd(__urng, param_type(__p.n() / 2));
2333         }
2334
2335       /**
2336        * @brief Inserts a %chi_squared_distribution random number distribution
2337        * @p __x into the output stream @p __os.
2338        *
2339        * @param __os An output stream.
2340        * @param __x  A %chi_squared_distribution random number distribution.
2341        *
2342        * @returns The output stream with the state of @p __x inserted or in
2343        * an error state.
2344        */
2345       template<typename _RealType1, typename _CharT, typename _Traits>
2346         friend std::basic_ostream<_CharT, _Traits>&
2347         operator<<(std::basic_ostream<_CharT, _Traits>&,
2348                    const std::chi_squared_distribution<_RealType1>&);
2349
2350       /**
2351        * @brief Extracts a %chi_squared_distribution random number distribution
2352        * @p __x from the input stream @p __is.
2353        *
2354        * @param __is An input stream.
2355        * @param __x A %chi_squared_distribution random number
2356        *            generator engine.
2357        *
2358        * @returns The input stream with @p __x extracted or in an error state.
2359        */
2360       template<typename _RealType1, typename _CharT, typename _Traits>
2361         friend std::basic_istream<_CharT, _Traits>&
2362         operator>>(std::basic_istream<_CharT, _Traits>&,
2363                    std::chi_squared_distribution<_RealType1>&);
2364
2365     private:
2366       param_type _M_param;
2367
2368       std::gamma_distribution<result_type> _M_gd;
2369     };
2370
2371
2372   /**
2373    * @brief A cauchy_distribution random number distribution.
2374    *
2375    * The formula for the normal probability mass function is
2376    * @f$ p(x|a,b) = (\pi b (1 + (\frac{x-a}{b})^2))^{-1} @f$
2377    */
2378   template<typename _RealType = double>
2379     class cauchy_distribution
2380     {
2381     public:
2382       /** The type of the range of the distribution. */
2383       typedef _RealType result_type;
2384       /** Parameter type. */
2385       struct param_type
2386       {
2387         typedef cauchy_distribution<_RealType> distribution_type;
2388
2389         explicit
2390         param_type(_RealType __a = _RealType(0),
2391                    _RealType __b = _RealType(1))
2392         : _M_a(__a), _M_b(__b)
2393         { }
2394
2395         _RealType
2396         a() const
2397         { return _M_a; }
2398
2399         _RealType
2400         b() const
2401         { return _M_b; }
2402
2403       private:
2404         _RealType _M_a;
2405         _RealType _M_b;
2406       };
2407
2408       explicit
2409       cauchy_distribution(_RealType __a = _RealType(0),
2410                           _RealType __b = _RealType(1))
2411       : _M_param(__a, __b)
2412       { }
2413
2414       explicit
2415       cauchy_distribution(const param_type& __p)
2416       : _M_param(__p)
2417       { }
2418
2419       /**
2420        * @brief Resets the distribution state.
2421        */
2422       void
2423       reset()
2424       { }
2425
2426       /**
2427        *
2428        */
2429       _RealType
2430       a() const
2431       { return _M_param.a(); }
2432
2433       _RealType
2434       b() const
2435       { return _M_param.b(); }
2436
2437       /**
2438        * @brief Returns the parameter set of the distribution.
2439        */
2440       param_type
2441       param() const
2442       { return _M_param; }
2443
2444       /**
2445        * @brief Sets the parameter set of the distribution.
2446        * @param __param The new parameter set of the distribution.
2447        */
2448       void
2449       param(const param_type& __param)
2450       { _M_param = __param; }
2451
2452       /**
2453        * @brief Returns the greatest lower bound value of the distribution.
2454        */
2455       result_type
2456       min() const
2457       { return std::numeric_limits<result_type>::min(); }
2458
2459       /**
2460        * @brief Returns the least upper bound value of the distribution.
2461        */
2462       result_type
2463       max() const
2464       { return std::numeric_limits<result_type>::max(); }
2465
2466       template<typename _UniformRandomNumberGenerator>
2467         result_type
2468         operator()(_UniformRandomNumberGenerator& __urng)
2469         { return this->operator()(__urng, this->param()); }
2470
2471       template<typename _UniformRandomNumberGenerator>
2472         result_type
2473         operator()(_UniformRandomNumberGenerator& __urng,
2474                    const param_type& __p);
2475
2476     private:
2477       param_type _M_param;
2478     };
2479
2480   /**
2481    * @brief Inserts a %cauchy_distribution random number distribution
2482    * @p __x into the output stream @p __os.
2483    *
2484    * @param __os An output stream.
2485    * @param __x  A %cauchy_distribution random number distribution.
2486    *
2487    * @returns The output stream with the state of @p __x inserted or in
2488    * an error state.
2489    */
2490   template<typename _RealType, typename _CharT, typename _Traits>
2491     std::basic_ostream<_CharT, _Traits>&
2492     operator<<(std::basic_ostream<_CharT, _Traits>&,
2493                const std::cauchy_distribution<_RealType>&);
2494
2495   /**
2496    * @brief Extracts a %cauchy_distribution random number distribution
2497    * @p __x from the input stream @p __is.
2498    *
2499    * @param __is An input stream.
2500    * @param __x A %cauchy_distribution random number
2501    *            generator engine.
2502    *
2503    * @returns The input stream with @p __x extracted or in an error state.
2504    */
2505   template<typename _RealType, typename _CharT, typename _Traits>
2506     std::basic_istream<_CharT, _Traits>&
2507     operator>>(std::basic_istream<_CharT, _Traits>&,
2508                std::cauchy_distribution<_RealType>&);
2509
2510
2511   /**
2512    * @brief A fisher_f_distribution random number distribution.
2513    *
2514    * The formula for the normal probability mass function is
2515    * @f$ p(x|m,n) = \frac{\Gamma((m+n)/2)}{\Gamma(m/2)\Gamma(n/2)}
2516    *                (\frac{m}{n})^{m/2} x^{(m/2)-1}
2517    *                (1 + \frac{mx}{n})^{-(m+n)/2} @f$
2518    */
2519   template<typename _RealType = double>
2520     class fisher_f_distribution
2521     {
2522     public:
2523       /** The type of the range of the distribution. */
2524       typedef _RealType result_type;
2525       /** Parameter type. */
2526       struct param_type
2527       {
2528         typedef fisher_f_distribution<_RealType> distribution_type;
2529
2530         explicit
2531         param_type(_RealType __m = _RealType(1),
2532                    _RealType __n = _RealType(1))
2533         : _M_m(__m), _M_n(__n)
2534         { }
2535
2536         _RealType
2537         m() const
2538         { return _M_m; }
2539
2540         _RealType
2541         n() const
2542         { return _M_n; }
2543
2544       private:
2545         _RealType _M_m;
2546         _RealType _M_n;
2547       };
2548
2549       explicit
2550       fisher_f_distribution(_RealType __m = _RealType(1),
2551                             _RealType __n = _RealType(1))
2552       : _M_param(__m, __n), _M_gd_x(__m / 2), _M_gd_y(__n / 2)
2553       { }
2554
2555       explicit
2556       fisher_f_distribution(const param_type& __p)
2557       : _M_param(__p), _M_gd_x(__p.m() / 2), _M_gd_y(__p.n() / 2)
2558       { }
2559
2560       /**
2561        * @brief Resets the distribution state.
2562        */
2563       void
2564       reset()
2565       {
2566         _M_gd_x.reset();
2567         _M_gd_y.reset();
2568       }
2569
2570       /**
2571        *
2572        */
2573       _RealType
2574       m() const
2575       { return _M_param.m(); }
2576
2577       _RealType
2578       n() const
2579       { return _M_param.n(); }
2580
2581       /**
2582        * @brief Returns the parameter set of the distribution.
2583        */
2584       param_type
2585       param() const
2586       { return _M_param; }
2587
2588       /**
2589        * @brief Sets the parameter set of the distribution.
2590        * @param __param The new parameter set of the distribution.
2591        */
2592       void
2593       param(const param_type& __param)
2594       { _M_param = __param; }
2595
2596       /**
2597        * @brief Returns the greatest lower bound value of the distribution.
2598        */
2599       result_type
2600       min() const
2601       { return result_type(0); }
2602
2603       /**
2604        * @brief Returns the least upper bound value of the distribution.
2605        */
2606       result_type
2607       max() const
2608       { return std::numeric_limits<result_type>::max(); }
2609
2610       template<typename _UniformRandomNumberGenerator>
2611         result_type
2612         operator()(_UniformRandomNumberGenerator& __urng)
2613         { return (_M_gd_x(__urng) * n()) / (_M_gd_y(__urng) * m()); }
2614
2615       template<typename _UniformRandomNumberGenerator>
2616         result_type
2617         operator()(_UniformRandomNumberGenerator& __urng,
2618                    const param_type& __p)
2619         {
2620           typedef typename std::gamma_distribution<result_type>::param_type
2621             param_type;
2622           return ((_M_gd_x(__urng, param_type(__p.m() / 2)) * n())
2623                   / (_M_gd_y(__urng, param_type(__p.n() / 2)) * m()));
2624         }
2625
2626       /**
2627        * @brief Inserts a %fisher_f_distribution random number distribution
2628        * @p __x into the output stream @p __os.
2629        *
2630        * @param __os An output stream.
2631        * @param __x  A %fisher_f_distribution random number distribution.
2632        *
2633        * @returns The output stream with the state of @p __x inserted or in
2634        * an error state.
2635        */
2636       template<typename _RealType1, typename _CharT, typename _Traits>
2637         friend std::basic_ostream<_CharT, _Traits>&
2638         operator<<(std::basic_ostream<_CharT, _Traits>&,
2639                    const std::fisher_f_distribution<_RealType1>&);
2640
2641       /**
2642        * @brief Extracts a %fisher_f_distribution random number distribution
2643        * @p __x from the input stream @p __is.
2644        *
2645        * @param __is An input stream.
2646        * @param __x A %fisher_f_distribution random number
2647        *            generator engine.
2648        *
2649        * @returns The input stream with @p __x extracted or in an error state.
2650        */
2651       template<typename _RealType1, typename _CharT, typename _Traits>
2652         friend std::basic_istream<_CharT, _Traits>&
2653         operator>>(std::basic_istream<_CharT, _Traits>&,
2654                    std::fisher_f_distribution<_RealType1>&);
2655
2656     private:
2657       param_type _M_param;
2658
2659       std::gamma_distribution<result_type> _M_gd_x, _M_gd_y;
2660     };
2661
2662
2663   /**
2664    * @brief A student_t_distribution random number distribution.
2665    *
2666    * The formula for the normal probability mass function is
2667    * @f$ p(x|n) = \frac{1}{\sqrt(n\pi)} \frac{\Gamma((n+1)/2)}{\Gamma(n/2)}
2668    *              (1 + \frac{x^2}{n}) ^{-(n+1)/2} @f$
2669    */
2670   template<typename _RealType = double>
2671     class student_t_distribution
2672     {
2673     public:
2674       /** The type of the range of the distribution. */
2675       typedef _RealType result_type;
2676       /** Parameter type. */
2677       struct param_type
2678       {
2679         typedef student_t_distribution<_RealType> distribution_type;
2680
2681         explicit
2682         param_type(_RealType __n = _RealType(1))
2683         : _M_n(__n)
2684         { }
2685
2686         _RealType
2687         n() const
2688         { return _M_n; }
2689
2690       private:
2691         _RealType _M_n;
2692       };
2693
2694       explicit
2695       student_t_distribution(_RealType __n = _RealType(1))
2696       : _M_param(__n), _M_nd(), _M_gd(__n / 2, 2)
2697       { }
2698
2699       explicit
2700       student_t_distribution(const param_type& __p)
2701       : _M_param(__p), _M_nd(), _M_gd(__p.n() / 2, 2)
2702       { }
2703
2704       /**
2705        * @brief Resets the distribution state.
2706        */
2707       void
2708       reset()
2709       {
2710         _M_nd.reset();
2711         _M_gd.reset();
2712       }
2713
2714       /**
2715        *
2716        */
2717       _RealType
2718       n() const
2719       { return _M_param.n(); }
2720
2721       /**
2722        * @brief Returns the parameter set of the distribution.
2723        */
2724       param_type
2725       param() const
2726       { return _M_param; }
2727
2728       /**
2729        * @brief Sets the parameter set of the distribution.
2730        * @param __param The new parameter set of the distribution.
2731        */
2732       void
2733       param(const param_type& __param)
2734       { _M_param = __param; }
2735
2736       /**
2737        * @brief Returns the greatest lower bound value of the distribution.
2738        */
2739       result_type
2740       min() const
2741       { return std::numeric_limits<result_type>::min(); }
2742
2743       /**
2744        * @brief Returns the least upper bound value of the distribution.
2745        */
2746       result_type
2747       max() const
2748       { return std::numeric_limits<result_type>::max(); }
2749
2750       template<typename _UniformRandomNumberGenerator>
2751         result_type
2752         operator()(_UniformRandomNumberGenerator& __urng)
2753         { return _M_nd(__urng) * std::sqrt(n() / _M_gd(__urng)); }
2754
2755       template<typename _UniformRandomNumberGenerator>
2756         result_type
2757         operator()(_UniformRandomNumberGenerator& __urng,
2758                    const param_type& __p)
2759         {
2760           typedef typename std::gamma_distribution<result_type>::param_type
2761             param_type;
2762
2763           const result_type __g = _M_gd(__urng, param_type(__p.n() / 2, 2));
2764           return _M_nd(__urng) * std::sqrt(__p.n() / __g);
2765         }
2766
2767       /**
2768        * @brief Inserts a %student_t_distribution random number distribution
2769        * @p __x into the output stream @p __os.
2770        *
2771        * @param __os An output stream.
2772        * @param __x  A %student_t_distribution random number distribution.
2773        *
2774        * @returns The output stream with the state of @p __x inserted or in
2775        * an error state.
2776        */
2777       template<typename _RealType1, typename _CharT, typename _Traits>
2778         friend std::basic_ostream<_CharT, _Traits>&
2779         operator<<(std::basic_ostream<_CharT, _Traits>&,
2780                    const std::student_t_distribution<_RealType1>&);
2781
2782       /**
2783        * @brief Extracts a %student_t_distribution random number distribution
2784        * @p __x from the input stream @p __is.
2785        *
2786        * @param __is An input stream.
2787        * @param __x A %student_t_distribution random number
2788        *            generator engine.
2789        *
2790        * @returns The input stream with @p __x extracted or in an error state.
2791        */
2792       template<typename _RealType1, typename _CharT, typename _Traits>
2793         friend std::basic_istream<_CharT, _Traits>&
2794         operator>>(std::basic_istream<_CharT, _Traits>&,
2795                    std::student_t_distribution<_RealType1>&);
2796
2797     private:
2798       param_type _M_param;
2799
2800       std::normal_distribution<result_type> _M_nd;
2801       std::gamma_distribution<result_type> _M_gd;
2802     };
2803
2804   /* @} */ // group std_random_distributions_normal
2805
2806   /**
2807    * @addtogroup std_random_distributions_bernoulli Bernoulli Distributions
2808    * @ingroup std_random_distributions
2809    * @{
2810    */
2811
2812   /**
2813    * @brief A Bernoulli random number distribution.
2814    *
2815    * Generates a sequence of true and false values with likelihood @f$ p @f$
2816    * that true will come up and @f$ (1 - p) @f$ that false will appear.
2817    */
2818   class bernoulli_distribution
2819   {
2820   public:
2821     /** The type of the range of the distribution. */
2822     typedef bool result_type;
2823     /** Parameter type. */
2824     struct param_type
2825     {
2826       typedef bernoulli_distribution distribution_type;
2827
2828       explicit
2829       param_type(double __p = 0.5)
2830       : _M_p(__p)
2831       {
2832         _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
2833       }
2834
2835       double
2836       p() const
2837       { return _M_p; }
2838
2839     private:
2840       double _M_p;
2841     };
2842
2843   public:
2844     /**
2845      * @brief Constructs a Bernoulli distribution with likelihood @p p.
2846      *
2847      * @param __p  [IN]  The likelihood of a true result being returned.
2848      *                   Must be in the interval @f$ [0, 1] @f$.
2849      */
2850     explicit
2851     bernoulli_distribution(double __p = 0.5)
2852     : _M_param(__p)
2853     { }
2854
2855     explicit
2856     bernoulli_distribution(const param_type& __p)
2857     : _M_param(__p)
2858     { }
2859
2860     /**
2861      * @brief Resets the distribution state.
2862      *
2863      * Does nothing for a Bernoulli distribution.
2864      */
2865     void
2866     reset() { }
2867
2868     /**
2869      * @brief Returns the @p p parameter of the distribution.
2870      */
2871     double
2872     p() const
2873     { return _M_param.p(); }
2874
2875     /**
2876      * @brief Returns the parameter set of the distribution.
2877      */
2878     param_type
2879     param() const
2880     { return _M_param; }
2881
2882     /**
2883      * @brief Sets the parameter set of the distribution.
2884      * @param __param The new parameter set of the distribution.
2885      */
2886     void
2887     param(const param_type& __param)
2888     { _M_param = __param; }
2889
2890     /**
2891      * @brief Returns the greatest lower bound value of the distribution.
2892      */
2893     result_type
2894     min() const
2895     { return std::numeric_limits<result_type>::min(); }
2896
2897     /**
2898      * @brief Returns the least upper bound value of the distribution.
2899      */
2900     result_type
2901     max() const
2902     { return std::numeric_limits<result_type>::max(); }
2903
2904     /**
2905      * @brief Returns the next value in the Bernoullian sequence.
2906      */
2907     template<typename _UniformRandomNumberGenerator>
2908       result_type
2909       operator()(_UniformRandomNumberGenerator& __urng)
2910       { return this->operator()(__urng, this->param()); }
2911
2912     template<typename _UniformRandomNumberGenerator>
2913       result_type
2914       operator()(_UniformRandomNumberGenerator& __urng,
2915                  const param_type& __p)
2916       {
2917         __detail::_Adaptor<_UniformRandomNumberGenerator, double>
2918           __aurng(__urng);
2919         if ((__aurng() - __aurng.min())
2920              < __p.p() * (__aurng.max() - __aurng.min()))
2921           return true;
2922         return false;
2923       }
2924
2925   private:
2926     param_type _M_param;
2927   };
2928
2929   /**
2930    * @brief Inserts a %bernoulli_distribution random number distribution
2931    * @p __x into the output stream @p __os.
2932    *
2933    * @param __os An output stream.
2934    * @param __x  A %bernoulli_distribution random number distribution.
2935    *
2936    * @returns The output stream with the state of @p __x inserted or in
2937    * an error state.
2938    */
2939   template<typename _CharT, typename _Traits>
2940     std::basic_ostream<_CharT, _Traits>&
2941     operator<<(std::basic_ostream<_CharT, _Traits>&,
2942                const std::bernoulli_distribution&);
2943
2944   /**
2945    * @brief Extracts a %bernoulli_distribution random number distribution
2946    * @p __x from the input stream @p __is.
2947    *
2948    * @param __is An input stream.
2949    * @param __x  A %bernoulli_distribution random number generator engine.
2950    *
2951    * @returns The input stream with @p __x extracted or in an error state.
2952    */
2953   template<typename _CharT, typename _Traits>
2954     std::basic_istream<_CharT, _Traits>&
2955     operator>>(std::basic_istream<_CharT, _Traits>& __is,
2956                std::bernoulli_distribution& __x)
2957     {
2958       double __p;
2959       __is >> __p;
2960       __x.param(bernoulli_distribution::param_type(__p));
2961       return __is;
2962     }
2963
2964
2965   /**
2966    * @brief A discrete binomial random number distribution.
2967    *
2968    * The formula for the binomial probability density function is
2969    * @f$ p(i|t,p) = \binom{n}{i} p^i (1 - p)^{t - i} @f$ where @f$ t @f$
2970    * and @f$ p @f$ are the parameters of the distribution.
2971    */
2972   template<typename _IntType = int>
2973     class binomial_distribution
2974     {
2975       __glibcxx_class_requires(_IntType, _IntegerConcept)
2976
2977     public:
2978       /** The type of the range of the distribution. */
2979       typedef _IntType result_type;
2980       /** Parameter type. */
2981       struct param_type
2982       {
2983         typedef binomial_distribution<_IntType> distribution_type;
2984         friend class binomial_distribution<_IntType>;
2985
2986         explicit
2987         param_type(_IntType __t = _IntType(1), double __p = 0.5)
2988         : _M_t(__t), _M_p(__p)
2989         {
2990           _GLIBCXX_DEBUG_ASSERT((_M_t >= _IntType(0))
2991                                 && (_M_p >= 0.0)
2992                                 && (_M_p <= 1.0));
2993           _M_initialize();
2994         }
2995
2996         _IntType
2997         t() const
2998         { return _M_t; }
2999
3000         double
3001         p() const
3002         { return _M_p; }
3003
3004       private:
3005         void
3006         _M_initialize();
3007
3008         _IntType _M_t;
3009         double _M_p;
3010
3011         double _M_q;
3012 #if _GLIBCXX_USE_C99_MATH_TR1
3013         double _M_d1, _M_d2, _M_s1, _M_s2, _M_c,
3014                _M_a1, _M_a123, _M_s, _M_lf, _M_lp1p;
3015 #endif
3016         bool   _M_easy;
3017       };
3018
3019       // constructors and member function
3020       explicit
3021       binomial_distribution(_IntType __t = _IntType(1),
3022                             double __p = 0.5)
3023       : _M_param(__t, __p), _M_nd()
3024       { }
3025
3026       explicit
3027       binomial_distribution(const param_type& __p)
3028       : _M_param(__p), _M_nd()
3029       { }
3030
3031       /**
3032        * @brief Resets the distribution state.
3033        */
3034       void
3035       reset()
3036       { _M_nd.reset(); }
3037
3038       /**
3039        * @brief Returns the distribution @p t parameter.
3040        */
3041       _IntType
3042       t() const
3043       { return _M_param.t(); }
3044
3045       /**
3046        * @brief Returns the distribution @p p parameter.
3047        */
3048       double
3049       p() const
3050       { return _M_param.p(); }
3051
3052       /**
3053        * @brief Returns the parameter set of the distribution.
3054        */
3055       param_type
3056       param() const
3057       { return _M_param; }
3058
3059       /**
3060        * @brief Sets the parameter set of the distribution.
3061        * @param __param The new parameter set of the distribution.
3062        */
3063       void
3064       param(const param_type& __param)
3065       { _M_param = __param; }
3066
3067       /**
3068        * @brief Returns the greatest lower bound value of the distribution.
3069        */
3070       result_type
3071       min() const
3072       { return 0; }
3073
3074       /**
3075        * @brief Returns the least upper bound value of the distribution.
3076        */
3077       result_type
3078       max() const
3079       { return _M_param.t(); }
3080
3081       template<typename _UniformRandomNumberGenerator>
3082         result_type
3083         operator()(_UniformRandomNumberGenerator& __urng)
3084         { return this->operator()(__urng, this->param()); }
3085
3086       template<typename _UniformRandomNumberGenerator>
3087         result_type
3088         operator()(_UniformRandomNumberGenerator& __urng,
3089                    const param_type& __p);
3090
3091       /**
3092        * @brief Inserts a %binomial_distribution random number distribution
3093        * @p __x into the output stream @p __os.
3094        *
3095        * @param __os An output stream.
3096        * @param __x  A %binomial_distribution random number distribution.
3097        *
3098        * @returns The output stream with the state of @p __x inserted or in
3099        * an error state.
3100        */
3101       template<typename _IntType1,
3102                typename _CharT, typename _Traits>
3103         friend std::basic_ostream<_CharT, _Traits>&
3104         operator<<(std::basic_ostream<_CharT, _Traits>&,
3105                    const std::binomial_distribution<_IntType1>&);
3106
3107       /**
3108        * @brief Extracts a %binomial_distribution random number distribution
3109        * @p __x from the input stream @p __is.
3110        *
3111        * @param __is An input stream.
3112        * @param __x  A %binomial_distribution random number generator engine.
3113        *
3114        * @returns The input stream with @p __x extracted or in an error
3115        *          state.
3116        */
3117       template<typename _IntType1,
3118                typename _CharT, typename _Traits>
3119         friend std::basic_istream<_CharT, _Traits>&
3120         operator>>(std::basic_istream<_CharT, _Traits>&,
3121                    std::binomial_distribution<_IntType1>&);
3122
3123     private:
3124       template<typename _UniformRandomNumberGenerator>
3125         result_type
3126         _M_waiting(_UniformRandomNumberGenerator& __urng, _IntType __t);
3127
3128       param_type _M_param;
3129
3130       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
3131       std::normal_distribution<double> _M_nd;
3132     };
3133
3134
3135   /**
3136    * @brief A discrete geometric random number distribution.
3137    *
3138    * The formula for the geometric probability density function is
3139    * @f$ p(i|p) = (1 - p)p^{i-1} @f$ where @f$ p @f$ is the parameter of the
3140    * distribution.
3141    */
3142   template<typename _IntType = int>
3143     class geometric_distribution
3144     {
3145       __glibcxx_class_requires(_IntType, _IntegerConcept)
3146
3147     public:
3148       /** The type of the range of the distribution. */
3149       typedef _IntType  result_type;
3150       /** Parameter type. */
3151       struct param_type
3152       {
3153         typedef geometric_distribution<_IntType> distribution_type;
3154         friend class geometric_distribution<_IntType>;
3155
3156         explicit
3157         param_type(double __p = 0.5)
3158         : _M_p(__p)
3159         {
3160           _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0)
3161                              && (_M_p <= 1.0));
3162           _M_initialize();
3163         }
3164
3165         double
3166         p() const
3167         { return _M_p; }
3168
3169       private:
3170         void
3171         _M_initialize()
3172         { _M_log_p = std::log(_M_p); }
3173
3174         double _M_p;
3175
3176         double _M_log_p;
3177       };
3178
3179       // constructors and member function
3180       explicit
3181       geometric_distribution(double __p = 0.5)
3182       : _M_param(__p)
3183       { }
3184
3185       explicit
3186       geometric_distribution(const param_type& __p)
3187       : _M_param(__p)
3188       { }
3189
3190       /**
3191        * @brief Resets the distribution state.
3192        *
3193        * Does nothing for the geometric distribution.
3194        */
3195       void
3196       reset() { }
3197
3198       /**
3199        * @brief Returns the distribution parameter @p p.
3200        */
3201       double
3202       p() const
3203       { return _M_param.p(); }
3204
3205       /**
3206        * @brief Returns the parameter set of the distribution.
3207        */
3208       param_type
3209       param() const
3210       { return _M_param; }
3211
3212       /**
3213        * @brief Sets the parameter set of the distribution.
3214        * @param __param The new parameter set of the distribution.
3215        */
3216       void
3217       param(const param_type& __param)
3218       { _M_param = __param; }
3219
3220       /**
3221        * @brief Returns the greatest lower bound value of the distribution.
3222        */
3223       result_type
3224       min() const
3225       { return 0; }
3226
3227       /**
3228        * @brief Returns the least upper bound value of the distribution.
3229        */
3230       result_type
3231       max() const
3232       { return std::numeric_limits<result_type>::max(); }
3233
3234       template<typename _UniformRandomNumberGenerator>
3235         result_type
3236         operator()(_UniformRandomNumberGenerator& __urng)
3237         { return this->operator()(__urng, this->param()); }
3238
3239       template<typename _UniformRandomNumberGenerator>
3240         result_type
3241         operator()(_UniformRandomNumberGenerator& __urng,
3242                    const param_type& __p);
3243
3244     private:
3245       param_type _M_param;
3246     };
3247
3248   /**
3249    * @brief Inserts a %geometric_distribution random number distribution
3250    * @p __x into the output stream @p __os.
3251    *
3252    * @param __os An output stream.
3253    * @param __x  A %geometric_distribution random number distribution.
3254    *
3255    * @returns The output stream with the state of @p __x inserted or in
3256    * an error state.
3257    */
3258   template<typename _IntType,
3259            typename _CharT, typename _Traits>
3260     std::basic_ostream<_CharT, _Traits>&
3261     operator<<(std::basic_ostream<_CharT, _Traits>&,
3262                const std::geometric_distribution<_IntType>&);
3263
3264   /**
3265    * @brief Extracts a %geometric_distribution random number distribution
3266    * @p __x from the input stream @p __is.
3267    *
3268    * @param __is An input stream.
3269    * @param __x  A %geometric_distribution random number generator engine.
3270    *
3271    * @returns The input stream with @p __x extracted or in an error state.
3272    */
3273   template<typename _IntType,
3274            typename _CharT, typename _Traits>
3275     std::basic_istream<_CharT, _Traits>&
3276     operator>>(std::basic_istream<_CharT, _Traits>&,
3277                std::geometric_distribution<_IntType>&);
3278
3279
3280   /**
3281    * @brief A negative_binomial_distribution random number distribution.
3282    *
3283    * The formula for the negative binomial probability mass function is
3284    * @f$ p(i) = \binom{n}{i} p^i (1 - p)^{t - i} @f$ where @f$ t @f$
3285    * and @f$ p @f$ are the parameters of the distribution.
3286    */
3287   template<typename _IntType = int>
3288     class negative_binomial_distribution
3289     {
3290       __glibcxx_class_requires(_IntType, _IntegerConcept)
3291
3292     public:
3293       /** The type of the range of the distribution. */
3294       typedef _IntType result_type;
3295       /** Parameter type. */
3296       struct param_type
3297       {
3298         typedef negative_binomial_distribution<_IntType> distribution_type;
3299
3300         explicit
3301         param_type(_IntType __k = 1, double __p = 0.5)
3302         : _M_k(__k), _M_p(__p)
3303         { }
3304
3305         _IntType
3306         k() const
3307         { return _M_k; }
3308
3309         double
3310         p() const
3311         { return _M_p; }
3312
3313       private:
3314         _IntType _M_k;
3315         double _M_p;
3316       };
3317
3318       explicit
3319       negative_binomial_distribution(_IntType __k = 1, double __p = 0.5)
3320       : _M_param(__k, __p), _M_gd(__k, __p / (1.0 - __p))
3321       { }
3322
3323       explicit
3324       negative_binomial_distribution(const param_type& __p)
3325       : _M_param(__p), _M_gd(__p.k(), __p.p() / (1.0 - __p.p()))
3326       { }
3327
3328       /**
3329        * @brief Resets the distribution state.
3330        */
3331       void
3332       reset()
3333       { _M_gd.reset(); }
3334
3335       /**
3336        * @brief Return the @f$ k @f$ parameter of the distribution.
3337        */
3338       _IntType
3339       k() const
3340       { return _M_param.k(); }
3341
3342       /**
3343        * @brief Return the @f$ p @f$ parameter of the distribution.
3344        */
3345       double
3346       p() const
3347       { return _M_param.p(); }
3348
3349       /**
3350        * @brief Returns the parameter set of the distribution.
3351        */
3352       param_type
3353       param() const
3354       { return _M_param; }
3355
3356       /**
3357        * @brief Sets the parameter set of the distribution.
3358        * @param __param The new parameter set of the distribution.
3359        */
3360       void
3361       param(const param_type& __param)
3362       { _M_param = __param; }
3363
3364       /**
3365        * @brief Returns the greatest lower bound value of the distribution.
3366        */
3367       result_type
3368       min() const
3369       { return result_type(0); }
3370
3371       /**
3372        * @brief Returns the least upper bound value of the distribution.
3373        */
3374       result_type
3375       max() const
3376       { return std::numeric_limits<result_type>::max(); }
3377
3378       template<typename _UniformRandomNumberGenerator>
3379         result_type
3380         operator()(_UniformRandomNumberGenerator& __urng);
3381
3382       template<typename _UniformRandomNumberGenerator>
3383         result_type
3384         operator()(_UniformRandomNumberGenerator& __urng,
3385                    const param_type& __p);
3386
3387       /**
3388        * @brief Inserts a %negative_binomial_distribution random
3389        *        number distribution @p __x into the output stream @p __os.
3390        *
3391        * @param __os An output stream.
3392        * @param __x  A %negative_binomial_distribution random number
3393        *             distribution.
3394        *
3395        * @returns The output stream with the state of @p __x inserted or in
3396        *          an error state.
3397        */
3398       template<typename _IntType1, typename _CharT, typename _Traits>
3399         friend std::basic_ostream<_CharT, _Traits>&
3400         operator<<(std::basic_ostream<_CharT, _Traits>&,
3401                    const std::negative_binomial_distribution<_IntType1>&);
3402
3403       /**
3404        * @brief Extracts a %negative_binomial_distribution random number
3405        *        distribution @p __x from the input stream @p __is.
3406        *
3407        * @param __is An input stream.
3408        * @param __x A %negative_binomial_distribution random number
3409        *            generator engine.
3410        *
3411        * @returns The input stream with @p __x extracted or in an error state.
3412        */
3413       template<typename _IntType1, typename _CharT, typename _Traits>
3414         friend std::basic_istream<_CharT, _Traits>&
3415         operator>>(std::basic_istream<_CharT, _Traits>&,
3416                    std::negative_binomial_distribution<_IntType1>&);
3417
3418     private:
3419       param_type _M_param;
3420
3421       std::gamma_distribution<double> _M_gd;
3422     };
3423
3424   /* @} */ // group std_random_distributions_bernoulli
3425
3426   /**
3427    * @addtogroup std_random_distributions_poisson Poisson Distributions
3428    * @ingroup std_random_distributions
3429    * @{
3430    */
3431
3432   /**
3433    * @brief A discrete Poisson random number distribution.
3434    *
3435    * The formula for the Poisson probability density function is
3436    * @f$ p(i|\mu) = \frac{\mu^i}{i!} e^{-\mu} @f$ where @f$ \mu @f$ is the
3437    * parameter of the distribution.
3438    */
3439   template<typename _IntType = int>
3440     class poisson_distribution
3441     {
3442       __glibcxx_class_requires(_IntType, _IntegerConcept)
3443
3444     public:
3445       /** The type of the range of the distribution. */
3446       typedef _IntType  result_type;
3447       /** Parameter type. */
3448       struct param_type
3449       {
3450         typedef poisson_distribution<_IntType> distribution_type;
3451         friend class poisson_distribution<_IntType>;
3452
3453         explicit
3454         param_type(double __mean = 1.0)
3455         : _M_mean(__mean)
3456         {
3457           _GLIBCXX_DEBUG_ASSERT(_M_mean > 0.0);
3458           _M_initialize();
3459         }
3460
3461         double
3462         mean() const
3463         { return _M_mean; }
3464
3465       private:
3466         // Hosts either log(mean) or the threshold of the simple method.
3467         void
3468         _M_initialize();
3469
3470         double _M_mean;
3471
3472         double _M_lm_thr;
3473 #if _GLIBCXX_USE_C99_MATH_TR1
3474         double _M_lfm, _M_sm, _M_d, _M_scx, _M_1cx, _M_c2b, _M_cb;
3475 #endif
3476       };
3477
3478       // constructors and member function
3479       explicit
3480       poisson_distribution(double __mean = 1.0)
3481       : _M_param(__mean), _M_nd()
3482       { }
3483
3484       explicit
3485       poisson_distribution(const param_type& __p)
3486       : _M_param(__p), _M_nd()
3487       { }
3488
3489       /**
3490        * @brief Resets the distribution state.
3491        */
3492       void
3493       reset()
3494       { _M_nd.reset(); }
3495
3496       /**
3497        * @brief Returns the distribution parameter @p mean.
3498        */
3499       double
3500       mean() const
3501       { return _M_param.mean(); }
3502
3503       /**
3504        * @brief Returns the parameter set of the distribution.
3505        */
3506       param_type
3507       param() const
3508       { return _M_param; }
3509
3510       /**
3511        * @brief Sets the parameter set of the distribution.
3512        * @param __param The new parameter set of the distribution.
3513        */
3514       void
3515       param(const param_type& __param)
3516       { _M_param = __param; }
3517
3518       /**
3519        * @brief Returns the greatest lower bound value of the distribution.
3520        */
3521       result_type
3522       min() const
3523       { return 0; }
3524
3525       /**
3526        * @brief Returns the least upper bound value of the distribution.
3527        */
3528       result_type
3529       max() const
3530       { return std::numeric_limits<result_type>::max(); }
3531
3532       template<typename _UniformRandomNumberGenerator>
3533         result_type
3534         operator()(_UniformRandomNumberGenerator& __urng)
3535         { return this->operator()(__urng, this->param()); }
3536
3537       template<typename _UniformRandomNumberGenerator>
3538         result_type
3539         operator()(_UniformRandomNumberGenerator& __urng,
3540                    const param_type& __p);
3541
3542       /**
3543        * @brief Inserts a %poisson_distribution random number distribution
3544        * @p __x into the output stream @p __os.
3545        *
3546        * @param __os An output stream.
3547        * @param __x  A %poisson_distribution random number distribution.
3548        *
3549        * @returns The output stream with the state of @p __x inserted or in
3550        * an error state.
3551        */
3552       template<typename _IntType1, typename _CharT, typename _Traits>
3553         friend std::basic_ostream<_CharT, _Traits>&
3554         operator<<(std::basic_ostream<_CharT, _Traits>&,
3555                    const std::poisson_distribution<_IntType1>&);
3556
3557       /**
3558        * @brief Extracts a %poisson_distribution random number distribution
3559        * @p __x from the input stream @p __is.
3560        *
3561        * @param __is An input stream.
3562        * @param __x  A %poisson_distribution random number generator engine.
3563        *
3564        * @returns The input stream with @p __x extracted or in an error
3565        *          state.
3566        */
3567       template<typename _IntType1, typename _CharT, typename _Traits>
3568         friend std::basic_istream<_CharT, _Traits>&
3569         operator>>(std::basic_istream<_CharT, _Traits>&,
3570                    std::poisson_distribution<_IntType1>&);
3571
3572     private:
3573       param_type _M_param;
3574
3575       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
3576       std::normal_distribution<double> _M_nd;
3577     };
3578
3579   /**
3580    * @brief An exponential continuous distribution for random numbers.
3581    *
3582    * The formula for the exponential probability density function is
3583    * @f$ p(x|\lambda) = \lambda e^{-\lambda x} @f$.
3584    *
3585    * <table border=1 cellpadding=10 cellspacing=0>
3586    * <caption align=top>Distribution Statistics</caption>
3587    * <tr><td>Mean</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
3588    * <tr><td>Median</td><td>@f$ \frac{\ln 2}{\lambda} @f$</td></tr>
3589    * <tr><td>Mode</td><td>@f$ zero @f$</td></tr>
3590    * <tr><td>Range</td><td>@f$[0, \infty]@f$</td></tr>
3591    * <tr><td>Standard Deviation</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
3592    * </table>
3593    */
3594   template<typename _RealType = double>
3595     class exponential_distribution
3596     {
3597     public:
3598       /** The type of the range of the distribution. */
3599       typedef _RealType result_type;
3600       /** Parameter type. */
3601       struct param_type
3602       {
3603         typedef exponential_distribution<_RealType> distribution_type;
3604
3605         explicit
3606         param_type(_RealType __lambda = _RealType(1))
3607         : _M_lambda(__lambda)
3608         {
3609           _GLIBCXX_DEBUG_ASSERT(_M_lambda > _RealType(0));
3610         }
3611
3612         _RealType
3613         lambda() const
3614         { return _M_lambda; }
3615
3616       private:
3617         _RealType _M_lambda;
3618       };
3619
3620     public:
3621       /**
3622        * @brief Constructs an exponential distribution with inverse scale
3623        *        parameter @f$ \lambda @f$.
3624        */
3625       explicit
3626       exponential_distribution(const result_type& __lambda = result_type(1))
3627       : _M_param(__lambda)
3628       { }
3629
3630       explicit
3631       exponential_distribution(const param_type& __p)
3632       : _M_param(__p)
3633       { }
3634
3635       /**
3636        * @brief Resets the distribution state.
3637        *
3638        * Has no effect on exponential distributions.
3639        */
3640       void
3641       reset() { }
3642
3643       /**
3644        * @brief Returns the inverse scale parameter of the distribution.
3645        */
3646       _RealType
3647       lambda() const
3648       { return _M_param.lambda(); }
3649
3650       /**
3651        * @brief Returns the parameter set of the distribution.
3652        */
3653       param_type
3654       param() const
3655       { return _M_param; }
3656
3657       /**
3658        * @brief Sets the parameter set of the distribution.
3659        * @param __param The new parameter set of the distribution.
3660        */
3661       void
3662       param(const param_type& __param)
3663       { _M_param = __param; }
3664
3665       /**
3666        * @brief Returns the greatest lower bound value of the distribution.
3667        */
3668       result_type
3669       min() const
3670       { return result_type(0); }
3671
3672       /**
3673        * @brief Returns the least upper bound value of the distribution.
3674        */
3675       result_type
3676       max() const
3677       { return std::numeric_limits<result_type>::max(); }
3678
3679       template<typename _UniformRandomNumberGenerator>
3680         result_type
3681         operator()(_UniformRandomNumberGenerator& __urng)
3682         { return this->operator()(__urng, this->param()); }
3683
3684       template<typename _UniformRandomNumberGenerator>
3685         result_type
3686         operator()(_UniformRandomNumberGenerator& __urng,
3687                    const param_type& __p)
3688         {
3689           __detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
3690             __aurng(__urng);
3691           return -std::log(__aurng()) / __p.lambda();
3692         }
3693
3694     private:
3695       param_type _M_param;
3696     };
3697
3698   /**
3699    * @brief Inserts a %exponential_distribution random number distribution
3700    * @p __x into the output stream @p __os.
3701    *
3702    * @param __os An output stream.
3703    * @param __x  A %exponential_distribution random number distribution.
3704    *
3705    * @returns The output stream with the state of @p __x inserted or in
3706    * an error state.
3707    */
3708   template<typename _RealType, typename _CharT, typename _Traits>
3709     std::basic_ostream<_CharT, _Traits>&
3710     operator<<(std::basic_ostream<_CharT, _Traits>&,
3711                const std::exponential_distribution<_RealType>&);
3712
3713   /**
3714    * @brief Extracts a %exponential_distribution random number distribution
3715    * @p __x from the input stream @p __is.
3716    *
3717    * @param __is An input stream.
3718    * @param __x A %exponential_distribution random number
3719    *            generator engine.
3720    *
3721    * @returns The input stream with @p __x extracted or in an error state.
3722    */
3723   template<typename _RealType, typename _CharT, typename _Traits>
3724     std::basic_istream<_CharT, _Traits>&
3725     operator>>(std::basic_istream<_CharT, _Traits>&,
3726                std::exponential_distribution<_RealType>&);
3727
3728
3729   /**
3730    * @brief A weibull_distribution random number distribution.
3731    *
3732    * The formula for the normal probability density function is
3733    * @f$ p(x|\alpha,\beta) = \frac{a}{b} (frac{x}{b})^{a-1}
3734    *                         \exp{(-(frac{x}{b})^a)} @f$.
3735    */
3736   template<typename _RealType = double>
3737     class weibull_distribution
3738     {
3739     public:
3740       /** The type of the range of the distribution. */
3741       typedef _RealType result_type;
3742       /** Parameter type. */
3743       struct param_type
3744       {
3745         typedef weibull_distribution<_RealType> distribution_type;
3746
3747         explicit
3748         param_type(_RealType __a = _RealType(1),
3749                    _RealType __b = _RealType(1))
3750         : _M_a(__a), _M_b(__b)
3751         { }
3752
3753         _RealType
3754         a() const
3755         { return _M_a; }
3756
3757         _RealType
3758         b() const
3759         { return _M_b; }
3760
3761       private:
3762         _RealType _M_a;
3763         _RealType _M_b;
3764       };
3765
3766       explicit
3767       weibull_distribution(_RealType __a = _RealType(1),
3768                            _RealType __b = _RealType(1))
3769       : _M_param(__a, __b)
3770       { }
3771
3772       explicit
3773       weibull_distribution(const param_type& __p)
3774       : _M_param(__p)
3775       { }
3776
3777       /**
3778        * @brief Resets the distribution state.
3779        */
3780       void
3781       reset()
3782       { }
3783
3784       /**
3785        * @brief Return the @f$ a @f$ parameter of the distribution.
3786        */
3787       _RealType
3788       a() const
3789       { return _M_param.a(); }
3790
3791       /**
3792        * @brief Return the @f$ b @f$ parameter of the distribution.
3793        */
3794       _RealType
3795       b() const
3796       { return _M_param.b(); }
3797
3798       /**
3799        * @brief Returns the parameter set of the distribution.
3800        */
3801       param_type
3802       param() const
3803       { return _M_param; }
3804
3805       /**
3806        * @brief Sets the parameter set of the distribution.
3807        * @param __param The new parameter set of the distribution.
3808        */
3809       void
3810       param(const param_type& __param)
3811       { _M_param = __param; }
3812
3813       /**
3814        * @brief Returns the greatest lower bound value of the distribution.
3815        */
3816       result_type
3817       min() const
3818       { return result_type(0); }
3819
3820       /**
3821        * @brief Returns the least upper bound value of the distribution.
3822        */
3823       result_type
3824       max() const
3825       { return std::numeric_limits<result_type>::max(); }
3826
3827       template<typename _UniformRandomNumberGenerator>
3828         result_type
3829         operator()(_UniformRandomNumberGenerator& __urng)
3830         { return this->operator()(__urng, this->param()); }
3831
3832       template<typename _UniformRandomNumberGenerator>
3833         result_type
3834         operator()(_UniformRandomNumberGenerator& __urng,
3835                    const param_type& __p);
3836
3837     private:
3838       param_type _M_param;
3839     };
3840
3841   /**
3842    * @brief Inserts a %weibull_distribution random number distribution
3843    * @p __x into the output stream @p __os.
3844    *
3845    * @param __os An output stream.
3846    * @param __x  A %weibull_distribution random number distribution.
3847    *
3848    * @returns The output stream with the state of @p __x inserted or in
3849    * an error state.
3850    */
3851   template<typename _RealType, typename _CharT, typename _Traits>
3852     std::basic_ostream<_CharT, _Traits>&
3853     operator<<(std::basic_ostream<_CharT, _Traits>&,
3854                const std::weibull_distribution<_RealType>&);
3855
3856   /**
3857    * @brief Extracts a %weibull_distribution random number distribution
3858    * @p __x from the input stream @p __is.
3859    *
3860    * @param __is An input stream.
3861    * @param __x A %weibull_distribution random number
3862    *            generator engine.
3863    *
3864    * @returns The input stream with @p __x extracted or in an error state.
3865    */
3866   template<typename _RealType, typename _CharT, typename _Traits>
3867     std::basic_istream<_CharT, _Traits>&
3868     operator>>(std::basic_istream<_CharT, _Traits>&,
3869                std::weibull_distribution<_RealType>&);
3870
3871
3872   /**
3873    * @brief A extreme_value_distribution random number distribution.
3874    *
3875    * The formula for the normal probability mass function is
3876    * @f$ p(x|a,b) = \frac{1}{b}
3877    *                \exp( \frac{a-x}{b} - \exp(\frac{a-x}{b})) @f$
3878    */
3879   template<typename _RealType = double>
3880     class extreme_value_distribution
3881     {
3882     public:
3883       /** The type of the range of the distribution. */
3884       typedef _RealType result_type;
3885       /** Parameter type. */
3886       struct param_type
3887       {
3888         typedef extreme_value_distribution<_RealType> distribution_type;
3889
3890         explicit
3891         param_type(_RealType __a = _RealType(0),
3892                    _RealType __b = _RealType(1))
3893         : _M_a(__a), _M_b(__b)
3894         { }
3895
3896         _RealType
3897         a() const
3898         { return _M_a; }
3899
3900         _RealType
3901         b() const
3902         { return _M_b; }
3903
3904       private:
3905         _RealType _M_a;
3906         _RealType _M_b;
3907       };
3908
3909       explicit
3910       extreme_value_distribution(_RealType __a = _RealType(0),
3911                                  _RealType __b = _RealType(1))
3912       : _M_param(__a, __b)
3913       { }
3914
3915       explicit
3916       extreme_value_distribution(const param_type& __p)
3917       : _M_param(__p)
3918       { }
3919
3920       /**
3921        * @brief Resets the distribution state.
3922        */
3923       void
3924       reset()
3925       { }
3926
3927       /**
3928        * @brief Return the @f$ a @f$ parameter of the distribution.
3929        */
3930       _RealType
3931       a() const
3932       { return _M_param.a(); }
3933
3934       /**
3935        * @brief Return the @f$ b @f$ parameter of the distribution.
3936        */
3937       _RealType
3938       b() const
3939       { return _M_param.b(); }
3940
3941       /**
3942        * @brief Returns the parameter set of the distribution.
3943        */
3944       param_type
3945       param() const
3946       { return _M_param; }
3947
3948       /**
3949        * @brief Sets the parameter set of the distribution.
3950        * @param __param The new parameter set of the distribution.
3951        */
3952       void
3953       param(const param_type& __param)
3954       { _M_param = __param; }
3955
3956       /**
3957        * @brief Returns the greatest lower bound value of the distribution.
3958        */
3959       result_type
3960       min() const
3961       { return std::numeric_limits<result_type>::min(); }
3962
3963       /**
3964        * @brief Returns the least upper bound value of the distribution.
3965        */
3966       result_type
3967       max() const
3968       { return std::numeric_limits<result_type>::max(); }
3969
3970       template<typename _UniformRandomNumberGenerator>
3971         result_type
3972         operator()(_UniformRandomNumberGenerator& __urng)
3973         { return this->operator()(__urng, this->param()); }
3974
3975       template<typename _UniformRandomNumberGenerator>
3976         result_type
3977         operator()(_UniformRandomNumberGenerator& __urng,
3978                    const param_type& __p);
3979
3980     private:
3981       param_type _M_param;
3982     };
3983
3984   /**
3985    * @brief Inserts a %extreme_value_distribution random number distribution
3986    * @p __x into the output stream @p __os.
3987    *
3988    * @param __os An output stream.
3989    * @param __x  A %extreme_value_distribution random number distribution.
3990    *
3991    * @returns The output stream with the state of @p __x inserted or in
3992    * an error state.
3993    */
3994   template<typename _RealType, typename _CharT, typename _Traits>
3995     std::basic_ostream<_CharT, _Traits>&
3996     operator<<(std::basic_ostream<_CharT, _Traits>&,
3997                const std::extreme_value_distribution<_RealType>&);
3998
3999   /**
4000    * @brief Extracts a %extreme_value_distribution random number
4001    *        distribution @p __x from the input stream @p __is.
4002    *
4003    * @param __is An input stream.
4004    * @param __x A %extreme_value_distribution random number
4005    *            generator engine.
4006    *
4007    * @returns The input stream with @p __x extracted or in an error state.
4008    */
4009   template<typename _RealType, typename _CharT, typename _Traits>
4010     std::basic_istream<_CharT, _Traits>&
4011     operator>>(std::basic_istream<_CharT, _Traits>&,
4012                std::extreme_value_distribution<_RealType>&);
4013
4014
4015   /**
4016    * @brief A discrete_distribution random number distribution.
4017    *
4018    * The formula for the discrete probability mass function is
4019    *
4020    */
4021   template<typename _IntType = int>
4022     class discrete_distribution
4023     {
4024       __glibcxx_class_requires(_IntType, _IntegerConcept)
4025
4026     public:
4027       /** The type of the range of the distribution. */
4028       typedef _IntType result_type;
4029       /** Parameter type. */
4030       struct param_type
4031       {
4032         typedef discrete_distribution<_IntType> distribution_type;
4033         friend class discrete_distribution<_IntType>;
4034
4035         param_type()
4036         : _M_prob(), _M_cp()
4037         { _M_initialize(); }
4038
4039         template<typename _InputIterator>
4040           param_type(_InputIterator __wbegin,
4041                      _InputIterator __wend)
4042           : _M_prob(__wbegin, __wend), _M_cp()
4043           { _M_initialize(); }
4044
4045         param_type(initializer_list<double> __wil)
4046         : _M_prob(__wil.begin(), __wil.end()), _M_cp()
4047         { _M_initialize(); }
4048
4049         template<typename _Func>
4050           param_type(size_t __nw, double __xmin, double __xmax,
4051                      _Func __fw);
4052
4053         std::vector<double>
4054         probabilities() const
4055         { return _M_prob; }
4056
4057       private:
4058         void
4059         _M_initialize();
4060
4061         std::vector<double> _M_prob;
4062         std::vector<double> _M_cp;
4063       };
4064
4065       discrete_distribution()
4066       : _M_param()
4067       { }
4068
4069       template<typename _InputIterator>
4070         discrete_distribution(_InputIterator __wbegin,
4071                               _InputIterator __wend)
4072         : _M_param(__wbegin, __wend)
4073         { }
4074
4075       discrete_distribution(initializer_list<double> __wl)
4076       : _M_param(__wl)
4077       { }
4078
4079       template<typename _Func>
4080         discrete_distribution(size_t __nw, double __xmin, double __xmax,
4081                               _Func __fw)
4082         : _M_param(__nw, __xmin, __xmax, __fw)
4083         { }
4084
4085       explicit
4086       discrete_distribution(const param_type& __p)
4087       : _M_param(__p)
4088       { }
4089
4090       /**
4091        * @brief Resets the distribution state.
4092        */
4093       void
4094       reset()
4095       { }
4096
4097       /**
4098        * @brief Returns the probabilities of the distribution.
4099        */
4100       std::vector<double>
4101       probabilities() const
4102       { return _M_param.probabilities(); }
4103
4104       /**
4105        * @brief Returns the parameter set of the distribution.
4106        */
4107       param_type
4108       param() const
4109       { return _M_param; }
4110
4111       /**
4112        * @brief Sets the parameter set of the distribution.
4113        * @param __param The new parameter set of the distribution.
4114        */
4115       void
4116       param(const param_type& __param)
4117       { _M_param = __param; }
4118
4119       /**
4120        * @brief Returns the greatest lower bound value of the distribution.
4121        */
4122       result_type
4123       min() const
4124       { return result_type(0); }
4125
4126       /**
4127        * @brief Returns the least upper bound value of the distribution.
4128        */
4129       result_type
4130       max() const
4131       { return this->_M_param._M_prob.size() - 1; }
4132
4133       template<typename _UniformRandomNumberGenerator>
4134         result_type
4135         operator()(_UniformRandomNumberGenerator& __urng)
4136         { return this->operator()(__urng, this->param()); }
4137
4138       template<typename _UniformRandomNumberGenerator>
4139         result_type
4140         operator()(_UniformRandomNumberGenerator& __urng,
4141                    const param_type& __p);
4142
4143       /**
4144        * @brief Inserts a %discrete_distribution random number distribution
4145        * @p __x into the output stream @p __os.
4146        *
4147        * @param __os An output stream.
4148        * @param __x  A %discrete_distribution random number distribution.
4149        *
4150        * @returns The output stream with the state of @p __x inserted or in
4151        * an error state.
4152        */
4153       template<typename _IntType1, typename _CharT, typename _Traits>
4154         friend std::basic_ostream<_CharT, _Traits>&
4155         operator<<(std::basic_ostream<_CharT, _Traits>&,
4156                    const std::discrete_distribution<_IntType1>&);
4157
4158       /**
4159        * @brief Extracts a %discrete_distribution random number distribution
4160        * @p __x from the input stream @p __is.
4161        *
4162        * @param __is An input stream.
4163        * @param __x A %discrete_distribution random number
4164        *            generator engine.
4165        *
4166        * @returns The input stream with @p __x extracted or in an error
4167        *          state.
4168        */
4169       template<typename _IntType1, typename _CharT, typename _Traits>
4170         friend std::basic_istream<_CharT, _Traits>&
4171         operator>>(std::basic_istream<_CharT, _Traits>&,
4172                    std::discrete_distribution<_IntType1>&);
4173
4174     private:
4175       param_type _M_param;
4176     };
4177
4178
4179   /**
4180    * @brief A piecewise_constant_distribution random number distribution.
4181    *
4182    * The formula for the piecewise constant probability mass function is
4183    *
4184    */
4185   template<typename _RealType = double>
4186     class piecewise_constant_distribution
4187     {
4188     public:
4189       /** The type of the range of the distribution. */
4190       typedef _RealType result_type;
4191       /** Parameter type. */
4192       struct param_type
4193       {
4194         typedef piecewise_constant_distribution<_RealType> distribution_type;
4195         friend class piecewise_constant_distribution<_RealType>;
4196
4197         param_type()
4198         : _M_int(), _M_den(), _M_cp()
4199         { _M_initialize(); }
4200
4201         template<typename _InputIteratorB, typename _InputIteratorW>
4202           param_type(_InputIteratorB __bfirst,
4203                      _InputIteratorB __bend,
4204                      _InputIteratorW __wbegin);
4205
4206         template<typename _Func>
4207           param_type(initializer_list<_RealType> __bi, _Func __fw);
4208
4209         template<typename _Func>
4210           param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
4211                      _Func __fw);
4212
4213         std::vector<_RealType>
4214         intervals() const
4215         { return _M_int; }
4216
4217         std::vector<double>
4218         densities() const
4219         { return _M_den; }
4220
4221       private:
4222         void
4223         _M_initialize();
4224
4225         std::vector<_RealType> _M_int;
4226         std::vector<double> _M_den;
4227         std::vector<double> _M_cp;
4228       };
4229
4230       explicit
4231       piecewise_constant_distribution()
4232       : _M_param()
4233       { }
4234
4235       template<typename _InputIteratorB, typename _InputIteratorW>
4236         piecewise_constant_distribution(_InputIteratorB __bfirst,
4237                                         _InputIteratorB __bend,
4238                                         _InputIteratorW __wbegin)
4239         : _M_param(__bfirst, __bend, __wbegin)
4240         { }
4241
4242       template<typename _Func>
4243         piecewise_constant_distribution(initializer_list<_RealType> __bl,
4244                                         _Func __fw)
4245         : _M_param(__bl, __fw)
4246         { }
4247
4248       template<typename _Func>
4249         piecewise_constant_distribution(size_t __nw,
4250                                         _RealType __xmin, _RealType __xmax,
4251                                         _Func __fw)
4252         : _M_param(__nw, __xmin, __xmax, __fw)
4253         { }
4254
4255       explicit
4256       piecewise_constant_distribution(const param_type& __p)
4257       : _M_param(__p)
4258       { }
4259
4260       /**
4261        * @brief Resets the distribution state.
4262        */
4263       void
4264       reset()
4265       { }
4266
4267       /**
4268        * @brief Returns a vector of the intervals.
4269        */
4270       std::vector<_RealType>
4271       intervals() const
4272       { return _M_param.intervals(); }
4273
4274       /**
4275        * @brief Returns a vector of the probability densities.
4276        */
4277       std::vector<double>
4278       densities() const
4279       { return _M_param.densities(); }
4280
4281       /**
4282        * @brief Returns the parameter set of the distribution.
4283        */
4284       param_type
4285       param() const
4286       { return _M_param; }
4287
4288       /**
4289        * @brief Sets the parameter set of the distribution.
4290        * @param __param The new parameter set of the distribution.
4291        */
4292       void
4293       param(const param_type& __param)
4294       { _M_param = __param; }
4295
4296       /**
4297        * @brief Returns the greatest lower bound value of the distribution.
4298        */
4299       result_type
4300       min() const
4301       { return this->_M_param._M_int.front(); }
4302
4303       /**
4304        * @brief Returns the least upper bound value of the distribution.
4305        */
4306       result_type
4307       max() const
4308       { return this->_M_param._M_int.back(); }
4309
4310       template<typename _UniformRandomNumberGenerator>
4311         result_type
4312         operator()(_UniformRandomNumberGenerator& __urng)
4313         { return this->operator()(__urng, this->param()); }
4314
4315       template<typename _UniformRandomNumberGenerator>
4316         result_type
4317         operator()(_UniformRandomNumberGenerator& __urng,
4318                    const param_type& __p);
4319
4320       /**
4321        * @brief Inserts a %piecewise_constan_distribution random
4322        *        number distribution @p __x into the output stream @p __os.
4323        *
4324        * @param __os An output stream.
4325        * @param __x  A %piecewise_constan_distribution random number
4326        *             distribution.
4327        *
4328        * @returns The output stream with the state of @p __x inserted or in
4329        * an error state.
4330        */
4331       template<typename _RealType1, typename _CharT, typename _Traits>
4332         friend std::basic_ostream<_CharT, _Traits>&
4333         operator<<(std::basic_ostream<_CharT, _Traits>&,
4334                    const std::piecewise_constant_distribution<_RealType1>&);
4335
4336       /**
4337        * @brief Extracts a %piecewise_constan_distribution random
4338        *        number distribution @p __x from the input stream @p __is.
4339        *
4340        * @param __is An input stream.
4341        * @param __x A %piecewise_constan_distribution random number
4342        *            generator engine.
4343        *
4344        * @returns The input stream with @p __x extracted or in an error
4345        *          state.
4346        */
4347       template<typename _RealType1, typename _CharT, typename _Traits>
4348         friend std::basic_istream<_CharT, _Traits>&
4349         operator>>(std::basic_istream<_CharT, _Traits>&,
4350                    std::piecewise_constant_distribution<_RealType1>&);
4351
4352     private:
4353       param_type _M_param;
4354     };
4355
4356
4357   /**
4358    * @brief A piecewise_linear_distribution random number distribution.
4359    *
4360    * The formula for the piecewise linear probability mass function is
4361    *
4362    */
4363   template<typename _RealType = double>
4364     class piecewise_linear_distribution
4365     {
4366     public:
4367       /** The type of the range of the distribution. */
4368       typedef _RealType result_type;
4369       /** Parameter type. */
4370       struct param_type
4371       {
4372         typedef piecewise_linear_distribution<_RealType> distribution_type;
4373         friend class piecewise_linear_distribution<_RealType>;
4374
4375         param_type()
4376         : _M_int(), _M_den(), _M_cp(), _M_m()
4377         { _M_initialize(); }
4378
4379         template<typename _InputIteratorB, typename _InputIteratorW>
4380           param_type(_InputIteratorB __bfirst,
4381                      _InputIteratorB __bend,
4382                      _InputIteratorW __wbegin);
4383
4384         template<typename _Func>
4385           param_type(initializer_list<_RealType> __bl, _Func __fw);
4386
4387         template<typename _Func>
4388           param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
4389                      _Func __fw);
4390
4391         std::vector<_RealType>
4392         intervals() const
4393         { return _M_int; }
4394
4395         std::vector<double>
4396         densities() const
4397         { return _M_den; }
4398
4399       private:
4400         void
4401         _M_initialize();
4402
4403         std::vector<_RealType> _M_int;
4404         std::vector<double> _M_den;
4405         std::vector<double> _M_cp;
4406         std::vector<double> _M_m;
4407       };
4408
4409       explicit
4410       piecewise_linear_distribution()
4411       : _M_param()
4412       { }
4413
4414       template<typename _InputIteratorB, typename _InputIteratorW>
4415         piecewise_linear_distribution(_InputIteratorB __bfirst,
4416                                       _InputIteratorB __bend,
4417                                       _InputIteratorW __wbegin)
4418         : _M_param(__bfirst, __bend, __wbegin)
4419         { }
4420
4421       template<typename _Func>
4422         piecewise_linear_distribution(initializer_list<_RealType> __bl,
4423                                       _Func __fw)
4424         : _M_param(__bl, __fw)
4425         { }
4426
4427       template<typename _Func>
4428         piecewise_linear_distribution(size_t __nw,
4429                                       _RealType __xmin, _RealType __xmax,
4430                                       _Func __fw)
4431         : _M_param(__nw, __xmin, __xmax, __fw)
4432         { }
4433
4434       explicit
4435       piecewise_linear_distribution(const param_type& __p)
4436       : _M_param(__p)
4437       { }
4438
4439       /**
4440        * Resets the distribution state.
4441        */
4442       void
4443       reset()
4444       { }
4445
4446       /**
4447        * @brief Return the intervals of the distribution.
4448        */
4449       std::vector<_RealType>
4450       intervals() const
4451       { return _M_param.intervals(); }
4452
4453       /**
4454        * @brief Return a vector of the probability densities of the
4455        *        distribution.
4456        */
4457       std::vector<double>
4458       densities() const
4459       { return _M_param.densities(); }
4460
4461       /**
4462        * @brief Returns the parameter set of the distribution.
4463        */
4464       param_type
4465       param() const
4466       { return _M_param; }
4467
4468       /**
4469        * @brief Sets the parameter set of the distribution.
4470        * @param __param The new parameter set of the distribution.
4471        */
4472       void
4473       param(const param_type& __param)
4474       { _M_param = __param; }
4475
4476       /**
4477        * @brief Returns the greatest lower bound value of the distribution.
4478        */
4479       result_type
4480       min() const
4481       { return this->_M_param._M_int.front(); }
4482
4483       /**
4484        * @brief Returns the least upper bound value of the distribution.
4485        */
4486       result_type
4487       max() const
4488       { return this->_M_param._M_int.back(); }
4489
4490       template<typename _UniformRandomNumberGenerator>
4491         result_type
4492         operator()(_UniformRandomNumberGenerator& __urng)
4493         { return this->operator()(__urng, this->param()); }
4494
4495       template<typename _UniformRandomNumberGenerator>
4496         result_type
4497         operator()(_UniformRandomNumberGenerator& __urng,
4498                    const param_type& __p);
4499
4500       /**
4501        * @brief Inserts a %piecewise_linear_distribution random number
4502        *        distribution @p __x into the output stream @p __os.
4503        *
4504        * @param __os An output stream.
4505        * @param __x  A %piecewise_linear_distribution random number
4506        *             distribution.
4507        *
4508        * @returns The output stream with the state of @p __x inserted or in
4509        *          an error state.
4510        */
4511       template<typename _RealType1, typename _CharT, typename _Traits>
4512         friend std::basic_ostream<_CharT, _Traits>&
4513         operator<<(std::basic_ostream<_CharT, _Traits>&,
4514                    const std::piecewise_linear_distribution<_RealType1>&);
4515
4516       /**
4517        * @brief Extracts a %piecewise_linear_distribution random number
4518        *        distribution @p __x from the input stream @p __is.
4519        *
4520        * @param __is An input stream.
4521        * @param __x  A %piecewise_linear_distribution random number
4522        *             generator engine.
4523        *
4524        * @returns The input stream with @p __x extracted or in an error
4525        *          state.
4526        */
4527       template<typename _RealType1, typename _CharT, typename _Traits>
4528         friend std::basic_istream<_CharT, _Traits>&
4529         operator>>(std::basic_istream<_CharT, _Traits>&,
4530                    std::piecewise_linear_distribution<_RealType1>&);
4531
4532     private:
4533       param_type _M_param;
4534     };
4535
4536
4537   /* @} */ // group std_random_distributions_poisson
4538
4539   /* @} */ // group std_random_distributions
4540
4541   /**
4542    * @addtogroup std_random_utilities Random Number Utilities
4543    * @ingroup std_random
4544    * @{
4545    */
4546
4547   /**
4548    * @brief The seed_seq class generates sequences of seeds for random
4549    *        number generators.
4550    */
4551   class seed_seq
4552   {
4553
4554   public:
4555     /** The type of the seed vales. */
4556     typedef uint_least32_t result_type;
4557
4558     /** Default constructor. */
4559     seed_seq()
4560     : _M_v()
4561     { }
4562
4563     template<typename _IntType>
4564       seed_seq(std::initializer_list<_IntType> il);
4565
4566     template<typename _InputIterator>
4567       seed_seq(_InputIterator __begin, _InputIterator __end);
4568
4569     // generating functions
4570     template<typename _RandomAccessIterator>
4571       void
4572       generate(_RandomAccessIterator __begin, _RandomAccessIterator __end);
4573
4574     // property functions
4575     size_t size() const
4576     { return _M_v.size(); }
4577
4578     template<typename OutputIterator>
4579       void
4580       param(OutputIterator __dest) const
4581       { std::copy(_M_v.begin(), _M_v.end(), __dest); }
4582
4583   private:
4584     ///
4585     std::vector<result_type> _M_v;
4586   };
4587
4588   /* @} */ // group std_random_utilities
4589
4590   /* @} */ // group std_random
4591
4592 }
4593