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

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