OSDN Git Service

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