libstdc++-v3/include/tr1/random.tcc

   1 // random number generation (out of line) -*- 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 namespace std
  31 {
  32 _GLIBCXX_BEGIN_NAMESPACE(tr1)
  33
  34   /*
  35    * Implementation-space details.
  36    */
  37   namespace _Private
  38   {
  39     // General case for x = (ax + c) mod m -- use Schrage's algorithm to avoid
  40     // integer overflow.
  41     //
  42     // Because a and c are compile-time integral constants the compiler kindly
  43     // elides any unreachable paths.
  44     //
  45     // Preconditions:  a > 0, m > 0.
  46     //
  47     template<typename _Tp, _Tp __a, _Tp __c, _Tp __m, bool>
  48       struct _Mod
  49       {
  50         static _Tp
  51         __calc(_Tp __x)
  52         {
  53           if (__a == 1)
  54             __x %= __m;
  55           else
  56             {
  57               static const _Tp __q = __m / __a;
  58               static const _Tp __r = __m % __a;
  59
  60               _Tp __t1 = __a * (__x % __q);
  61               _Tp __t2 = __r * (__x / __q);
  62               if (__t1 >= __t2)
  63                 __x = __t1 - __t2;
  64               else
  65                 __x = __m - __t2 + __t1;
  66             }
  67
  68           if (__c != 0)
  69             {
  70               const _Tp __d = __m - __x;
  71               if (__d > __c)
  72                 __x += __c;
  73               else
  74                 __x = __c - __d;
  75             }
  76           return __x;
  77         }
  78       };
  79
  80     // Special case for m == 0 -- use unsigned integer overflow as modulo
  81     // operator.
  82     template<typename _Tp, _Tp __a, _Tp __c, _Tp __m>
  83       struct _Mod<_Tp, __a, __c, __m, true>
  84       {
  85         static _Tp
  86         __calc(_Tp __x)
  87         { return __a * __x + __c; }
  88       };
  89
  90     // Dispatch based on modulus value to prevent divide-by-zero compile-time
  91     // errors when m == 0.
  92     template<typename _Tp, _Tp __a, _Tp __c, _Tp __m>
  93       inline _Tp
  94       __mod(_Tp __x)
  95       { return _Mod<_Tp, __a, __c, __m, __m == 0>::__calc(__x); }
  96
  97     // See N1822.
  98     template<typename _RealType>
  99       struct _Max_digits10
 100       {
 101         static const std::streamsize __value =
 102           2 + std::numeric_limits<_RealType>::digits * 3010/10000;
 103       };
 104
 105     template<typename _ValueT>
 106       struct _To_Unsigned_Type
 107       { typedef _ValueT _Type; };
 108
 109     template<>
 110       struct _To_Unsigned_Type<short>
 111       { typedef unsigned short _Type; };
 112
 113     template<>
 114       struct _To_Unsigned_Type<int>
 115       { typedef unsigned int _Type; };
 116
 117     template<>
 118       struct _To_Unsigned_Type<long>
 119       { typedef unsigned long _Type; };
 120
 121 #ifdef _GLIBCXX_USE_LONG_LONG
 122     template<>
 123       struct _To_Unsigned_Type<long long>
 124       { typedef unsigned long long _Type; };
 125 #endif
 126
 127   } // namespace _Private
 128
 129
 130   /**
 131    * Seeds the LCR with integral value @p __x0, adjusted so that the
 132    * ring identity is never a member of the convergence set.
 133    */
 134   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 135     void
 136     linear_congruential<_UIntType, __a, __c, __m>::
 137     seed(unsigned long __x0)
 138     {
 139       if ((_Private::__mod<_UIntType, 1, 0, __m>(__c) == 0)
 140           && (_Private::__mod<_UIntType, 1, 0, __m>(__x0) == 0))
 141         _M_x = _Private::__mod<_UIntType, 1, 0, __m>(1);
 142       else
 143         _M_x = _Private::__mod<_UIntType, 1, 0, __m>(__x0);
 144     }
 145
 146   /**
 147    * Seeds the LCR engine with a value generated by @p __g.
 148    */
 149   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 150     template<class _Gen>
 151       void
 152       linear_congruential<_UIntType, __a, __c, __m>::
 153       seed(_Gen& __g, false_type)
 154       {
 155         _UIntType __x0 = __g();
 156         if ((_Private::__mod<_UIntType, 1, 0, __m>(__c) == 0)
 157             && (_Private::__mod<_UIntType, 1, 0, __m>(__x0) == 0))
 158           _M_x = _Private::__mod<_UIntType, 1, 0, __m>(1);
 159         else
 160           _M_x = _Private::__mod<_UIntType, 1, 0, __m>(__x0);
 161       }
 162
 163   /**
 164    * Returns a value that is less than or equal to all values potentially
 165    * returned by operator(). The return value of this function does not
 166    * change during the lifetime of the object..
 167    *
 168    * The minumum depends on the @p __c parameter: if it is zero, the
 169    * minimum generated must be > 0, otherwise 0 is allowed.
 170    */
 171   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 172     typename linear_congruential<_UIntType, __a, __c, __m>::result_type
 173     linear_congruential<_UIntType, __a, __c, __m>::
 174     min() const
 175     { return (_Private::__mod<_UIntType, 1, 0, __m>(__c) == 0) ? 1 : 0; }
 176
 177   /**
 178    * Gets the maximum possible value of the generated range.
 179    *
 180    * For a linear congruential generator, the maximum is always @p __m - 1.
 181    */
 182   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 183     typename linear_congruential<_UIntType, __a, __c, __m>::result_type
 184     linear_congruential<_UIntType, __a, __c, __m>::
 185     max() const
 186     { return (__m == 0) ? std::numeric_limits<_UIntType>::max() : (__m - 1); }
 187
 188   /**
 189    * Gets the next generated value in sequence.
 190    */
 191   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 192     typename linear_congruential<_UIntType, __a, __c, __m>::result_type
 193     linear_congruential<_UIntType, __a, __c, __m>::
 194     operator()()
 195     {
 196       _M_x = _Private::__mod<_UIntType, __a, __c, __m>(_M_x);
 197       return _M_x;
 198     }
 199
 200   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m,
 201            typename _CharT, typename _Traits>
 202     std::basic_ostream<_CharT, _Traits>&
 203     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 204                const linear_congruential<_UIntType, __a, __c, __m>& __lcr)
 205     {
 206       const std::ios_base::fmtflags __flags = __os.flags();
 207       const _CharT __fill = __os.fill();
 208       __os.flags(std::ios_base::dec | std::ios_base::fixed
 209                  | std::ios_base::left);
 210       __os.fill(__os.widen(' '));
 211
 212       __os << __lcr._M_x;
 213
 214       __os.flags(__flags);
 215       __os.fill(__fill);
 216       return __os;
 217     }
 218
 219   template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m,
 220            typename _CharT, typename _Traits>
 221     std::basic_istream<_CharT, _Traits>&
 222     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 223                linear_congruential<_UIntType, __a, __c, __m>& __lcr)
 224     {
 225       const std::ios_base::fmtflags __flags = __is.flags();
 226       __is.flags(std::ios_base::dec);
 227
 228       __is >> __lcr._M_x;
 229
 230       __is.flags(__flags);
 231       return __is;
 232     }
 233
 234
 235   template<class _UIntType, int __w, int __n, int __m, int __r,
 236            _UIntType __a, int __u, int __s,
 237            _UIntType __b, int __t, _UIntType __c, int __l>
 238     void
 239     mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
 240                      __b, __t, __c, __l>::
 241     seed(unsigned long __value)
 242     {
 243       _M_x[0] = _Private::__mod<_UIntType, 1, 0,
 244         _Private::_Shift<_UIntType, __w>::__value>(__value);
 245
 246       for (int __i = 1; __i < state_size; ++__i)
 247         {
 248           _UIntType __x = _M_x[__i - 1];
 249           __x ^= __x >> (__w - 2);
 250           __x *= 1812433253ul;
 251           __x += __i;
 252           _M_x[__i] = _Private::__mod<_UIntType, 1, 0,
 253             _Private::_Shift<_UIntType, __w>::__value>(__x);
 254         }
 255       _M_p = state_size;
 256     }
 257
 258   template<class _UIntType, int __w, int __n, int __m, int __r,
 259            _UIntType __a, int __u, int __s,
 260            _UIntType __b, int __t, _UIntType __c, int __l>
 261     template<class _Gen>
 262       void
 263       mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
 264                        __b, __t, __c, __l>::
 265       seed(_Gen& __gen, false_type)
 266       {
 267         for (int __i = 0; __i < state_size; ++__i)
 268           _M_x[__i] = _Private::__mod<_UIntType, 1, 0,
 269             _Private::_Shift<_UIntType, __w>::__value>(__gen());
 270         _M_p = state_size;
 271       }
 272
 273   template<class _UIntType, int __w, int __n, int __m, int __r,
 274            _UIntType __a, int __u, int __s,
 275            _UIntType __b, int __t, _UIntType __c, int __l>
 276     typename
 277     mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
 278                      __b, __t, __c, __l>::result_type
 279     mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
 280                      __b, __t, __c, __l>::
 281     operator()()
 282     {
 283       // Reload the vector - cost is O(n) amortized over n calls.
 284       if (_M_p >= state_size)
 285         {
 286           const _UIntType __upper_mask = (~_UIntType()) << __r;
 287           const _UIntType __lower_mask = ~__upper_mask;
 288
 289           for (int __k = 0; __k < (__n - __m); ++__k)
 290             {
 291               _UIntType __y = ((_M_x[__k] & __upper_mask)
 292                                | (_M_x[__k + 1] & __lower_mask));
 293               _M_x[__k] = (_M_x[__k + __m] ^ (__y >> 1)
 294                            ^ ((__y & 0x01) ? __a : 0));
 295             }
 296
 297           for (int __k = (__n - __m); __k < (__n - 1); ++__k)
 298             {
 299               _UIntType __y = ((_M_x[__k] & __upper_mask)
 300                                | (_M_x[__k + 1] & __lower_mask));
 301               _M_x[__k] = (_M_x[__k + (__m - __n)] ^ (__y >> 1)
 302                            ^ ((__y & 0x01) ? __a : 0));
 303             }
 304
 305           _UIntType __y = ((_M_x[__n - 1] & __upper_mask)
 306                            | (_M_x[0] & __lower_mask));
 307           _M_x[__n - 1] = (_M_x[__m - 1] ^ (__y >> 1)
 308                            ^ ((__y & 0x01) ? __a : 0));
 309           _M_p = 0;
 310         }
 311
 312       // Calculate o(x(i)).
 313       result_type __z = _M_x[_M_p++];
 314       __z ^= (__z >> __u);
 315       __z ^= (__z << __s) & __b;
 316       __z ^= (__z << __t) & __c;
 317       __z ^= (__z >> __l);
 318
 319       return __z;
 320     }
 321
 322   template<class _UIntType, int __w, int __n, int __m, int __r,
 323            _UIntType __a, int __u, int __s, _UIntType __b, int __t,
 324            _UIntType __c, int __l,
 325            typename _CharT, typename _Traits>
 326     std::basic_ostream<_CharT, _Traits>&
 327     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 328                const mersenne_twister<_UIntType, __w, __n, __m,
 329                __r, __a, __u, __s, __b, __t, __c, __l>& __x)
 330     {
 331       const std::ios_base::fmtflags __flags = __os.flags();
 332       const _CharT __fill = __os.fill();
 333       const _CharT __space = __os.widen(' ');
 334       __os.flags(std::ios_base::dec | std::ios_base::fixed
 335                  | std::ios_base::left);
 336       __os.fill(__space);
 337
 338       for (int __i = 0; __i < __n - 1; ++__i)
 339         __os << __x._M_x[__i] << __space;
 340       __os << __x._M_x[__n - 1];
 341
 342       __os.flags(__flags);
 343       __os.fill(__fill);
 344       return __os;
 345     }
 346
 347   template<class _UIntType, int __w, int __n, int __m, int __r,
 348            _UIntType __a, int __u, int __s, _UIntType __b, int __t,
 349            _UIntType __c, int __l,
 350            typename _CharT, typename _Traits>
 351     std::basic_istream<_CharT, _Traits>&
 352     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 353                mersenne_twister<_UIntType, __w, __n, __m,
 354                __r, __a, __u, __s, __b, __t, __c, __l>& __x)
 355     {
 356       const std::ios_base::fmtflags __flags = __is.flags();
 357       __is.flags(std::ios_base::dec | std::ios_base::skipws);
 358
 359       for (int __i = 0; __i < __n; ++__i)
 360         __is >> __x._M_x[__i];
 361
 362       __is.flags(__flags);
 363       return __is;
 364     }
 365
 366
 367   template<typename _IntType, _IntType __m, int __s, int __r>
 368     void
 369     subtract_with_carry<_IntType, __m, __s, __r>::
 370     seed(unsigned long __value)
 371     {
 372       if (__value == 0)
 373         __value = 19780503;
 374
 375       std::tr1::linear_congruential<unsigned long, 40014, 0, 2147483563>
 376         __lcg(__value);
 377
 378       for (int __i = 0; __i < long_lag; ++__i)
 379         _M_x[__i] = _Private::__mod<_IntType, 1, 0, modulus>(__lcg());
 380
 381       _M_carry = (_M_x[long_lag - 1] == 0) ? 1 : 0;
 382       _M_p = 0;
 383     }
 384
 385   template<typename _IntType, _IntType __m, int __s, int __r>
 386     template<class _Gen>
 387       void
 388       subtract_with_carry<_IntType, __m, __s, __r>::
 389       seed(_Gen& __gen, false_type)
 390       {
 391         const int __n = (std::numeric_limits<_IntType>::digits + 31) / 32;
 392
 393         typedef typename _Private::_Select<(sizeof(unsigned) == 4),
 394           unsigned, unsigned long>::_Type _UInt32Type;
 395
 396         typedef typename _Private::_To_Unsigned_Type<_IntType>::_Type
 397           _UIntType;
 398
 399         for (int __i = 0; __i < long_lag; ++__i)
 400           {
 401             _UIntType __tmp = 0;
 402             _UIntType __factor = 1;
 403             for (int __j = 0; __j < __n; ++__j)
 404               {
 405                 __tmp += (_Private::__mod<_UInt32Type, 1, 0, 0>(__gen())
 406                           * __factor);
 407                 __factor *= _Private::_Shift<_UIntType, 32>::__value;
 408               }
 409             _M_x[__i] = _Private::__mod<_UIntType, 1, 0, modulus>(__tmp);
 410           }
 411         _M_carry = (_M_x[long_lag - 1] == 0) ? 1 : 0;
 412         _M_p = 0;
 413       }
 414
 415   template<typename _IntType, _IntType __m, int __s, int __r>
 416     typename subtract_with_carry<_IntType, __m, __s, __r>::result_type
 417     subtract_with_carry<_IntType, __m, __s, __r>::
 418     operator()()
 419     {
 420       // Derive short lag index from current index.
 421       int __ps = _M_p - short_lag;
 422       if (__ps < 0)
 423         __ps += long_lag;
 424
 425       // Calculate new x(i) without overflow or division.
 426       _IntType __xi;
 427       if (_M_x[__ps] >= _M_x[_M_p] + _M_carry)
 428         {
 429           __xi = _M_x[__ps] - _M_x[_M_p] - _M_carry;
 430           _M_carry = 0;
 431         }
 432       else
 433         {
 434           __xi = modulus - _M_x[_M_p] - _M_carry + _M_x[__ps];
 435           _M_carry = 1;
 436         }
 437       _M_x[_M_p++] = __xi;
 438
 439       // Adjust current index to loop around in ring buffer.
 440       if (_M_p >= long_lag)
 441         _M_p = 0;
 442
 443       return __xi;
 444     }
 445
 446   template<typename _IntType, _IntType __m, int __s, int __r,
 447            typename _CharT, typename _Traits>
 448     std::basic_ostream<_CharT, _Traits>&
 449     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 450                const subtract_with_carry<_IntType, __m, __s, __r>& __x)
 451     {
 452       const std::ios_base::fmtflags __flags = __os.flags();
 453       const _CharT __fill = __os.fill();
 454       const _CharT __space = __os.widen(' ');
 455       __os.flags(std::ios_base::dec | std::ios_base::fixed
 456                  | std::ios_base::left);
 457       __os.fill(__space);
 458
 459       for (int __i = 0; __i < __r; ++__i)
 460         __os << __x._M_x[__i] << __space;
 461       __os << __x._M_carry;
 462
 463       __os.flags(__flags);
 464       __os.fill(__fill);
 465       return __os;
 466     }
 467
 468   template<typename _IntType, _IntType __m, int __s, int __r,
 469            typename _CharT, typename _Traits>
 470     std::basic_istream<_CharT, _Traits>&
 471     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 472                subtract_with_carry<_IntType, __m, __s, __r>& __x)
 473     {
 474       const std::ios_base::fmtflags __flags = __is.flags();
 475       __is.flags(std::ios_base::dec | std::ios_base::skipws);
 476
 477       for (int __i = 0; __i < __r; ++__i)
 478         __is >> __x._M_x[__i];
 479       __is >> __x._M_carry;
 480
 481       __is.flags(__flags);
 482       return __is;
 483     }
 484
 485
 486   template<class _UniformRandomNumberGenerator, int __p, int __r>
 487     typename discard_block<_UniformRandomNumberGenerator,
 488                            __p, __r>::result_type
 489     discard_block<_UniformRandomNumberGenerator, __p, __r>::
 490     operator()()
 491     {
 492       if (_M_n >= used_block)
 493         {
 494           while (_M_n < block_size)
 495             {
 496               _M_b();
 497               ++_M_n;
 498             }
 499           _M_n = 0;
 500         }
 501       ++_M_n;
 502       return _M_b();
 503     }
 504
 505   template<class _UniformRandomNumberGenerator, int __p, int __r,
 506            typename _CharT, typename _Traits>
 507     std::basic_ostream<_CharT, _Traits>&
 508     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 509                const discard_block<_UniformRandomNumberGenerator,
 510                __p, __r>& __x)
 511     {
 512       const std::ios_base::fmtflags __flags = __os.flags();
 513       const _CharT __fill = __os.fill();
 514       const _CharT __space = __os.widen(' ');
 515       __os.flags(std::ios_base::dec | std::ios_base::fixed
 516                  | std::ios_base::left);
 517       __os.fill(__space);
 518
 519       __os << __x._M_b << __space << __x._M_n;
 520
 521       __os.flags(__flags);
 522       __os.fill(__fill);
 523       return __os;
 524     }
 525
 526   template<class _UniformRandomNumberGenerator, int __p, int __r,
 527            typename _CharT, typename _Traits>
 528     std::basic_istream<_CharT, _Traits>&
 529     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 530                discard_block<_UniformRandomNumberGenerator, __p, __r>& __x)
 531     {
 532       const std::ios_base::fmtflags __flags = __is.flags();
 533       __is.flags(std::ios_base::dec | std::ios_base::skipws);
 534
 535       __is >> __x._M_b >> __x._M_n;
 536
 537       __is.flags(__flags);
 538       return __is;
 539     }
 540
 541
 542   template<class _UniformRandomNumberGenerator1, int __s1,
 543            class _UniformRandomNumberGenerator2, int __s2,
 544            typename _CharT, typename _Traits>
 545     std::basic_ostream<_CharT, _Traits>&
 546     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 547                const xor_combine<_UniformRandomNumberGenerator1, __s1,
 548                _UniformRandomNumberGenerator2, __s2>& __x)
 549     {
 550       const std::ios_base::fmtflags __flags = __os.flags();
 551       const _CharT __fill = __os.fill();
 552       const _CharT __space = __os.widen(' ');
 553       __os.flags(std::ios_base::dec | std::ios_base::fixed
 554                  | std::ios_base::left);
 555       __os.fill(__space);
 556
 557       __os << __x.base1() << __space << __x.base2();
 558
 559       __os.flags(__flags);
 560       __os.fill(__fill);
 561       return __os;
 562     }
 563
 564   template<class _UniformRandomNumberGenerator1, int __s1,
 565            class _UniformRandomNumberGenerator2, int __s2,
 566            typename _CharT, typename _Traits>
 567     std::basic_istream<_CharT, _Traits>&
 568     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 569                xor_combine<_UniformRandomNumberGenerator1, __s1,
 570                _UniformRandomNumberGenerator2, __s2>& __x)
 571     {
 572       const std::ios_base::fmtflags __flags = __is.flags();
 573       __is.flags(std::ios_base::skipws);
 574
 575       __is >> __x._M_b1 >> __x._M_b2;
 576
 577       __is.flags(__flags);
 578       return __is;
 579     }
 580
 581
 582   template<typename _IntType, typename _CharT, typename _Traits>
 583     std::basic_ostream<_CharT, _Traits>&
 584     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 585                const uniform_int<_IntType>& __x)
 586     {
 587       const std::ios_base::fmtflags __flags = __os.flags();
 588       const _CharT __fill = __os.fill();
 589       const _CharT __space = __os.widen(' ');
 590       __os.flags(std::ios_base::scientific | std::ios_base::left);
 591       __os.fill(__space);
 592
 593       __os << __x.min() << __space << __x.max();
 594
 595       __os.flags(__flags);
 596       __os.fill(__fill);
 597       return __os;
 598     }
 599
 600   template<typename _IntType, typename _CharT, typename _Traits>
 601     std::basic_istream<_CharT, _Traits>&
 602     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 603                uniform_int<_IntType>& __x)
 604     {
 605       const std::ios_base::fmtflags __flags = __is.flags();
 606       __is.flags(std::ios_base::dec | std::ios_base::skipws);
 607
 608       __is >> __x._M_min >> __x._M_max;
 609
 610       __is.flags(__flags);
 611       return __is;
 612     }
 613
 614
 615   template<typename _CharT, typename _Traits>
 616     std::basic_ostream<_CharT, _Traits>&
 617     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 618                const bernoulli_distribution& __x)
 619     {
 620       const std::ios_base::fmtflags __flags = __os.flags();
 621       const _CharT __fill = __os.fill();
 622       const std::streamsize __precision = __os.precision();
 623       __os.flags(std::ios_base::scientific | std::ios_base::left);
 624       __os.fill(__os.widen(' '));
 625       __os.precision(_Private::_Max_digits10<double>::__value);
 626
 627       __os << __x.p();
 628
 629       __os.flags(__flags);
 630       __os.fill(__fill);
 631       __os.precision(__precision);
 632       return __os;
 633     }
 634
 635
 636   template<typename _IntType, typename _RealType,
 637            typename _CharT, typename _Traits>
 638     std::basic_ostream<_CharT, _Traits>&
 639     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 640                const geometric_distribution<_IntType, _RealType>& __x)
 641     {
 642       const std::ios_base::fmtflags __flags = __os.flags();
 643       const _CharT __fill = __os.fill();
 644       const std::streamsize __precision = __os.precision();
 645       __os.flags(std::ios_base::scientific | std::ios_base::left);
 646       __os.fill(__os.widen(' '));
 647       __os.precision(_Private::_Max_digits10<_RealType>::__value);
 648
 649       __os << __x.p();
 650
 651       __os.flags(__flags);
 652       __os.fill(__fill);
 653       __os.precision(__precision);
 654       return __os;
 655     }
 656
 657
 658   template<typename _RealType, typename _CharT, typename _Traits>
 659     std::basic_ostream<_CharT, _Traits>&
 660     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 661                const uniform_real<_RealType>& __x)
 662     {
 663       const std::ios_base::fmtflags __flags = __os.flags();
 664       const _CharT __fill = __os.fill();
 665       const std::streamsize __precision = __os.precision();
 666       const _CharT __space = __os.widen(' ');
 667       __os.flags(std::ios_base::scientific | std::ios_base::left);
 668       __os.fill(__space);
 669       __os.precision(_Private::_Max_digits10<_RealType>::__value);
 670
 671       __os << __x.min() << __space << __x.max();
 672
 673       __os.flags(__flags);
 674       __os.fill(__fill);
 675       __os.precision(__precision);
 676       return __os;
 677     }
 678
 679   template<typename _RealType, typename _CharT, typename _Traits>
 680     std::basic_istream<_CharT, _Traits>&
 681     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 682                uniform_real<_RealType>& __x)
 683     {
 684       const std::ios_base::fmtflags __flags = __is.flags();
 685       __is.flags(std::ios_base::skipws);
 686
 687       __is >> __x._M_min >> __x._M_max;
 688
 689       __is.flags(__flags);
 690       return __is;
 691     }
 692
 693
 694   template<typename _RealType, typename _CharT, typename _Traits>
 695     std::basic_ostream<_CharT, _Traits>&
 696     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 697                const exponential_distribution<_RealType>& __x)
 698     {
 699       const std::ios_base::fmtflags __flags = __os.flags();
 700       const _CharT __fill = __os.fill();
 701       const std::streamsize __precision = __os.precision();
 702       __os.flags(std::ios_base::scientific | std::ios_base::left);
 703       __os.fill(__os.widen(' '));
 704       __os.precision(_Private::_Max_digits10<_RealType>::__value);
 705
 706       __os << __x.lambda();
 707
 708       __os.flags(__flags);
 709       __os.fill(__fill);
 710       __os.precision(__precision);
 711       return __os;
 712     }
 713
 714
 715   /**
 716    * Classic Box-Muller method.
 717    *
 718    * Reference:
 719    * Box, G. E. P. and Muller, M. E. "A Note on the Generation of
 720    * Random Normal Deviates." Ann. Math. Stat. 29, 610-611, 1958.
 721    */
 722   template<typename _RealType>
 723     template<class _UniformRandomNumberGenerator>
 724       typename normal_distribution<_RealType>::result_type
 725       normal_distribution<_RealType>::
 726       operator()(_UniformRandomNumberGenerator& __urng)
 727       {
 728         result_type __ret;
 729
 730         if (_M_saved_available)
 731           {
 732             _M_saved_available = false;
 733             __ret = _M_saved;
 734           }
 735         else
 736           {
 737             result_type __x, __y, __r2;
 738             do
 739               {
 740                 __x = result_type(2.0) * __urng() - result_type(1.0);
 741                 __y = result_type(2.0) * __urng() - result_type(1.0);
 742                 __r2 = __x * __x + __y * __y;
 743               }
 744             while (__r2 > result_type(1.0) || __r2 == result_type(0));
 745
 746             const result_type __mult = std::sqrt(-result_type(2.0)
 747                                                  * std::log(__r2) / __r2);
 748             _M_saved = __x * __mult;
 749             _M_saved_available = true;
 750             __ret = __y * __mult;
 751           }
 752
 753         return __ret * _M_sigma + _M_mean;
 754       }
 755
 756   template<typename _RealType, typename _CharT, typename _Traits>
 757     std::basic_ostream<_CharT, _Traits>&
 758     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 759                const normal_distribution<_RealType>& __x)
 760     {
 761       const std::ios_base::fmtflags __flags = __os.flags();
 762       const _CharT __fill = __os.fill();
 763       const std::streamsize __precision = __os.precision();
 764       const _CharT __space = __os.widen(' ');
 765       __os.flags(std::ios_base::scientific | std::ios_base::left);
 766       __os.fill(__space);
 767       __os.precision(_Private::_Max_digits10<_RealType>::__value);
 768
 769       __os << __x.mean() << __space
 770            << __x.sigma() << __space
 771            << __x._M_saved << __space
 772            << __x._M_saved_available;
 773
 774       __os.flags(__flags);
 775       __os.fill(__fill);
 776       __os.precision(__precision);
 777       return __os;
 778     }
 779
 780   template<typename _RealType, typename _CharT, typename _Traits>
 781     std::basic_istream<_CharT, _Traits>&
 782     operator>>(std::basic_istream<_CharT, _Traits>& __is,
 783                normal_distribution<_RealType>& __x)
 784     {
 785       const std::ios_base::fmtflags __flags = __is.flags();
 786       __is.flags(std::ios_base::dec | std::ios_base::skipws);
 787
 788       __is >> __x._M_mean >> __x._M_sigma
 789            >> __x._M_saved >> __x._M_saved_available;
 790
 791       __is.flags(__flags);
 792       return __is;
 793     }
 794
 795
 796   /**
 797    * Cheng's rejection algorithm GB for alpha >= 1 and a modification
 798    * of Vaduva's rejection from Weibull algorithm due to Devroye for
 799    * alpha < 1.
 800    *
 801    * References:
 802    * Cheng, R. C. "The Generation of Gamma Random Variables with Non-integral
 803    * Shape Parameter." Applied Statistics, 26, 71-75, 1977.
 804    *
 805    * Vaduva, I. "Computer Generation of Gamma Gandom Variables by Rejection
 806    * and Composition Procedures." Math. Operationsforschung and Statistik,
 807    * Series in Statistics, 8, 545-576, 1977.
 808    *
 809    * Devroye, L. "Non-Uniform Random Variates Generation." Springer-Verlag,
 810    * New York, 1986, Sect. 3.4.
 811    */
 812   template<typename _RealType>
 813     template<class _UniformRandomNumberGenerator>
 814       typename gamma_distribution<_RealType>::result_type
 815       gamma_distribution<_RealType>::
 816       operator()(_UniformRandomNumberGenerator& __urng)
 817       {
 818         result_type __x;
 819
 820         if (_M_alpha >= 1)
 821           {
 822             // alpha - log(4)
 823             const result_type __b = _M_alpha
 824               - result_type(1.3862943611198906188344642429163531L);
 825             const result_type __c = _M_alpha + std::sqrt(2 * _M_alpha - 1);
 826
 827             // 1 + log(9 / 2)
 828             const result_type __k = 2.5040773967762740733732583523868748L;
 829
 830             result_type __z, __r;
 831             do
 832               {
 833                 const result_type __u = __urng();
 834                 const result_type __v = __urng();
 835
 836                 const result_type __y = _M_alpha * std::log(__v / (1 - __v));
 837                 __x = _M_alpha * std::exp(__v);
 838
 839                 __z = __u * __v * __v;
 840                 __r = __b + __c * __y - __x;
 841               }
 842             while (__r < result_type(4.5) * __z - __k
 843                    && __r < std::log(__z));
 844           }
 845         else
 846           {
 847             const result_type __c = 1 / _M_alpha;
 848             const result_type __d =
 849               std::pow(_M_alpha, _M_alpha / (1 - _M_alpha)) * (1 - _M_alpha);
 850
 851             result_type __z, __e;
 852             do
 853               {
 854                 __z = -std::log(__urng());
 855                 __e = -std::log(__urng());
 856
 857                 __x = std::pow(__z, __c);
 858               }
 859             while (__z + __e > __d + __x);
 860           }
 861
 862         return __x;
 863       }
 864
 865   template<typename _RealType, typename _CharT, typename _Traits>
 866     std::basic_ostream<_CharT, _Traits>&
 867     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
 868                const gamma_distribution<_RealType>& __x)
 869     {
 870       const std::ios_base::fmtflags __flags = __os.flags();
 871       const _CharT __fill = __os.fill();
 872       const std::streamsize __precision = __os.precision();
 873       __os.flags(std::ios_base::scientific | std::ios_base::left);
 874       __os.fill(__os.widen(' '));
 875       __os.precision(_Private::_Max_digits10<_RealType>::__value);
 876
 877       __os << __x.alpha();
 878
 879       __os.flags(__flags);
 880       __os.fill(__fill);
 881       __os.precision(__precision);
 882       return __os;
 883     }
 884
 885 _GLIBCXX_END_NAMESPACE
 886 }