contrib/gcc-4.7/libstdc++-v3/include/tr1/random.h

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