mingw/lib/gcc/mingw32/4.3.3/include/c++/tr1_impl/random

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