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