contrib/gcc-4.4/libstdc++-v3/include/tr1_impl/random

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