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