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