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 implemeted 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 genereator 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 d.
 158        *
 159        * @throws Any exceptions which may thrown by the copy constructors of the
 160        * @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 large
 273    * enough to store values up to (m-1). If the template parameter @p m is 0,
 274    * the modulus @p m used is std::numeric_limits<UIntType>::max() plus 1.
 275    * Otherwise, the template parameters @p a and @p c must be less than @p m.
 276    *
 277    * The size of the state is @f$ 1 @f$.
 278    */
 279   template<class UIntType, UIntType a, UIntType c, UIntType m>
 280     class linear_congruential
 281     {
 282       __glibcxx_class_requires(UIntType, _UnsignedIntegerConcept)
 283       //  __glibcpp_class_requires(a < m && c < m)
 284
 285     public:
 286       /** The type of the generated random value. */
 287       typedef UIntType result_type;
 288
 289       /** The multiplier. */
 290       static const UIntType multiplier = a;
 291       /** An increment. */
 292       static const UIntType increment = c;
 293       /** The modulus. */
 294       static const UIntType modulus = m;
 295
 296       /**
 297        * Constructs a %linear_congruential random number generator engine with
 298        * seed @p s.  The default seed value is 1.
 299        *
 300        * @param s The initial seed value.
 301        */
 302       explicit linear_congruential(unsigned long s = 1);
 303
 304       /**
 305        * Constructs a %linear_congruential random number generator engine
 306        * seeded from the generator function @g.
 307        *
 308        * @param g The seed generator function.
 309        */
 310       template<class Gen>
 311         linear_congruential(Gen& g);
 312
 313       /**
 314        * Resets the %linear_congruential random number generator engine sequence
 315        * to @p.
 316        *
 317        * @param s The new seed.
 318        */
 319       void
 320       seed(unsigned long s = 1);
 321
 322       /**
 323        * Resets the %linear_congruential random number generator engine sequence
 324        * using a vlaue from the generator function @g.
 325        *
 326        * @param g the seed generator function.
 327        */
 328       template<class Gen>
 329         void
 330         seed(Gen& g)
 331         { seed(g, typename is_fundamental<Gen>::type()); }
 332
 333       /**
 334        * Gets the smallest possible value in the output range.
 335        */
 336       result_type
 337       min() const;
 338
 339       /**
 340        * Gets the largest possible value in the output range.
 341        */
 342       result_type
 343       max() const;
 344
 345       /**
 346        * Gets the next random number in the sequence.
 347        */
 348       result_type
 349       operator()();
 350
 351       /**
 352        * Compares two linear congruential random number generator objects of the
 353        * same type for equality.
 354        *
 355        * @param lhs A linear congruential random number generator object.
 356        * @param rhs Another linear congruential random number generator object.
 357        *
 358        * @returns true if the two objects are equal, false otherwise.
 359        */
 360       friend bool
 361       operator==(const linear_congruential& lhs, const linear_congruential& rhs)
 362       { return lhs.m_x == rhs.m_x; }
 363
 364       /**
 365        * Compares two linear congruential random number generator objects of the
 366        * same type for inequality.
 367        *
 368        * @param lhs A linear congruential random number generator object.
 369        * @param rhs Another linear congruential random number generator object.
 370        *
 371        * @returns true if the two objects are not equal, false otherwise.
 372        */
 373       friend bool
 374       operator!=(const linear_congruential& lhs, const linear_congruential& rhs)
 375       { return !(lhs == rhs); }
 376
 377       /**
 378        * Writes the textual representation of the state x(i) of x to @p os.
 379        *
 380        * @param os  The output stream.
 381        * @param lcr A linear_congruential random number generator.
 382        * @returns os.
 383        */
 384       template<typename CharT, typename Traits>
 385         friend std::basic_ostream<CharT, Traits>&
 386         operator<<(std::basic_ostream<CharT, Traits>& os,
 387                    const linear_congruential& lcr)
 388         { return os << lcr.m_x; }
 389
 390       /**
 391        * Sets the state of the engine by reading its textual
 392        * representation from @p is.
 393        *
 394        * The textual representation must have been previously written using an
 395        * output stream whose imbued locale and whose type's template
 396        * specialization arguments CharT and Traits were the same as those of
 397        * @p is.
 398        *
 399        * @param is  The input stream.
 400        * @param lcr A linear_congruential random number generator.
 401        * @returns os.
 402        */
 403       template<typename CharT, typename Traits>
 404         friend std::basic_istream<CharT, Traits>&
 405         operator>>(std::basic_istream<CharT, Traits>& is,
 406                    linear_congruential& lcr)
 407         { return is >> lcr.m_x; }
 408
 409     private:
 410       template<class Gen>
 411         void
 412         seed(Gen& g, true_type)
 413         { return seed(static_cast<unsigned long>(g)); }
 414
 415       template<class Gen>
 416         void
 417         seed(Gen& g, false_type);
 418
 419     private:
 420       UIntType m_x;
 421     };
 422
 423   /**
 424    * The classic Minimum Standard rand0 of Lewis, Goodman, and Miller.
 425    */
 426   typedef linear_congruential<unsigned int, 16807, 0, 2147483647> minstd_rand0;
 427
 428   /**
 429    * An alternative LCR (Lehmer Generator function) .
 430    */
 431   typedef linear_congruential<unsigned int, 48271, 0, 2147483647> minstd_rand;
 432
 433
 434   /**
 435    * A generalized feedback shift register discrete random number generator.
 436    *
 437    * This algorithm avoind multiplication and division and is designed to be
 438    * friendly to a pipelined architecture.  If the parameters are chosen
 439    * correctly, this generator will produce numbers with a very long period and
 440    * fairly good apparent entropy, although still not cryptographically strong.
 441    *
 442    * The best way to use this generator is with the predefined mt19937 class.
 443    *
 444    * This algorithm was originally invented by Makoto Matsumoto and
 445    * Takuji Nishimura.
 446    *
 447    * @var word_size   The number of bits in each element of the state vector.
 448    * @var state_size  The degree of recursion.
 449    * @var shift_size  The period parameter.
 450    * @var mask_bits   The separation point bit index.
 451    * @var parameter_a The last row of the twist matrix.
 452    * @var output_u    The first right-shift tempering matrix parameter.
 453    * @var output_s    The first left-shift tempering matrix parameter.
 454    * @var output_b    The first left-shift tempering matrix mask.
 455    * @var output_t    The second left-shift tempering matrix parameter.
 456    * @var output_c    The second left-shift tempering matrix mask.
 457    * @var output_l    The second right-shift tempering matrix parameter.
 458    */
 459   template<class UIntType, int w, int n, int m, int r,
 460            UIntType a, int u, int s, UIntType b, int t, UIntType c, int l>
 461     class mersenne_twister
 462     {
 463       __glibcxx_class_requires(UIntType, _UnsignedIntegerConcept)
 464
 465     public:
 466       // types
 467       typedef UIntType result_type ;
 468
 469       // parameter values
 470       static const int      word_size   = w;
 471       static const int      state_size  = n;
 472       static const int      shift_size  = m;
 473       static const int      mask_bits   = r;
 474       static const UIntType parameter_a = a;
 475       static const int      output_u    = u;
 476       static const int      output_s    = s;
 477       static const UIntType output_b    = b;
 478       static const int      output_t    = t;
 479       static const UIntType output_c    = c;
 480       static const int      output_l    = l;
 481
 482       // constructors and member function
 483       mersenne_twister()
 484       { seed(); }
 485
 486       explicit
 487       mersenne_twister(unsigned long value)
 488       { seed(value); }
 489
 490       template<class Gen>
 491         mersenne_twister(Gen& g)
 492         { seed(g); }
 493
 494       void
 495       seed()
 496       { seed(0UL); }
 497
 498       void
 499       seed(unsigned long value);
 500
 501       template<class Gen>
 502         void
 503         seed(Gen& g)
 504         { seed(g, typename is_fundamental<Gen>::type()); }
 505
 506       result_type
 507       min() const
 508       { return 0; };
 509
 510       result_type
 511       max() const;
 512
 513       result_type
 514       operator()();
 515
 516     private:
 517       template<class Gen>
 518         void
 519         seed(Gen& g, true_type)
 520         { return seed(static_cast<unsigned long>(g)); }
 521
 522       template<class Gen>
 523         void
 524         seed(Gen& g, false_type);
 525
 526     private:
 527       UIntType _M_x[state_size];
 528       int      _M_p;
 529     };
 530
 531   /**
 532    * The classic Mersenne Twister.
 533    *
 534    * Reference:
 535    * M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
 536    * Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions
 537    * on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
 538    */
 539   typedef mersenne_twister<
 540     unsigned long, 32, 624, 397, 31,
 541     0x9908b0dful, 11, 7,
 542     0x9d2c5680ul, 15,
 543     0xefc60000ul, 18
 544     > mt19937;
 545
 546
 547   /**
 548    * @brief The Marsaglia-Zaman generator.
 549    *
 550    * This is a model of a Generalized Fibonacci discrete random number
 551    * generator, sometimes referred to as the SWC generator.
 552    *
 553    * A discrete random number generator that produces pseudorandom numbers using
 554    * @f$x_{i}\leftarrow(x_{i - s} - x_{i - r} - carry_{i-1}) \bmod m @f$.
 555    *
 556    * The size of the state is @f$ r @f$
 557    * and the maximum period of the generator is @f$ m^r - m^s -1 @f$.
 558    *
 559    * N1688[4.13] says "the template parameter _IntType shall denote an integral
 560    * type large enough to store values up to m."
 561    *
 562    * @if maint
 563    * @var _M_x     The state of te generator.  This is a ring buffer.
 564    * @var _M_carry The carry.
 565    * @var _M_p     Current index of x(i - r).
 566    * @endif
 567    */
 568   template<typename _IntType, _IntType m, int s, int r>
 569     class subtract_with_carry
 570     {
 571       __glibcxx_class_requires(_IntType, _IntegerConcept)
 572
 573     public:
 574       /** The type of the generated random value. */
 575       typedef _IntType result_type;
 576
 577       // parameter values
 578       static const _IntType modulus   = m;
 579       static const int      long_lag  = r;
 580       static const int      short_lag = s;
 581
 582     public:
 583       /**
 584        * Constructs a default-initialized % subtract_with_carry random number
 585        * generator.
 586        */
 587       subtract_with_carry()
 588       { this->seed(); }
 589
 590       /**
 591        * Constructs an explicitly seeded % subtract_with_carry random number
 592        * generator.
 593        */
 594       explicit
 595       subtract_with_carry(_IntType __value)
 596       { this->seed(__value); }
 597
 598       /**
 599        * Constructs a % subtract_with_carry random number generator seeded from
 600        * the PAD iterated by [__first, last).
 601        */
 602       template<class Gen>
 603         subtract_with_carry(Gen& g)
 604         { this->seed(g); }
 605
 606       /**
 607        * Seeds the initial state @f$ x_0 @f$ of the random number generator.
 608        *
 609        * @note This implementation follows the tr1 specification but will
 610        * obviously not work correctly on all platforms, since it has hardcoded
 611        * values that may overflow ints on some platforms.
 612        *
 613        * N1688[4.19] modifies this as follows.
 614        * If @p __value == 0, sets value to 19780503.  In any case, with a linear
 615        * congruential generator lcg(i) having parameters @f$ m_{lcg} =
 616        * 2147483563, a_{lcg} = 40014, c_{lcg} = 0, and lcg(0) = value @f$, sets
 617        * @f$ x_{-r} \dots x_{-1} @f$ to
 618        * @f$ lcg(1) \bmod m \dots lcg(r) \bmod m @f$ respectively.
 619        * If @f$ x_{-1} = 0 @f$ set carry to 1, otherwise sets carry to 0.
 620        */
 621       void
 622       seed(_IntType __value = 19780503);
 623
 624       /**
 625        * Seeds the initial state @f$ x_0 @f$ of the % subtract_with_carry
 626        * random number generator.
 627        */
 628       template<class Gen>
 629         void
 630         seed(Gen& g)
 631         { seed(g, typename is_fundamental<Gen>::type()); }
 632
 633       /**
 634        * Gets the inclusive minimum value of the range of random integers
 635        * returned by this generator.
 636        */
 637       result_type
 638       min() const
 639       { return 0; }
 640
 641       /**
 642        * Gets the inclusive maximum value of the range of random integers
 643        * returned by this generator.
 644        */
 645       result_type
 646       max() const
 647       { return this->modulus - 1; }
 648
 649       /**
 650        * Gets the next random number in the sequence.
 651        */
 652       result_type
 653       operator()();
 654
 655       /**
 656        * Compares two % subtract_with_carry random number generator objects of
 657        * the same type for equality.
 658        *
 659        * @param __lhs A % subtract_with_carry random number generator object.
 660        * @param __rhs Another % subtract_with_carry random number generator
 661        *              object.
 662        *
 663        * @returns true if the two objects are equal, false otherwise.
 664        */
 665       friend bool
 666       operator==(const subtract_with_carry& __lhs,
 667                  const subtract_with_carry& __rhs)
 668       {
 669         return ((__lhs._M_x[0] == __rhs._M_x[0])
 670                 && (__lhs._M_x[r-1] == __rhs._M_x[r-1]));
 671       }
 672
 673       /**
 674        * Compares two % subtract_with_carry random number generator objects of
 675        * the same type for inequality.
 676        *
 677        * @param __lhs A % subtract_with_carry random number generator object.
 678        * @param __rhs Another % subtract_with_carry random number generator
 679        *              object.
 680        *
 681        * @returns true if the two objects are not equal, false otherwise.
 682        */
 683       friend bool
 684       operator!=(const subtract_with_carry& __lhs,
 685                  const subtract_with_carry& __rhs)
 686       { return !(__lhs == __rhs); }
 687
 688       /**
 689        * Inserts the current state of a % subtract_with_carry random number
 690        * genator engine @p x into the output stream @p os.
 691        *
 692        * @param __os An output stream.
 693        * @param __x  A % subtract_with_carry random number generator engine.
 694        *
 695        * @returns The output stream with the state of @p x inserted or in an
 696        * error state.
 697        */
 698       template<typename _CharT, typename _Traits>
 699         friend basic_ostream<_CharT, _Traits>&
 700         operator<<(basic_ostream<_CharT, _Traits>& __os,
 701                    const subtract_with_carry& __x)
 702         {
 703           std::copy(__x._M_x, __x._M_x + r,
 704                     std::ostream_iterator<_IntType>(__os, " "));
 705           return __os << __x._M_carry;
 706         }
 707
 708       /**
 709        * Extracts the current state of a % subtract_with_carry random number
 710        * gerator engine @p x from the input stream @p is.
 711        *
 712        * @param __is An input stream.
 713        * @param __x  A % subtract_with_carry random number generator engine.
 714        *
 715        * @returns The input stream with the state of @p x extracted or in an
 716        * error state.
 717        */
 718       template<typename _CharT, typename _Traits>
 719         friend basic_istream<_CharT, _Traits>&
 720         operator>>(basic_istream<_CharT, _Traits>& __is,
 721                    subtract_with_carry& __x)
 722         {
 723           for (int __i = 0; __i < r; ++__i)
 724             __is >> __x._M_x[__i];
 725           __is >> __x._M_carry;
 726           return __is;
 727         }
 728
 729     private:
 730       template<class Gen>
 731         void
 732         seed(Gen& g, true_type)
 733         { return seed(static_cast<unsigned long>(g)); }
 734
 735       template<class Gen>
 736         void
 737         seed(Gen& g, false_type);
 738
 739     private:
 740       int         _M_p;
 741       result_type _M_x[long_lag];
 742       result_type _M_carry;
 743     };
 744
 745
 746   /**
 747    * Produces random numbers from some base engine by discarding blocks of
 748    * data.
 749    *
 750    * 0 <= @p r <= @p p
 751    */
 752   template<class UniformRandomNumberGenerator, int p, int r>
 753     class discard_block
 754     {
 755       // __glibcxx_class_requires(typename base_type::result_type,
 756       //                          ArithmeticTypeConcept);
 757
 758     public:
 759       /** The type of the underlying generator engine. */
 760       typedef UniformRandomNumberGenerator    base_type;
 761       /** The type of the generated random value. */
 762       typedef typename base_type::result_type result_type;
 763
 764       // parameter values
 765       static const int block_size = p;
 766       static const int used_block = r;
 767
 768       /**
 769        * Constructs a default %discard_block engine.
 770        *
 771        * The underlying engine is default constrcuted as well.
 772        */
 773       discard_block()
 774       : _M_n(0) { }
 775
 776       /**
 777        * Copy constructs a %discard_block engine.
 778        *
 779        * Copies an existing base class random number geenerator.
 780        * @param rng An existing (base class) engine object.
 781        */
 782       explicit discard_block(const base_type& rng)
 783       : _M_b(rng) , _M_n(0) { }
 784
 785       /**
 786        * Seed constructs a %discard_block engine.
 787        *
 788        * Constructs the underlying generator engine seeded with @p s.
 789        * @param s A seed value for the base class engine.
 790        */
 791       explicit discard_block(unsigned long s)
 792       : _M_b(s), _M_n(0) { }
 793
 794       /**
 795        * Generator constructs a %discard_block engine.
 796        *
 797        * @param g A seed generator function.
 798        */
 799       template<class Gen>
 800         discard_block(Gen& g)
 801         : _M_b(g), _M_n(0) { }
 802
 803       /**
 804        * Reseeds the %discard_block object with the default seed for the
 805        * underlying base class generator engine.
 806        */
 807       void seed()
 808       {
 809         _M_b.seed();
 810         _M_n = 0;
 811       }
 812
 813       /**
 814        * Reseeds the %discard_block object with the given seed generator
 815        * function.
 816        * @param g A seed generator function.
 817        */
 818       template<class Gen>
 819         void seed(Gen& g)
 820         {
 821           _M_b.seed(g);
 822           _M_n = 0;
 823         }
 824
 825       /**
 826        * Gets a const reference to the underlying generator engine object.
 827        */
 828       const base_type&
 829       base() const
 830       { return _M_b; }
 831
 832       /**
 833        * Gets the minimum value in the generated random number range.
 834        */
 835       result_type
 836       min() const
 837       { return _M_b.min(); }
 838
 839       /**
 840        * Gets the maximum value in the generated random number range.
 841        */
 842       result_type
 843       max() const
 844       { return _M_b.max(); }
 845
 846       /**
 847        * Gets the next value in the generated random number sequence.
 848        */
 849       result_type
 850       operator()();
 851
 852       /**
 853        * Compares two %discard_block random number generator objects of
 854        * the same type for equality.
 855        *
 856        * @param __lhs A %discard_block random number generator object.
 857        * @param __rhs Another %discard_block random number generator
 858        *              object.
 859        *
 860        * @returns true if the two objects are equal, false otherwise.
 861        */
 862       friend bool
 863       operator==(const discard_block& __lhs, const discard_block& __rhs)
 864       {
 865         return ((__lhs._M_b == __rhs._M_b)
 866                 && (__lhs._M_n == __rhs._M_n));
 867       }
 868
 869       /**
 870        * Compares two %discard_block random number generator objects of
 871        * the same type for inequality.
 872        *
 873        * @param __lhs A %discard_block random number generator object.
 874        * @param __rhs Another %discard_block random number generator
 875        *              object.
 876        *
 877        * @returns true if the two objects are not equal, false otherwise.
 878        */
 879       friend bool
 880       operator!=(const discard_block& __lhs, const discard_block& __rhs)
 881       { return !(__lhs == __rhs); }
 882
 883       /**
 884        * Inserts the current state of a %discard_block random number
 885        * genator engine @p x into the output stream @p os.
 886        *
 887        * @param __os An output stream.
 888        * @param __x  A %discard_block random number generator engine.
 889        *
 890        * @returns The output stream with the state of @p x inserted or in an
 891        * error state.
 892        */
 893       template<typename _CharT, typename _Traits>
 894         friend basic_ostream<_CharT, _Traits>&
 895         operator<<(basic_ostream<_CharT, _Traits>& __os,
 896                    const discard_block& __x)
 897         { return __os << __x._M_b << " " << __x._M_n; }
 898
 899       /**
 900        * Extracts the current state of a % subtract_with_carry random number
 901        * gerator engine @p x from the input stream @p is.
 902        *
 903        * @param __is An input stream.
 904        * @param __x  A %discard_block random number generator engine.
 905        *
 906        * @returns The input stream with the state of @p x extracted or in an
 907        * error state.
 908        */
 909       template<typename _CharT, typename _Traits>
 910         friend basic_istream<_CharT, _Traits>&
 911         operator>>(basic_istream<_CharT, _Traits>& __is,
 912                    discard_block& __x)
 913         { return __is >> __x._M_b >> __x._M_n; }
 914
 915     private:
 916       base_type _M_b;
 917       int       _M_n;
 918     };
 919
 920
 921   /**
 922    * James's luxury-level-3 integer adaptation of Luescher's generator.
 923    */
 924   typedef discard_block<
 925     subtract_with_carry<int, (1<<24), 10, 24>,
 926       223,
 927       24
 928       > ranlux3;
 929
 930   /**
 931    * James's luxury-level-4 integer adaptation of Luescher's generator.
 932    */
 933   typedef discard_block<
 934     subtract_with_carry<int, (1<<24), 10, 24>,
 935       389,
 936       24
 937       > ranlux4;
 938
 939
 940   /**
 941    * A random number generator adaptor class that combines two random number
 942    * generator engines into a single output sequence.
 943    */
 944   template<class UniformRandomNumberGenerator1, int s1,
 945            class UniformRandomNumberGenerator2, int s2>
 946     class xor_combine
 947     {
 948       // __glibcxx_class_requires(typename UniformRandomNumberGenerator1::
 949       //                          result_type, ArithmeticTypeConcept);
 950       // __glibcxx_class_requires(typename UniformRandomNumberGenerator2::
 951       //                          result_type, ArithmeticTypeConcept);
 952
 953     public:
 954       /** The type of the the first underlying generator engine. */
 955       typedef UniformRandomNumberGenerator1 base1_type;
 956       /** The type of the the second underlying generator engine. */
 957       typedef UniformRandomNumberGenerator2 base2_type;
 958       /** The type of the generated random value. */
 959       typedef typename _Private::_Select<
 960         (sizeof(base1_type) > sizeof(base2_type)),
 961         base1_type,
 962         base2_type
 963         >::Type result_type;
 964
 965       // parameter values
 966       static const int shift1 = s1;
 967       static const int shift2 = s2;
 968
 969       // constructors and member function
 970       xor_combine() { }
 971
 972       xor_combine(const base1_type& rng1, const base2_type& rng2)
 973       : _M_b1(rng1), _M_b2(rng2) { }
 974
 975       xor_combine(unsigned long s)
 976       : _M_b1(s), _M_b2(s + 1) { }
 977
 978       template<class Gen>
 979         xor_combine(Gen& g)
 980         : _M_b1(g), _M_b2(g) { }
 981
 982       void
 983       seed()
 984       {
 985         _M_b1.seed();
 986         _M_b2.seed();
 987       }
 988
 989       template<class Gen>
 990         void
 991         seed(Gen& g)
 992         {
 993           _M_b1.seed(g);
 994           _M_b2.seed(g);
 995         }
 996
 997       const base1_type&
 998       base1() const
 999       { return _M_b1; }
1000
1001       const base2_type&
1002       base2() const
1003       { return _M_b2; }
1004
1005       result_type
1006       min() const
1007       { return _M_b1.min() ^ _M_b2.min(); }
1008
1009       result_type
1010       max() const
1011       { return _M_b1.max() | _M_b2.max(); }
1012
1013       /**
1014        * Gets the next random number in the sequence.
1015        */
1016       result_type
1017       operator()()
1018       { return ((_M_b1() << shift1) ^ (_M_b2() << shift2)); }
1019
1020       /**
1021        * Compares two %xor_combine random number generator objects of
1022        * the same type for equality.
1023        *
1024        * @param __lhs A %xor_combine random number generator object.
1025        * @param __rhs Another %xor_combine random number generator
1026        *              object.
1027        *
1028        * @returns true if the two objects are equal, false otherwise.
1029        */
1030       friend bool
1031       operator==(const xor_combine& __lhs, const xor_combine& __rhs)
1032       {
1033         return (__lhs.base1() == __rhs.base1())
1034           && (__lhs.base2() == __rhs.base2());
1035       }
1036
1037       /**
1038        * Compares two %xor_combine random number generator objects of
1039        * the same type for inequality.
1040        *
1041        * @param __lhs A %xor_combine random number generator object.
1042        * @param __rhs Another %xor_combine random number generator
1043        *              object.
1044        *
1045        * @returns true if the two objects are not equal, false otherwise.
1046        */
1047       friend bool
1048       operator!=(const xor_combine& __lhs, const xor_combine& __rhs)
1049       { return !(__lhs == __rhs); }
1050
1051       /**
1052        * Inserts the current state of a %xor_combine random number
1053        * genator engine @p x into the output stream @p os.
1054        *
1055        * @param __os An output stream.
1056        * @param __x  A %xor_combine random number generator engine.
1057        *
1058        * @returns The output stream with the state of @p x inserted or in an
1059        * error state.
1060        */
1061       template<typename _CharT, typename _Traits>
1062         friend basic_ostream<_CharT, _Traits>&
1063         operator<<(basic_ostream<_CharT, _Traits>& __os,
1064                    const xor_combine& __x)
1065         { return __os << __x.base1() << " " << __x.base1(); }
1066
1067       /**
1068        * Extracts the current state of a %xor_combine random number
1069        * gerator engine @p x from the input stream @p is.
1070        *
1071        * @param __is An input stream.
1072        * @param __x  A %xor_combine random number generator engine.
1073        *
1074        * @returns The input stream with the state of @p x extracted or in an
1075        * error state.
1076        */
1077       template<typename _CharT, typename _Traits>
1078         friend basic_istream<_CharT, _Traits>&
1079         operator>>(basic_istream<_CharT, _Traits>& __is,
1080                    xor_combine& __x)
1081         { return __is >> __x._M_b1 >> __x._M_b2; }
1082
1083     private:
1084       base1_type _M_b1;
1085       base2_type _M_b2;
1086     };
1087
1088
1089   /**
1090    * A standard interface to a platform-specific non-deterministic random number
1091    * generator (if any are available).
1092    *
1093    * @todo The underlying interface is system-specific and needs to be factored
1094    * into the generated configury mechs.  For example, the use of "/dev/random"
1095    * under a Linux OS would be appropriate.
1096    */
1097   class random_device
1098   {
1099   public:
1100     // types
1101     typedef unsigned int result_type;
1102
1103     // constructors, destructors and member functions
1104     explicit random_device(const std::string& token = "unimplemented");
1105     result_type min() const;
1106     result_type max() const;
1107     double entropy() const;
1108     result_type operator()();
1109
1110   private:
1111     random_device(const random_device &);
1112     void operator=(const random_device &);
1113   };
1114
1115   /* @} */ // group tr1_random_generators
1116
1117   /**
1118    * @addtogroup tr1_random_distributions Random Number Distributions
1119    * @ingroup tr1_random
1120    * @{
1121    */
1122
1123   /**
1124    * @addtogroup tr1_random_distributions_discrete Discrete Distributions
1125    * @ingroup tr1_random_distributions
1126    * @{
1127    */
1128
1129   /**
1130    * @brief Uniform discrete distribution for random numbers.
1131    * A discrete random distribution on the range @f$[min, max]@f$ with equal
1132    * probability throughout the range.
1133    */
1134   template<typename _IntType = int>
1135     class uniform_int
1136     {
1137       __glibcxx_class_requires(_IntType, _IntegerConcept)
1138
1139     public:
1140       /** The type of the parameters of the distribution. */
1141       typedef _IntType input_type;
1142       /** The type of the range of the distribution. */
1143       typedef _IntType result_type;
1144
1145     public:
1146       /**
1147        * Constructs a uniform distribution object.
1148        */
1149       explicit
1150       uniform_int(_IntType __min = 0, _IntType __max = 9)
1151       : _M_min(__min), _M_max(__max)
1152       {
1153         _GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
1154       }
1155
1156       /**
1157        * Gets the inclusive lower bound of the distribution range.
1158        */
1159       result_type
1160       min() const
1161       { return _M_min; }
1162
1163       /**
1164        * Gets the inclusive upper bound of the distribution range.
1165        */
1166       result_type
1167       max() const
1168       { return _M_max; }
1169
1170       /**
1171        * Resets the distribution state.
1172        *
1173        * Does nothing for the uniform integer distribution.
1174        */
1175       void
1176       reset() { }
1177
1178       /**
1179        * Gets a uniformly distributed random number in the range
1180        * @f$(min, max)@f$.
1181        */
1182       template<typename _UniformRandomNumberGenerator>
1183         result_type
1184         operator()(_UniformRandomNumberGenerator& __urng)
1185         { return (__urng() % (_M_max - _M_min + 1)) + _M_min; }
1186
1187       /**
1188        * Gets a uniform random number in the range @f$[0, n)@f$.
1189        *
1190        * This function is aimed at use with std::random_shuffle.
1191        */
1192       template<typename _UniformRandomNumberGenerator>
1193         result_type
1194         operator()(_UniformRandomNumberGenerator& __urng, result_type __n)
1195         { return __urng() % __n; }
1196
1197       /**
1198        * Inserts a %uniform_int random number distribution @p x into the
1199        * output stream @p os.
1200        *
1201        * @param __os An output stream.
1202        * @param __x  A %uniform_int random number distribution.
1203        *
1204        * @returns The output stream with the state of @p x inserted or in an
1205        * error state.
1206        */
1207       template<typename _CharT, typename _Traits>
1208         friend basic_ostream<_CharT, _Traits>&
1209         operator<<(basic_ostream<_CharT, _Traits>& __os,
1210                    const uniform_int& __x)
1211         { return __os << __x._M_min << " " << __x._M_max; }
1212
1213       /**
1214        * Extracts a %unform_int random number distribution
1215        * @p u from the input stream @p is.
1216        *
1217        * @param __is An input stream.
1218        * @param __u  A %uniform_int random number generator engine.
1219        *
1220        * @returns The input stream with @p u extracted or in an error state.
1221        */
1222       template<typename _CharT, typename _Traits>
1223         friend basic_istream<_CharT, _Traits>&
1224         operator>>(basic_istream<_CharT, _Traits>& __is, uniform_int& __u)
1225         { return __is >> __u._M_min >> __u._M_max; }
1226
1227     private:
1228       _IntType _M_min;
1229       _IntType _M_max;
1230     };
1231
1232
1233   /**
1234    * @brief A Bernoulli random number distribution.
1235    *
1236    * Generates a sequence of true and false values with likelihood @f$ p @f$
1237    * that true will come up and @f$ (1 - p) @f$ that false will appear.
1238    */
1239   class bernoulli_distribution
1240   {
1241   public:
1242     typedef int  input_type;
1243     typedef bool result_type;
1244
1245   public:
1246     /**
1247      * Constructs a Bernoulli distribution with likelihood @p p.
1248      *
1249      * @param p  [IN]  The likelihood of a true result being returned.  Must
1250      * be in the interval @f$ [0, 1] @f$.
1251      */
1252     explicit
1253     bernoulli_distribution(double __p = 0.5)
1254     : _M_p(__p)
1255     {
1256       _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
1257     }
1258
1259     /**
1260      * Gets the @p p parameter of the distribution.
1261      */
1262     double
1263     p() const
1264     { return _M_p; }
1265
1266     /**
1267      * Gets the inclusive lower bound of the distribution range.
1268      */
1269     result_type
1270     min() const
1271     { return false; }
1272
1273     /**
1274      * Gets the inclusive upper bound of the distribution range.
1275      */
1276     result_type
1277     max() const
1278     { return true; }
1279
1280     /**
1281      * Resets the distribution state.
1282      *
1283      * Does nothing for a bernoulli distribution.
1284      */
1285     void
1286     reset() { }
1287
1288     /**
1289      * Gets the next value in the Bernoullian sequence.
1290      */
1291     template<class UniformRandomNumberGenerator>
1292       result_type
1293       operator()(UniformRandomNumberGenerator& __urng)
1294       {
1295         if (__urng() < _M_p)
1296           return true;
1297         return false;
1298       }
1299
1300     /**
1301      * Inserts a %bernoulli_distribution random number distribution
1302      * @p x into the output stream @p os.
1303      *
1304      * @param __os An output stream.
1305      * @param __x  A %bernoulli_distribution random number distribution.
1306      *
1307      * @returns The output stream with the state of @p x inserted or in an
1308      * error state.
1309      */
1310     template<typename _CharT, typename _Traits>
1311       friend basic_ostream<_CharT, _Traits>&
1312       operator<<(basic_ostream<_CharT, _Traits>& __os,
1313                  const bernoulli_distribution& __x)
1314       { return __os << __x.p(); }
1315
1316     /**
1317      * Extracts a %bernoulli_distribution random number distribution
1318      * @p u from the input stream @p is.
1319      *
1320      * @param __is An input stream.
1321      * @param __u  A %bernoulli_distribution random number generator engine.
1322      *
1323      * @returns The input stream with @p u extracted or in an error state.
1324      */
1325     template<typename _CharT, typename _Traits>
1326       friend basic_istream<_CharT, _Traits>&
1327       operator>>(basic_istream<_CharT, _Traits>& __is,
1328                  bernoulli_distribution& __u)
1329       { return __is >> __u._M_p; }
1330
1331   protected:
1332     double _M_p;
1333   };
1334
1335
1336   /**
1337    * @brief A discrete geometric random number distribution.
1338    *
1339    * The formula for the geometric probability mass function is
1340    * @f$ p(i) = (1 - p)p^{i-1} @f$ where @f$ p @f$ is the parameter of the
1341    * distribution.
1342    */
1343   template<typename _IntType = int, typename _RealType = double>
1344     class geometric_distribution
1345     {
1346     public:
1347       // types
1348       typedef _RealType input_type;
1349       typedef _IntType  result_type;
1350
1351       // constructors and member function
1352
1353       explicit
1354       geometric_distribution(const _RealType& __p = _RealType(0.5))
1355       : _M_p(__p), _M_log_p(std::log(_M_p))
1356       {
1357         _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
1358       }
1359
1360       /**
1361        * Gets the distribution parameter @p.
1362        */
1363       _RealType
1364       p() const
1365       { return _M_p; }
1366
1367       /**
1368        * Gets the inclusive lower bound of the distribution range.
1369        */
1370       result_type
1371       min() const;
1372
1373       /**
1374        * Gets the inclusive upper bound of the distribution range.
1375        */
1376       result_type
1377       max() const;
1378
1379       void
1380       reset() { }
1381
1382       template<class _UniformRandomNumberGenerator>
1383         result_type
1384         operator()(_UniformRandomNumberGenerator& __urng)
1385         {
1386           return result_type(std::floor(std::log(_RealType(1.0) - __urng())
1387                                         / _M_log_p)) + result_type(1);
1388         }
1389
1390       /**
1391        * Inserts a %geometric_distribution random number distribution
1392        * @p x into the output stream @p os.
1393        *
1394        * @param __os An output stream.
1395        * @param __x  A %geometric_distribution random number distribution.
1396        *
1397        * @returns The output stream with the state of @p x inserted or in an
1398        * error state.
1399        */
1400       template<typename _CharT, typename _Traits>
1401         friend basic_ostream<_CharT, _Traits>&
1402         operator<<(basic_ostream<_CharT, _Traits>& __os,
1403                    const geometric_distribution& __x)
1404         { return __os << __x.p(); }
1405
1406       /**
1407        * Extracts a %geometric_distribution random number distribution
1408        * @p u from the input stream @p is.
1409        *
1410        * @param __is An input stream.
1411        * @param __u  A %geometric_distribution random number generator engine.
1412        *
1413        * @returns The input stream with @p u extracted or in an error state.
1414        */
1415       template<typename _CharT, typename _Traits>
1416         friend basic_istream<_CharT, _Traits>&
1417         operator>>(basic_istream<_CharT, _Traits>& __is,
1418                    geometric_distribution& __u)
1419         {
1420           __is >> __u._M_p;
1421           __u._M_log_p = std::log(__u._M_p);
1422           return __is;
1423         }
1424
1425     protected:
1426       _RealType _M_p;
1427       _RealType _M_log_p;
1428     };
1429
1430   /* @} */ // group tr1_random_distributions_discrete
1431
1432   /**
1433    * @addtogroup tr1_random_distributions_continuous Continuous Distributions
1434    * @ingroup tr1_random_distributions
1435    * @{
1436    */
1437
1438   /**
1439    * @brief Uniform continuous distribution for random numbers.
1440    *
1441    * A continuous random distribution on the range [min, max) with equal
1442    * probability throughout the range.  The URNG should be real-valued and
1443    * deliver number in the range [0, 1).
1444    */
1445   template<typename _RealType = double>
1446     class uniform_real
1447     {
1448     public:
1449       // types
1450       typedef _RealType input_type;
1451       typedef _RealType result_type;
1452
1453     public:
1454       /**
1455        * Constructs a uniform_real object.
1456        *
1457        * @param min [IN]  The lower bound of the distribution.
1458        * @param max [IN]  The upper bound of the distribution.
1459        */
1460       explicit
1461       uniform_real(_RealType min = _RealType(0), _RealType max = _RealType(1));
1462
1463       result_type
1464       min() const;
1465
1466       result_type
1467       max() const;
1468
1469       void reset();
1470
1471       template<class _UniformRandomNumberGenerator>
1472         result_type
1473         operator()(_UniformRandomNumberGenerator& __urng)
1474         { return (__urng() * (max() - min())) + min(); }
1475
1476       /**
1477        * Inserts a %uniform_real random number distribution @p x into the
1478        * output stream @p os.
1479        *
1480        * @param __os An output stream.
1481        * @param __x  A %uniform_real random number distribution.
1482        *
1483        * @returns The output stream with the state of @p x inserted or in an
1484        * error state.
1485        */
1486       template<typename _CharT, typename _Traits>
1487         friend basic_ostream<_CharT, _Traits>&
1488         operator<<(basic_ostream<_CharT, _Traits>& __os,
1489                    const uniform_real& __x)
1490         { return __os << __x.min() << " " << __x.max(); }
1491
1492       /**
1493        * Extracts a %unform_real random number distribution
1494        * @p u from the input stream @p is.
1495        *
1496        * @param __is An input stream.
1497        * @param __u  A %uniform_real random number generator engine.
1498        *
1499        * @returns The input stream with @p u extracted or in an error state.
1500        */
1501       template<typename _CharT, typename _Traits>
1502         friend basic_istream<_CharT, _Traits>&
1503         operator>>(basic_istream<_CharT, _Traits>& __is,
1504                  uniform_real& __u)
1505         { return __is >> __u._M_min >> __u._M_max; }
1506
1507     protected:
1508       _RealType _M_min;
1509       _RealType _M_max;
1510     };
1511
1512
1513   /**
1514    * @brief An exponential continuous distribution for random numbers.
1515    *
1516    * The formula for the exponential probability mass function is
1517    * @f$ p(x) = \lambda e^{-\lambda x} @f$.
1518    *
1519    * <table border=1 cellpadding=10 cellspacing=0>
1520    * <caption align=top>Distribution Statistics</caption>
1521    * <tr><td>Mean</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
1522    * <tr><td>Median</td><td>@f$ \frac{\ln 2}{\lambda} @f$</td></tr>
1523    * <tr><td>Mode</td><td>@f$ zero @f$</td></tr>
1524    * <tr><td>Range</td><td>@f$[0, \infty]@f$</td></tr>
1525    * <tr><td>Standard Deviation</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
1526    * </table>
1527    */
1528   template<typename _RealType = double>
1529     class exponential_distribution
1530     {
1531     public:
1532       // types
1533       typedef _RealType input_type;
1534       typedef _RealType result_type;
1535
1536     public:
1537       /**
1538        * Constructs an exponential distribution with inverse scale parameter
1539        * @f$ \lambda @f$.
1540        */
1541       explicit
1542       exponential_distribution(const result_type& __lambda = result_type(1))
1543       : _M_lambda(__lambda) { }
1544
1545       /**
1546        * Gets the inverse scale parameter of the distribution.
1547        */
1548       _RealType
1549       lambda() const
1550       { return _M_lambda; }
1551
1552       /**
1553        * Resets the distribution.
1554        *
1555        * Has no effect on exponential distributions.
1556        */
1557       void
1558       reset() { }
1559
1560       template<class _UniformRandomNumberGenerator>
1561         result_type
1562         operator()(_UniformRandomNumberGenerator& __urng)
1563         { return std::log(__urng) / _M_lambda; }
1564
1565       /**
1566        * Inserts a %exponential_distribution random number distribution
1567        * @p x into the output stream @p os.
1568        *
1569        * @param __os An output stream.
1570        * @param __x  A %exponential_distribution random number distribution.
1571        *
1572        * @returns The output stream with the state of @p x inserted or in an
1573        * error state.
1574        */
1575       template<typename _CharT, typename _Traits>
1576         friend basic_ostream<_CharT, _Traits>&
1577         operator<<(basic_ostream<_CharT, _Traits>& __os,
1578                    const exponential_distribution& __x)
1579         { return __os << __x.lambda(); }
1580
1581       /**
1582        * Extracts a %exponential_distribution random number distribution
1583        * @p u from the input stream @p is.
1584        *
1585        * @param __is An input stream.
1586        * @param __u  A %exponential_distribution random number generator engine.
1587        *
1588        * @returns The input stream with @p u extracted or in an error state.
1589        */
1590       template<typename _CharT, typename _Traits>
1591         friend basic_istream<_CharT, _Traits>&
1592         operator>>(basic_istream<_CharT, _Traits>& __is,
1593                    exponential_distribution& __u)
1594         { return __is >> __u._M_lambda; }
1595
1596     private:
1597       result_type _M_lambda;
1598     };
1599
1600   /* @} */ // group tr1_random_distributions_continuous
1601   /* @} */ // group tr1_random_distributions
1602   /* @} */ // group tr1_random
1603
1604 _GLIBCXX_END_NAMESPACE
1605 }
1606
1607 #include <tr1/random.tcc>
1608
1609 #endif // _STD_TR1_RANDOM