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