contrib/libstdc++/include/tr1/random

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