libstdc++-v3/include/tr1/random

   1 // random number generation -*- C++ -*-
   2
   3 // Copyright (C) 2006 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 #ifndef _STD_TR1_RANDOM
  31 #define _STD_TR1_RANDOM 1
  32
  33 /**
  34  * @file
  35  * This is a TR1 C++ Library header.
  36  */
  37
  38 #include <algorithm>
  39 #include <bits/concept_check.h>
  40 #include <bits/cpp_type_traits.h>
  41 #include <cmath>
  42 #include <debug/debug.h>
  43 #include <iterator>
  44 #include <iosfwd>
  45 #include <limits>
  46 #include <tr1/type_traits>
  47
  48 namespace std
  49 {
  50 _GLIBCXX_BEGIN_NAMESPACE(tr1)
  51
  52   // [5.1] Random number generation
  53
  54   /**
  55    * @addtogroup tr1_random Random Number Generation
  56    * A facility for generating random numbers on selected distributions.
  57    * @{
  58    */
  59
  60   /*
  61    * Implementation-space details.
  62    */
  63   namespace _Private
  64   {
  65     // Type selectors -- are these already implemented elsewhere?
  66     template<bool, typename _TpTrue, typename _TpFalse>
  67       struct _Select
  68       {
  69         typedef _TpTrue _Type;
  70       };
  71
  72     template<typename _TpTrue, typename _TpFalse>
  73       struct _Select<false, _TpTrue, _TpFalse>
  74       {
  75         typedef _TpFalse _Type;
  76       };
  77
  78     /*
  79      * An adaptor class for converting the output of any Generator into
  80      * the input for a specific Distribution.
  81      */
  82     template<typename _Generator, typename _Distribution>
  83       struct _Adaptor
  84       {
  85         typedef typename _Generator::result_type   generated_type;
  86         typedef typename _Distribution::input_type result_type;
  87
  88       public:
  89         _Adaptor(const _Generator& __g)
  90         : _M_g(__g) { }
  91
  92         result_type
  93         operator()();
  94
  95       private:
  96         _Generator _M_g;
  97       };
  98
  99     /*
 100      * Converts a value generated by the adapted random number generator into a
 101      * value in the input domain for the dependent random number distribution.
 102      *
 103      * Because the type traits are compile time constants only the appropriate
 104      * clause of the if statements will actually be emitted by the compiler.
 105      */
 106     template<typename _Generator, typename _Distribution>
 107       typename _Adaptor<_Generator, _Distribution>::result_type
 108       _Adaptor<_Generator, _Distribution>::
 109       operator()()
 110       {
 111         result_type __return_value = 0;
 112         if (is_integral<generated_type>::value
 113             && is_integral<result_type>::value)
 114           __return_value = _M_g();
 115         else if (is_integral<generated_type>::value
 116                  && !is_integral<result_type>::value)
 117           __return_value = result_type(_M_g())
 118             / result_type(_M_g.max() - _M_g.min() + 1);
 119         else if (!is_integral<generated_type>::value
 120                  && !is_integral<result_type>::value)
 121           __return_value = result_type(_M_g())
 122             / result_type(_M_g.max() - _M_g.min());
 123         return __return_value;
 124       }
 125
 126   } // namespace std::tr1::_Private
 127
 128
 129   /**
 130    * Produces random numbers on a given disribution function using a un uniform
 131    * random number generation engine.
 132    *
 133    * @todo the engine_value_type needs to be studied more carefully.
 134    */
 135   template<typename _Generator, typename _Dist>
 136     class variate_generator
 137     {
 138       // Concept requirements.
 139       __glibcxx_class_requires(_Generator, _CopyConstructibleConcept)
 140       //  __glibcxx_class_requires(_Generator, _GeneratorConcept)
 141       //  __glibcxx_class_requires(_Dist,      _GeneratorConcept)
 142
 143     public:
 144       typedef _Generator                             engine_type;
 145       typedef _Private::_Adaptor<_Generator, _Dist>  engine_value_type;
 146       typedef _Dist                                  distribution_type;
 147       typedef typename _Dist::result_type            result_type;
 148
 149       // tr1:5.1.1 table 5.1 requirement
 150       typedef typename std::__enable_if<result_type,
 151                                         is_arithmetic<result_type>::value
 152         >::__type _IsValidType;
 153
 154     public:
 155       /**
 156        * Constructs a variate generator with the uniform random number
 157        * generator @p __eng for the random distribution @p __dist.
 158        *
 159        * @throws Any exceptions which may thrown by the copy constructors of
 160        * the @p _Generator or @p _Dist objects.
 161        */
 162       variate_generator(engine_type __eng, distribution_type __dist)
 163       : _M_engine(__eng), _M_dist(__dist) { }
 164
 165       /**
 166        * Gets the next generated value on the distribution.
 167        */
 168       result_type
 169       operator()();
 170
 171       template<typename _Tp>
 172         result_type
 173         operator()(_Tp __value);
 174
 175       /**
 176        * Gets a reference to the underlying uniform random number generator
 177        * object.
 178        */
 179       engine_value_type&
 180       engine()
 181       { return _M_engine; }
 182
 183       /**
 184        * Gets a const reference to the underlying uniform random number
 185        * generator object.
 186        */
 187       const engine_value_type&
 188       engine() const
 189       { return _M_engine; }
 190
 191       /**
 192        * Gets a reference to the underlying random distribution.
 193        */
 194       distribution_type&
 195       distribution()
 196       { return _M_dist; }
 197
 198       /**
 199        * Gets a const reference to the underlying random distribution.
 200        */
 201       const distribution_type&
 202       distribution() const
 203       { return _M_dist; }
 204
 205       /**
 206        * Gets the closed lower bound of the distribution interval.
 207        */
 208       result_type
 209       min() const
 210       { return this->distribution().min(); }
 211
 212       /**
 213        * Gets the closed upper bound of the distribution interval.
 214        */
 215       result_type
 216       max() const
 217       { return this->distribution().max(); }
 218
 219     private:
 220       engine_value_type _M_engine;
 221       distribution_type _M_dist;
 222     };
 223
 224   /**
 225    * Gets the next random value on the given distribution.
 226    */
 227   template<typename _Generator, typename _Dist>
 228     typename variate_generator<_Generator, _Dist>::result_type
 229     variate_generator<_Generator, _Dist>::
 230     operator()()
 231     { return _M_dist(_M_engine); }
 232
 233   /**
 234    * WTF?
 235    */
 236   template<typename _Generator, typename _Dist>
 237     template<typename _Tp>
 238       typename variate_generator<_Generator, _Dist>::result_type
 239       variate_generator<_Generator, _Dist>::
 240       operator()(_Tp __value)
 241       { return _M_dist(_M_engine, __value); }
 242
 243
 244   /**
 245    * @addtogroup tr1_random_generators Random Number Generators
 246    * @ingroup tr1_random
 247    *
 248    * These classes define objects which provide random or pseudorandom numbers,
 249    * either from a discrete or a continuous interval.  The random number
 250    * generator supplied as a part of this library are all uniform random number
 251    * generators which provide a sequence of random number uniformly distributed
 252    * over their range.
 253    *
 254    * A number generator is a function object with an operator() that takes zero
 255    * arguments and returns a number.
 256    *
 257    * A compliant random number generator must satisy the following requirements.
 258    * <table border=1 cellpadding=10 cellspacing=0>
 259    * <caption align=top>Random Number Generator Requirements</caption>
 260    * <tr><td>To be documented.</td></tr>
 261    * </table>
 262    *
 263    * @{
 264    */
 265
 266   /**
 267    * @brief A model of a linear congruential random number generator.
 268    *
 269    * A random number generator that produces pseudorandom numbers using the
 270    * linear function @f$x_{i+1}\leftarrow(ax_{i} + c) \bmod m @f$.
 271    *
 272    * The template parameter @p _UIntType must be an unsigned integral type
 273    * large enough to store values up to (__m-1). If the template parameter
 274    * @p __m is 0, the modulus @p __m used is
 275    * std::numeric_limits<_UIntType>::max() plus 1. Otherwise, the template
 276    * parameters @p __a and @p __c must be less than @p __m.
 277    *
 278    * The size of the state is @f$ 1 @f$.
 279    */
 280   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 281     class linear_congruential
 282     {
 283       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
 284       //  __glibcpp_class_requires(__a < __m && __c < __m)
 285
 286     public:
 287       /** The type of the generated random value. */
 288       typedef _UIntType result_type;
 289
 290       /** The multiplier. */
 291       static const _UIntType multiplier = __a;
 292       /** An increment. */
 293       static const _UIntType increment = __c;
 294       /** The modulus. */
 295       static const _UIntType modulus = __m;
 296
 297       /**
 298        * Constructs a %linear_congruential random number generator engine with
 299        * seed @p __s.  The default seed value is 1.
 300        *
 301        * @param __s The initial seed value.
 302        */
 303       explicit linear_congruential(unsigned long __s = 1);
 304
 305       /**
 306        * Constructs a %linear_congruential random number generator engine
 307        * seeded from the generator function @p __g.
 308        *
 309        * @param __g The seed generator function.
 310        */
 311       template<class _Gen>
 312         linear_congruential(_Gen& __g);
 313
 314       /**
 315        * Reseeds the %linear_congruential random number generator engine
 316        * sequence to the seed @g __s.
 317        *
 318        * @param __s The new seed.
 319        */
 320       void
 321       seed(unsigned long __s = 1);
 322
 323       /**
 324        * Reseeds the %linear_congruential random number generator engine
 325        * sequence using values from the generator function @p __g.
 326        *
 327        * @param __g the seed generator function.
 328        */
 329       template<class _Gen>
 330         void
 331         seed(_Gen& __g)
 332         { seed(__g, typename is_fundamental<_Gen>::type()); }
 333
 334       /**
 335        * Gets the smallest possible value in the output range.
 336        */
 337       result_type
 338       min() const;
 339
 340       /**
 341        * Gets the largest possible value in the output range.
 342        */
 343       result_type
 344       max() const;
 345
 346       /**
 347        * Gets the next random number in the sequence.
 348        */
 349       result_type
 350       operator()();
 351
 352       /**
 353        * Compares two linear congruential random number generator objects of the
 354        * same type for equality.
 355        *
 356        * @param __lhs A linear congruential random number generator object.
 357        * @param __rhs Another linear congruential random number generator obj.
 358        *
 359        * @returns true if the two objects are equal, false otherwise.
 360        */
 361       friend bool
 362       operator==(const linear_congruential& __lhs,
 363                  const linear_congruential& __rhs)
 364       { return __lhs._M_x == __rhs._M_x; }
 365
 366       /**
 367        * Compares two linear congruential random number generator objects of the
 368        * same type for inequality.
 369        *
 370        * @param __lhs A linear congruential random number generator object.
 371        * @param __rhs Another linear congruential random number generator obj.
 372        *
 373        * @returns true if the two objects are not equal, false otherwise.
 374        */
 375       friend bool
 376       operator!=(const linear_congruential& __lhs,
 377                  const linear_congruential& __rhs)
 378       { return !(__lhs == __rhs); }
 379
 380       /**
 381        * Writes the textual representation of the state x(i) of x to @p __os.
 382        *
 383        * @param __os  The output stream.
 384        * @param __lcr A linear_congruential random number generator.
 385        * @returns __os.
 386        */
 387       template<typename _CharT, typename _Traits>
 388         friend std::basic_ostream<_CharT, _Traits>&
 389         operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 390                    const linear_congruential& __lcr)
 391         { return __os << __lcr._M_x; }
 392
 393       /**
 394        * Sets the state of the engine by reading its textual
 395        * representation from @p __is.
 396        *
 397        * The textual representation must have been previously written using an
 398        * output stream whose imbued locale and whose type's template
 399        * specialization arguments _CharT and _Traits were the same as those of
 400        * @p __is.
 401        *
 402        * @param __is  The input stream.
 403        * @param __lcr A linear_congruential random number generator.
 404        * @returns __is.
 405        */
 406       template<typename _CharT, typename _Traits>
 407         friend std::basic_istream<_CharT, _Traits>&
 408         operator>>(std::basic_istream<_CharT, _Traits>& __is,
 409                    linear_congruential& __lcr)
 410         { return __is >> __lcr._M_x; }
 411
 412     private:
 413       template<class _Gen>
 414         void
 415         seed(_Gen& __g, true_type)
 416         { return seed(static_cast<unsigned long>(__g)); }
 417
 418       template<class _Gen>
 419         void
 420         seed(_Gen& __g, false_type);
 421
 422     private:
 423       _UIntType _M_x;
 424     };
 425
 426   /**
 427    * The classic Minimum Standard rand0 of Lewis, Goodman, and Miller.
 428    */
 429   typedef linear_congruential<unsigned int, 16807, 0, 2147483647> minstd_rand0;
 430
 431   /**
 432    * An alternative LCR (Lehmer Generator function) .
 433    */
 434   typedef linear_congruential<unsigned int, 48271, 0, 2147483647> minstd_rand;
 435
 436
 437   /**
 438    * A generalized feedback shift register discrete random number generator.
 439    *
 440    * This algorithm avoind multiplication and division and is designed to be
 441    * friendly to a pipelined architecture.  If the parameters are chosen
 442    * correctly, this generator will produce numbers with a very long period and
 443    * fairly good apparent entropy, although still not cryptographically strong.
 444    *
 445    * The best way to use this generator is with the predefined mt19937 class.
 446    *
 447    * This algorithm was originally invented by Makoto Matsumoto and
 448    * Takuji Nishimura.
 449    *
 450    * @var word_size   The number of bits in each element of the state vector.
 451    * @var state_size  The degree of recursion.
 452    * @var shift_size  The period parameter.
 453    * @var mask_bits   The separation point bit index.
 454    * @var parameter_a The last row of the twist matrix.
 455    * @var output_u    The first right-shift tempering matrix parameter.
 456    * @var output_s    The first left-shift tempering matrix parameter.
 457    * @var output_b    The first left-shift tempering matrix mask.
 458    * @var output_t    The second left-shift tempering matrix parameter.
 459    * @var output_c    The second left-shift tempering matrix mask.
 460    * @var output_l    The second right-shift tempering matrix parameter.
 461    */
 462   template<class _UIntType, int __w, int __n, int __m, int __r,
 463            _UIntType __a, int __u, int __s, _UIntType __b, int __t,
 464            _UIntType __c, int __l>
 465     class mersenne_twister
 466     {
 467       __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
 468
 469     public:
 470       // types
 471       typedef _UIntType result_type ;
 472
 473       // parameter values
 474       static const int       word_size   = __w;
 475       static const int       state_size  = __n;
 476       static const int       shift_size  = __m;
 477       static const int       mask_bits   = __r;
 478       static const _UIntType parameter_a = __a;
 479       static const int       output_u    = __u;
 480       static const int       output_s    = __s;
 481       static const _UIntType output_b    = __b;
 482       static const int       output_t    = __t;
 483       static const _UIntType output_c    = __c;
 484       static const int       output_l    = __l;
 485
 486       // constructors and member function
 487       mersenne_twister()
 488       { seed(); }
 489
 490       explicit
 491       mersenne_twister(unsigned long __value)
 492       { seed(__value); }
 493
 494       template<class _Gen>
 495         mersenne_twister(_Gen& __g)
 496         { seed(__g); }
 497
 498       void
 499       seed()
 500       { seed(5489UL); }
 501
 502       void
 503       seed(unsigned long __value);
 504
 505       template<class _Gen>
 506         void
 507         seed(_Gen& __g)
 508         { seed(__g, typename is_fundamental<_Gen>::type()); }
 509
 510       result_type
 511       min() const
 512       { return 0; };
 513
 514       result_type
 515       max() const;
 516
 517       result_type
 518       operator()();
 519
 520     private:
 521       template<class _Gen>
 522         void
 523         seed(_Gen& __g, true_type)
 524         { return seed(static_cast<unsigned long>(__g)); }
 525
 526       template<class _Gen>
 527         void
 528         seed(_Gen& __g, false_type);
 529
 530     private:
 531       _UIntType _M_x[state_size];
 532       int       _M_p;
 533     };
 534
 535   /**
 536    * The classic Mersenne Twister.
 537    *
 538    * Reference:
 539    * M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
 540    * Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions
 541    * on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
 542    */
 543   typedef mersenne_twister<
 544     unsigned long, 32, 624, 397, 31,
 545     0x9908b0dful, 11, 7,
 546     0x9d2c5680ul, 15,
 547     0xefc60000ul, 18
 548     > mt19937;
 549
 550
 551   /**
 552    * @brief The Marsaglia-Zaman generator.
 553    *
 554    * This is a model of a Generalized Fibonacci discrete random number
 555    * generator, sometimes referred to as the SWC generator.
 556    *
 557    * A discrete random number generator that produces pseudorandom numbers using
 558    * @f$x_{i}\leftarrow(x_{i - s} - x_{i - r} - carry_{i-1}) \bmod m @f$.
 559    *
 560    * The size of the state is @f$ r @f$
 561    * and the maximum period of the generator is @f$ m^r - m^s -1 @f$.
 562    *
 563    * N1688[4.13] says "the template parameter _IntType shall denote an integral
 564    * type large enough to store values up to m."
 565    *
 566    * @if maint
 567    * @var _M_x     The state of te generator.  This is a ring buffer.
 568    * @var _M_carry The carry.
 569    * @var _M_p     Current index of x(i - r).
 570    * @endif
 571    */
 572   template<typename _IntType, _IntType __m, int __s, int __r>
 573     class subtract_with_carry
 574     {
 575       __glibcxx_class_requires(_IntType, _IntegerConcept)
 576
 577     public:
 578       /** The type of the generated random value. */
 579       typedef _IntType result_type;
 580
 581       // parameter values
 582       static const _IntType modulus   = __m;
 583       static const int      long_lag  = __r;
 584       static const int      short_lag = __s;
 585
 586     public:
 587       /**
 588        * Constructs a default-initialized % subtract_with_carry random number
 589        * generator.
 590        */
 591       subtract_with_carry()
 592       { this->seed(); }
 593
 594       /**
 595        * Constructs an explicitly seeded % subtract_with_carry random number
 596        * generator.
 597        */
 598       explicit
 599       subtract_with_carry(unsigned long __value)
 600       { this->seed(__value); }
 601
 602       /**
 603        * Constructs a % subtract_with_carry random number generator seeded from
 604        * the PAD iterated by [__first, last).
 605        */
 606       template<class _Gen>
 607         subtract_with_carry(_Gen& __g)
 608         { this->seed(__g); }
 609
 610       /**
 611        * Seeds the initial state @f$ x_0 @f$ of the random number generator.
 612        *
 613        * @note This implementation follows the tr1 specification but will
 614        * obviously not work correctly on all platforms, since it has hardcoded
 615        * values that may overflow ints on some platforms.
 616        *
 617        * N1688[4.19] modifies this as follows.
 618        * If @p __value == 0, sets value to 19780503.  In any case, with a linear
 619        * congruential generator lcg(i) having parameters @f$ m_{lcg} =
 620        * 2147483563, a_{lcg} = 40014, c_{lcg} = 0, and lcg(0) = value @f$, sets
 621        * @f$ x_{-r} \dots x_{-1} @f$ to
 622        * @f$ lcg(1) \bmod m \dots lcg(r) \bmod m @f$ respectively.
 623        * If @f$ x_{-1} = 0 @f$ set carry to 1, otherwise sets carry to 0.
 624        */
 625       void
 626       seed(unsigned long __value = 19780503);
 627
 628       /**
 629        * Seeds the initial state @f$ x_0 @f$ of the % subtract_with_carry
 630        * random number generator.
 631        */
 632       template<class _Gen>
 633         void
 634         seed(_Gen& __g)
 635         { seed(__g, typename is_fundamental<_Gen>::type()); }
 636
 637       /**
 638        * Gets the inclusive minimum value of the range of random integers
 639        * returned by this generator.
 640        */
 641       result_type
 642       min() const
 643       { return 0; }
 644
 645       /**
 646        * Gets the inclusive maximum value of the range of random integers
 647        * returned by this generator.
 648        */
 649       result_type
 650       max() const
 651       { return this->modulus - 1; }
 652
 653       /**
 654        * Gets the next random number in the sequence.
 655        */
 656       result_type
 657       operator()();
 658
 659       /**
 660        * Compares two % subtract_with_carry random number generator objects of
 661        * the same type for equality.
 662        *
 663        * @param __lhs A % subtract_with_carry random number generator object.
 664        * @param __rhs Another % subtract_with_carry random number generator
 665        *              object.
 666        *
 667        * @returns true if the two objects are equal, false otherwise.
 668        */
 669       friend bool
 670       operator==(const subtract_with_carry& __lhs,
 671                  const subtract_with_carry& __rhs)
 672       {
 673         return ((__lhs._M_x[0] == __rhs._M_x[0])
 674                 && (__lhs._M_x[__r - 1] == __rhs._M_x[__r - 1]));
 675       }
 676
 677       /**
 678        * Compares two % subtract_with_carry random number generator objects of
 679        * the same type for inequality.
 680        *
 681        * @param __lhs A % subtract_with_carry random number generator object.
 682        * @param __rhs Another % subtract_with_carry random number generator
 683        *              object.
 684        *
 685        * @returns true if the two objects are not equal, false otherwise.
 686        */
 687       friend bool
 688       operator!=(const subtract_with_carry& __lhs,
 689                  const subtract_with_carry& __rhs)
 690       { return !(__lhs == __rhs); }
 691
 692       /**
 693        * Inserts the current state of a % subtract_with_carry random number
 694        * genator engine @p x into the output stream @p __os.
 695        *
 696        * @param __os An output stream.
 697        * @param __x  A % subtract_with_carry random number generator engine.
 698        *
 699        * @returns The output stream with the state of @p x inserted or in an
 700        * error state.
 701        */
 702       template<typename _CharT, typename _Traits>
 703         friend basic_ostream<_CharT, _Traits>&
 704         operator<<(basic_ostream<_CharT, _Traits>& __os,
 705                    const subtract_with_carry& __x)
 706         {
 707           std::copy(__x._M_x, __x._M_x + __r,
 708                     std::ostream_iterator<_IntType>(__os, " "));
 709           return __os << __x._M_carry;
 710         }
 711
 712       /**
 713        * Extracts the current state of a % subtract_with_carry random number
 714        * gerator engine @p x from the input stream @p __is.
 715        *
 716        * @param __is An input stream.
 717        * @param __x  A % subtract_with_carry random number generator engine.
 718        *
 719        * @returns The input stream with the state of @p x extracted or in an
 720        * error state.
 721        */
 722       template<typename _CharT, typename _Traits>
 723         friend basic_istream<_CharT, _Traits>&
 724         operator>>(basic_istream<_CharT, _Traits>& __is,
 725                    subtract_with_carry& __x)
 726         {
 727           for (int __i = 0; __i < __r; ++__i)
 728             __is >> __x._M_x[__i];
 729           __is >> __x._M_carry;
 730           return __is;
 731         }
 732
 733     private:
 734       template<class _Gen>
 735         void
 736         seed(_Gen& __g, true_type)
 737         { return seed(static_cast<unsigned long>(__g)); }
 738
 739       template<class _Gen>
 740         void
 741         seed(_Gen& __g, false_type);
 742
 743     private:
 744       int         _M_p;
 745       result_type _M_x[long_lag];
 746       result_type _M_carry;
 747     };
 748
 749
 750   /**
 751    * Produces random numbers from some base engine by discarding blocks of
 752    * data.
 753    *
 754    * 0 <= @p __r <= @p __p
 755    */
 756   template<class _UniformRandomNumberGenerator, int __p, int __r>
 757     class discard_block
 758     {
 759       // __glibcxx_class_requires(typename base_type::result_type,
 760       //                          ArithmeticTypeConcept);
 761
 762     public:
 763       /** The type of the underlying generator engine. */
 764       typedef _UniformRandomNumberGenerator   base_type;
 765       /** The type of the generated random value. */
 766       typedef typename base_type::result_type result_type;
 767
 768       // parameter values
 769       static const int block_size = __p;
 770       static const int used_block = __r;
 771
 772       /**
 773        * Constructs a default %discard_block engine.
 774        *
 775        * The underlying engine is default constrcuted as well.
 776        */
 777       discard_block()
 778       : _M_n(0) { }
 779
 780       /**
 781        * Copy constructs a %discard_block engine.
 782        *
 783        * Copies an existing base class random number geenerator.
 784        * @param rng An existing (base class) engine object.
 785        */
 786       explicit discard_block(const base_type& __rng)
 787       : _M_b(__rng) , _M_n(0) { }
 788
 789       /**
 790        * Seed constructs a %discard_block engine.
 791        *
 792        * Constructs the underlying generator engine seeded with @p __s.
 793        * @param __s A seed value for the base class engine.
 794        */
 795       explicit discard_block(unsigned long __s)
 796       : _M_b(__s), _M_n(0) { }
 797
 798       /**
 799        * Generator constructs a %discard_block engine.
 800        *
 801        * @param __g A seed generator function.
 802        */
 803       template<class _Gen>
 804         discard_block(_Gen& __g)
 805         : _M_b(__g), _M_n(0) { }
 806
 807       /**
 808        * Reseeds the %discard_block object with the default seed for the
 809        * underlying base class generator engine.
 810        */
 811       void seed()
 812       {
 813         _M_b.seed();
 814         _M_n = 0;
 815       }
 816
 817       /**
 818        * Reseeds the %discard_block object with the given seed generator
 819        * function.
 820        * @param __g A seed generator function.
 821        */
 822       template<class _Gen>
 823         void seed(_Gen& __g)
 824         {
 825           _M_b.seed(__g);
 826           _M_n = 0;
 827         }
 828
 829       /**
 830        * Gets a const reference to the underlying generator engine object.
 831        */
 832       const base_type&
 833       base() const
 834       { return _M_b; }
 835
 836       /**
 837        * Gets the minimum value in the generated random number range.
 838        */
 839       result_type
 840       min() const
 841       { return _M_b.min(); }
 842
 843       /**
 844        * Gets the maximum value in the generated random number range.
 845        */
 846       result_type
 847       max() const
 848       { return _M_b.max(); }
 849
 850       /**
 851        * Gets the next value in the generated random number sequence.
 852        */
 853       result_type
 854       operator()();
 855
 856       /**
 857        * Compares two %discard_block random number generator objects of
 858        * the same type for equality.
 859        *
 860        * @param __lhs A %discard_block random number generator object.
 861        * @param __rhs Another %discard_block random number generator
 862        *              object.
 863        *
 864        * @returns true if the two objects are equal, false otherwise.
 865        */
 866       friend bool
 867       operator==(const discard_block& __lhs, const discard_block& __rhs)
 868       {
 869         return ((__lhs._M_b == __rhs._M_b)
 870                 && (__lhs._M_n == __rhs._M_n));
 871       }
 872
 873       /**
 874        * Compares two %discard_block random number generator objects of
 875        * the same type for inequality.
 876        *
 877        * @param __lhs A %discard_block random number generator object.
 878        * @param __rhs Another %discard_block random number generator
 879        *              object.
 880        *
 881        * @returns true if the two objects are not equal, false otherwise.
 882        */
 883       friend bool
 884       operator!=(const discard_block& __lhs, const discard_block& __rhs)
 885       { return !(__lhs == __rhs); }
 886
 887       /**
 888        * Inserts the current state of a %discard_block random number
 889        * genator engine @p x into the output stream @p __os.
 890        *
 891        * @param __os An output stream.
 892        * @param __x  A %discard_block random number generator engine.
 893        *
 894        * @returns The output stream with the state of @p x inserted or in an
 895        * error state.
 896        */
 897       template<typename _CharT, typename _Traits>
 898         friend basic_ostream<_CharT, _Traits>&
 899         operator<<(basic_ostream<_CharT, _Traits>& __os,
 900                    const discard_block& __x)
 901         { return __os << __x._M_b << " " << __x._M_n; }
 902
 903       /**
 904        * Extracts the current state of a % subtract_with_carry random number
 905        * gerator engine @p x from the input stream @p __is.
 906        *
 907        * @param __is An input stream.
 908        * @param __x  A %discard_block random number generator engine.
 909        *
 910        * @returns The input stream with the state of @p x extracted or in an
 911        * error state.
 912        */
 913       template<typename _CharT, typename _Traits>
 914         friend basic_istream<_CharT, _Traits>&
 915         operator>>(basic_istream<_CharT, _Traits>& __is,
 916                    discard_block& __x)
 917         { return __is >> __x._M_b >> __x._M_n; }
 918
 919     private:
 920       base_type _M_b;
 921       int       _M_n;
 922     };
 923
 924
 925   /**
 926    * James's luxury-level-3 integer adaptation of Luescher's generator.
 927    */
 928   typedef discard_block<
 929     subtract_with_carry<int, (1<<24), 10, 24>,
 930       223,
 931       24
 932       > ranlux3;
 933
 934   /**
 935    * James's luxury-level-4 integer adaptation of Luescher's generator.
 936    */
 937   typedef discard_block<
 938     subtract_with_carry<int, (1<<24), 10, 24>,
 939       389,
 940       24
 941       > ranlux4;
 942
 943
 944   /**
 945    * A random number generator adaptor class that combines two random number
 946    * generator engines into a single output sequence.
 947    */
 948   template<class _UniformRandomNumberGenerator1, int __s1,
 949            class _UniformRandomNumberGenerator2, int __s2>
 950     class xor_combine
 951     {
 952       // __glibcxx_class_requires(typename _UniformRandomNumberGenerator1::
 953       //                          result_type, ArithmeticTypeConcept);
 954       // __glibcxx_class_requires(typename _UniformRandomNumberGenerator2::
 955       //                          result_type, ArithmeticTypeConcept);
 956
 957     public:
 958       /** The type of the the first underlying generator engine. */
 959       typedef _UniformRandomNumberGenerator1 base1_type;
 960       /** The type of the the second underlying generator engine. */
 961       typedef _UniformRandomNumberGenerator2 base2_type;
 962       /** The type of the generated random value. */
 963       typedef typename _Private::_Select<
 964         (sizeof(base1_type) > sizeof(base2_type)),
 965         base1_type,
 966         base2_type
 967         >::_Type result_type;
 968
 969       // parameter values
 970       static const int shift1 = __s1;
 971       static const int shift2 = __s2;
 972
 973       // constructors and member function
 974       xor_combine() { }
 975
 976       xor_combine(const base1_type& __rng1, const base2_type& __rng2)
 977       : _M_b1(__rng1), _M_b2(__rng2) { }
 978
 979       xor_combine(unsigned long __s)
 980       : _M_b1(__s), _M_b2(__s + 1) { }
 981
 982       template<class _Gen>
 983         xor_combine(_Gen& __g)
 984         : _M_b1(__g), _M_b2(__g) { }
 985
 986       void
 987       seed()
 988       {
 989         _M_b1.seed();
 990         _M_b2.seed();
 991       }
 992
 993       template<class _Gen>
 994         void
 995         seed(_Gen& __g)
 996         {
 997           _M_b1.seed(__g);
 998           _M_b2.seed(__g);
 999         }
1000
1001       const base1_type&
1002       base1() const
1003       { return _M_b1; }
1004
1005       const base2_type&
1006       base2() const
1007       { return _M_b2; }
1008
1009       result_type
1010       min() const
1011       { return _M_b1.min() ^ _M_b2.min(); }
1012
1013       result_type
1014       max() const
1015       { return _M_b1.max() | _M_b2.max(); }
1016
1017       /**
1018        * Gets the next random number in the sequence.
1019        */
1020       result_type
1021       operator()()
1022       { return ((_M_b1() << shift1) ^ (_M_b2() << shift2)); }
1023
1024       /**
1025        * Compares two %xor_combine random number generator objects of
1026        * the same type for equality.
1027        *
1028        * @param __lhs A %xor_combine random number generator object.
1029        * @param __rhs Another %xor_combine random number generator
1030        *              object.
1031        *
1032        * @returns true if the two objects are equal, false otherwise.
1033        */
1034       friend bool
1035       operator==(const xor_combine& __lhs, const xor_combine& __rhs)
1036       {
1037         return (__lhs.base1() == __rhs.base1())
1038           && (__lhs.base2() == __rhs.base2());
1039       }
1040
1041       /**
1042        * Compares two %xor_combine random number generator objects of
1043        * the same type for inequality.
1044        *
1045        * @param __lhs A %xor_combine random number generator object.
1046        * @param __rhs Another %xor_combine random number generator
1047        *              object.
1048        *
1049        * @returns true if the two objects are not equal, false otherwise.
1050        */
1051       friend bool
1052       operator!=(const xor_combine& __lhs, const xor_combine& __rhs)
1053       { return !(__lhs == __rhs); }
1054
1055       /**
1056        * Inserts the current state of a %xor_combine random number
1057        * genator engine @p x into the output stream @p __os.
1058        *
1059        * @param __os An output stream.
1060        * @param __x  A %xor_combine random number generator engine.
1061        *
1062        * @returns The output stream with the state of @p x inserted or in an
1063        * error state.
1064        */
1065       template<typename _CharT, typename _Traits>
1066         friend basic_ostream<_CharT, _Traits>&
1067         operator<<(basic_ostream<_CharT, _Traits>& __os,
1068                    const xor_combine& __x)
1069         { return __os << __x.base1() << " " << __x.base1(); }
1070
1071       /**
1072        * Extracts the current state of a %xor_combine random number
1073        * gerator engine @p x from the input stream @p __is.
1074        *
1075        * @param __is An input stream.
1076        * @param __x  A %xor_combine random number generator engine.
1077        *
1078        * @returns The input stream with the state of @p x extracted or in an
1079        * error state.
1080        */
1081       template<typename _CharT, typename _Traits>
1082         friend basic_istream<_CharT, _Traits>&
1083         operator>>(basic_istream<_CharT, _Traits>& __is,
1084                    xor_combine& __x)
1085         { return __is >> __x._M_b1 >> __x._M_b2; }
1086
1087     private:
1088       base1_type _M_b1;
1089       base2_type _M_b2;
1090     };
1091
1092
1093   /**
1094    * A standard interface to a platform-specific non-deterministic random number
1095    * generator (if any are available).
1096    *
1097    * @todo The underlying interface is system-specific and needs to be factored
1098    * into the generated configury mechs.  For example, the use of "/dev/random"
1099    * under a Linux OS would be appropriate.
1100    */
1101   class random_device
1102   {
1103   public:
1104     // types
1105     typedef unsigned int result_type;
1106
1107     // constructors, destructors and member functions
1108     explicit random_device(const std::string& __token = "unimplemented");
1109     result_type min() const;
1110     result_type max() const;
1111     double entropy() const;
1112     result_type operator()();
1113
1114   private:
1115     random_device(const random_device&);
1116     void operator=(const random_device&);
1117   };
1118
1119   /* @} */ // group tr1_random_generators
1120
1121   /**
1122    * @addtogroup tr1_random_distributions Random Number Distributions
1123    * @ingroup tr1_random
1124    * @{
1125    */
1126
1127   /**
1128    * @addtogroup tr1_random_distributions_discrete Discrete Distributions
1129    * @ingroup tr1_random_distributions
1130    * @{
1131    */
1132
1133   /**
1134    * @brief Uniform discrete distribution for random numbers.
1135    * A discrete random distribution on the range @f$[min, max]@f$ with equal
1136    * probability throughout the range.
1137    */
1138   template<typename _IntType = int>
1139     class uniform_int
1140     {
1141       __glibcxx_class_requires(_IntType, _IntegerConcept)
1142
1143     public:
1144       /** The type of the parameters of the distribution. */
1145       typedef _IntType input_type;
1146       /** The type of the range of the distribution. */
1147       typedef _IntType result_type;
1148
1149     public:
1150       /**
1151        * Constructs a uniform distribution object.
1152        */
1153       explicit
1154       uniform_int(_IntType __min = 0, _IntType __max = 9)
1155       : _M_min(__min), _M_max(__max)
1156       {
1157         _GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
1158       }
1159
1160       /**
1161        * Gets the inclusive lower bound of the distribution range.
1162        */
1163       result_type
1164       min() const
1165       { return _M_min; }
1166
1167       /**
1168        * Gets the inclusive upper bound of the distribution range.
1169        */
1170       result_type
1171       max() const
1172       { return _M_max; }
1173
1174       /**
1175        * Resets the distribution state.
1176        *
1177        * Does nothing for the uniform integer distribution.
1178        */
1179       void
1180       reset() { }
1181
1182       /**
1183        * Gets a uniformly distributed random number in the range
1184        * @f$(min, max)@f$.
1185        */
1186       template<typename _UniformRandomNumberGenerator>
1187         result_type
1188         operator()(_UniformRandomNumberGenerator& __urng)
1189         { return (__urng() % (_M_max - _M_min + 1)) + _M_min; }
1190
1191       /**
1192        * Gets a uniform random number in the range @f$[0, n)@f$.
1193        *
1194        * This function is aimed at use with std::random_shuffle.
1195        */
1196       template<typename _UniformRandomNumberGenerator>
1197         result_type
1198         operator()(_UniformRandomNumberGenerator& __urng, result_type __n)
1199         { return __urng() % __n; }
1200
1201       /**
1202        * Inserts a %uniform_int random number distribution @p x into the
1203        * output stream @p os.
1204        *
1205        * @param __os An output stream.
1206        * @param __x  A %uniform_int random number distribution.
1207        *
1208        * @returns The output stream with the state of @p x inserted or in an
1209        * error state.
1210        */
1211       template<typename _CharT, typename _Traits>
1212         friend basic_ostream<_CharT, _Traits>&
1213         operator<<(basic_ostream<_CharT, _Traits>& __os,
1214                    const uniform_int& __x)
1215         { return __os << __x._M_min << " " << __x._M_max; }
1216
1217       /**
1218        * Extracts a %unform_int random number distribution
1219        * @p u from the input stream @p __is.
1220        *
1221        * @param __is An input stream.
1222        * @param __u  A %uniform_int random number generator engine.
1223        *
1224        * @returns The input stream with @p u extracted or in an error state.
1225        */
1226       template<typename _CharT, typename _Traits>
1227         friend basic_istream<_CharT, _Traits>&
1228         operator>>(basic_istream<_CharT, _Traits>& __is, uniform_int& __u)
1229         { return __is >> __u._M_min >> __u._M_max; }
1230
1231     private:
1232       _IntType _M_min;
1233       _IntType _M_max;
1234     };
1235
1236
1237   /**
1238    * @brief A Bernoulli random number distribution.
1239    *
1240    * Generates a sequence of true and false values with likelihood @f$ p @f$
1241    * that true will come up and @f$ (1 - p) @f$ that false will appear.
1242    */
1243   class bernoulli_distribution
1244   {
1245   public:
1246     typedef int  input_type;
1247     typedef bool result_type;
1248
1249   public:
1250     /**
1251      * Constructs a Bernoulli distribution with likelihood @p p.
1252      *
1253      * @param __p  [IN]  The likelihood of a true result being returned.  Must
1254      * be in the interval @f$ [0, 1] @f$.
1255      */
1256     explicit
1257     bernoulli_distribution(double __p = 0.5)
1258     : _M_p(__p)
1259     {
1260       _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
1261     }
1262
1263     /**
1264      * Gets the @p p parameter of the distribution.
1265      */
1266     double
1267     p() const
1268     { return _M_p; }
1269
1270     /**
1271      * Gets the inclusive lower bound of the distribution range.
1272      */
1273     result_type
1274     min() const
1275     { return false; }
1276
1277     /**
1278      * Gets the inclusive upper bound of the distribution range.
1279      */
1280     result_type
1281     max() const
1282     { return true; }
1283
1284     /**
1285      * Resets the distribution state.
1286      *
1287      * Does nothing for a bernoulli distribution.
1288      */
1289     void
1290     reset() { }
1291
1292     /**
1293      * Gets the next value in the Bernoullian sequence.
1294      */
1295     template<class UniformRandomNumberGenerator>
1296       result_type
1297       operator()(UniformRandomNumberGenerator& __urng)
1298       {
1299         if (__urng() < _M_p)
1300           return true;
1301         return false;
1302       }
1303
1304     /**
1305      * Inserts a %bernoulli_distribution random number distribution
1306      * @p x into the output stream @p __os.
1307      *
1308      * @param __os An output stream.
1309      * @param __x  A %bernoulli_distribution random number distribution.
1310      *
1311      * @returns The output stream with the state of @p x inserted or in an
1312      * error state.
1313      */
1314     template<typename _CharT, typename _Traits>
1315       friend basic_ostream<_CharT, _Traits>&
1316       operator<<(basic_ostream<_CharT, _Traits>& __os,
1317                  const bernoulli_distribution& __x)
1318       { return __os << __x.p(); }
1319
1320     /**
1321      * Extracts a %bernoulli_distribution random number distribution
1322      * @p u from the input stream @p __is.
1323      *
1324      * @param __is An input stream.
1325      * @param __u  A %bernoulli_distribution random number generator engine.
1326      *
1327      * @returns The input stream with @p u extracted or in an error state.
1328      */
1329     template<typename _CharT, typename _Traits>
1330       friend basic_istream<_CharT, _Traits>&
1331       operator>>(basic_istream<_CharT, _Traits>& __is,
1332                  bernoulli_distribution& __u)
1333       { return __is >> __u._M_p; }
1334
1335   protected:
1336     double _M_p;
1337   };
1338
1339
1340   /**
1341    * @brief A discrete geometric random number distribution.
1342    *
1343    * The formula for the geometric probability mass function is
1344    * @f$ p(i) = (1 - p)p^{i-1} @f$ where @f$ p @f$ is the parameter of the
1345    * distribution.
1346    */
1347   template<typename _IntType = int, typename _RealType = double>
1348     class geometric_distribution
1349     {
1350     public:
1351       // types
1352       typedef _RealType input_type;
1353       typedef _IntType  result_type;
1354
1355       // constructors and member function
1356
1357       explicit
1358       geometric_distribution(const _RealType& __p = _RealType(0.5))
1359       : _M_p(__p), _M_log_p(std::log(_M_p))
1360       {
1361         _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
1362       }
1363
1364       /**
1365        * Gets the distribution parameter @p p.
1366        */
1367       _RealType
1368       p() const
1369       { return _M_p; }
1370
1371       /**
1372        * Gets the inclusive lower bound of the distribution range.
1373        */
1374       result_type
1375       min() const;
1376
1377       /**
1378        * Gets the inclusive upper bound of the distribution range.
1379        */
1380       result_type
1381       max() const;
1382
1383       void
1384       reset() { }
1385
1386       template<class _UniformRandomNumberGenerator>
1387         result_type
1388         operator()(_UniformRandomNumberGenerator& __urng)
1389         {
1390           return result_type(std::floor(std::log(_RealType(1.0) - __urng())
1391                                         / _M_log_p)) + result_type(1);
1392         }
1393
1394       /**
1395        * Inserts a %geometric_distribution random number distribution
1396        * @p x into the output stream @p __os.
1397        *
1398        * @param __os An output stream.
1399        * @param __x  A %geometric_distribution random number distribution.
1400        *
1401        * @returns The output stream with the state of @p x inserted or in an
1402        * error state.
1403        */
1404       template<typename _CharT, typename _Traits>
1405         friend basic_ostream<_CharT, _Traits>&
1406         operator<<(basic_ostream<_CharT, _Traits>& __os,
1407                    const geometric_distribution& __x)
1408         { return __os << __x.p(); }
1409
1410       /**
1411        * Extracts a %geometric_distribution random number distribution
1412        * @p u from the input stream @p __is.
1413        *
1414        * @param __is An input stream.
1415        * @param __u  A %geometric_distribution random number generator engine.
1416        *
1417        * @returns The input stream with @p u extracted or in an error state.
1418        */
1419       template<typename _CharT, typename _Traits>
1420         friend basic_istream<_CharT, _Traits>&
1421         operator>>(basic_istream<_CharT, _Traits>& __is,
1422                    geometric_distribution& __u)
1423         {
1424           __is >> __u._M_p;
1425           __u._M_log_p = std::log(__u._M_p);
1426           return __is;
1427         }
1428
1429     protected:
1430       _RealType _M_p;
1431       _RealType _M_log_p;
1432     };
1433
1434   /* @} */ // group tr1_random_distributions_discrete
1435
1436   /**
1437    * @addtogroup tr1_random_distributions_continuous Continuous Distributions
1438    * @ingroup tr1_random_distributions
1439    * @{
1440    */
1441
1442   /**
1443    * @brief Uniform continuous distribution for random numbers.
1444    *
1445    * A continuous random distribution on the range [min, max) with equal
1446    * probability throughout the range.  The URNG should be real-valued and
1447    * deliver number in the range [0, 1).
1448    */
1449   template<typename _RealType = double>
1450     class uniform_real
1451     {
1452     public:
1453       // types
1454       typedef _RealType input_type;
1455       typedef _RealType result_type;
1456
1457     public:
1458       /**
1459        * Constructs a uniform_real object.
1460        *
1461        * @param __min [IN]  The lower bound of the distribution.
1462        * @param __max [IN]  The upper bound of the distribution.
1463        */
1464       explicit
1465       uniform_real(_RealType __min = _RealType(0),
1466                    _RealType __max = _RealType(1));
1467
1468       result_type
1469       min() const;
1470
1471       result_type
1472       max() const;
1473
1474       void reset();
1475
1476       template<class _UniformRandomNumberGenerator>
1477         result_type
1478         operator()(_UniformRandomNumberGenerator& __urng)
1479         { return (__urng() * (max() - min())) + min(); }
1480
1481       /**
1482        * Inserts a %uniform_real random number distribution @p x into the
1483        * output stream @p __os.
1484        *
1485        * @param __os An output stream.
1486        * @param __x  A %uniform_real random number distribution.
1487        *
1488        * @returns The output stream with the state of @p x inserted or in an
1489        * error state.
1490        */
1491       template<typename _CharT, typename _Traits>
1492         friend basic_ostream<_CharT, _Traits>&
1493         operator<<(basic_ostream<_CharT, _Traits>& __os,
1494                    const uniform_real& __x)
1495         { return __os << __x.min() << " " << __x.max(); }
1496
1497       /**
1498        * Extracts a %unform_real random number distribution
1499        * @p u from the input stream @p __is.
1500        *
1501        * @param __is An input stream.
1502        * @param __u  A %uniform_real random number generator engine.
1503        *
1504        * @returns The input stream with @p u extracted or in an error state.
1505        */
1506       template<typename _CharT, typename _Traits>
1507         friend basic_istream<_CharT, _Traits>&
1508         operator>>(basic_istream<_CharT, _Traits>& __is,
1509                  uniform_real& __u)
1510         { return __is >> __u._M_min >> __u._M_max; }
1511
1512     protected:
1513       _RealType _M_min;
1514       _RealType _M_max;
1515     };
1516
1517
1518   /**
1519    * @brief An exponential continuous distribution for random numbers.
1520    *
1521    * The formula for the exponential probability mass function is
1522    * @f$ p(x) = \lambda e^{-\lambda x} @f$.
1523    *
1524    * <table border=1 cellpadding=10 cellspacing=0>
1525    * <caption align=top>Distribution Statistics</caption>
1526    * <tr><td>Mean</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
1527    * <tr><td>Median</td><td>@f$ \frac{\ln 2}{\lambda} @f$</td></tr>
1528    * <tr><td>Mode</td><td>@f$ zero @f$</td></tr>
1529    * <tr><td>Range</td><td>@f$[0, \infty]@f$</td></tr>
1530    * <tr><td>Standard Deviation</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
1531    * </table>
1532    */
1533   template<typename _RealType = double>
1534     class exponential_distribution
1535     {
1536     public:
1537       // types
1538       typedef _RealType input_type;
1539       typedef _RealType result_type;
1540
1541     public:
1542       /**
1543        * Constructs an exponential distribution with inverse scale parameter
1544        * @f$ \lambda @f$.
1545        */
1546       explicit
1547       exponential_distribution(const result_type& __lambda = result_type(1))
1548       : _M_lambda(__lambda) { }
1549
1550       /**
1551        * Gets the inverse scale parameter of the distribution.
1552        */
1553       _RealType
1554       lambda() const
1555       { return _M_lambda; }
1556
1557       /**
1558        * Resets the distribution.
1559        *
1560        * Has no effect on exponential distributions.
1561        */
1562       void
1563       reset() { }
1564
1565       template<class _UniformRandomNumberGenerator>
1566         result_type
1567         operator()(_UniformRandomNumberGenerator& __urng)
1568         { return -std::log(__urng()) / _M_lambda; }
1569
1570       /**
1571        * Inserts a %exponential_distribution random number distribution
1572        * @p x into the output stream @p __os.
1573        *
1574        * @param __os An output stream.
1575        * @param __x  A %exponential_distribution random number distribution.
1576        *
1577        * @returns The output stream with the state of @p x inserted or in an
1578        * error state.
1579        */
1580       template<typename _CharT, typename _Traits>
1581         friend basic_ostream<_CharT, _Traits>&
1582         operator<<(basic_ostream<_CharT, _Traits>& __os,
1583                    const exponential_distribution& __x)
1584         { return __os << __x.lambda(); }
1585
1586       /**
1587        * Extracts a %exponential_distribution random number distribution
1588        * @p u from the input stream @p __is.
1589        *
1590        * @param __is An input stream.
1591        * @param __u  A %exponential_distribution random number generator engine.
1592        *
1593        * @returns The input stream with @p u extracted or in an error state.
1594        */
1595       template<typename _CharT, typename _Traits>
1596         friend basic_istream<_CharT, _Traits>&
1597         operator>>(basic_istream<_CharT, _Traits>& __is,
1598                    exponential_distribution& __u)
1599         { return __is >> __u._M_lambda; }
1600
1601     private:
1602       result_type _M_lambda;
1603     };
1604
1605   /* @} */ // group tr1_random_distributions_continuous
1606   /* @} */ // group tr1_random_distributions
1607   /* @} */ // group tr1_random
1608
1609 _GLIBCXX_END_NAMESPACE
1610 }
1611
1612 #include <tr1/random.tcc>
1613
1614 #endif // _STD_TR1_RANDOM