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