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

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