1 // random number generation (out of line) -*- C++ -*-
3 // Copyright (C) 2009, 2010 Free Software Foundation, Inc.
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)
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.
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.
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/>.
26 /** @file tr1/random.tcc
27 * This is an internal header file, included by other library headers.
28 * You should not attempt to use it directly.
36 * (Further) implementation-space details.
40 // General case for x = (ax + c) mod m -- use Schrage's algorithm to avoid
43 // Because a and c are compile-time integral constants the compiler kindly
44 // elides any unreachable paths.
46 // Preconditions: a > 0, m > 0.
48 template<typename _Tp, _Tp __a, _Tp __c, _Tp __m, bool>
58 static const _Tp __q = __m / __a;
59 static const _Tp __r = __m % __a;
61 _Tp __t1 = __a * (__x % __q);
62 _Tp __t2 = __r * (__x / __q);
66 __x = __m - __t2 + __t1;
71 const _Tp __d = __m - __x;
81 // Special case for m == 0 -- use unsigned integer overflow as modulo
83 template<typename _Tp, _Tp __a, _Tp __c, _Tp __m>
84 struct _Mod<_Tp, __a, __c, __m, true>
88 { return __a * __x + __c; }
90 } // namespace __detail
93 template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
95 linear_congruential<_UIntType, __a, __c, __m>::multiplier;
97 template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
99 linear_congruential<_UIntType, __a, __c, __m>::increment;
101 template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
103 linear_congruential<_UIntType, __a, __c, __m>::modulus;
106 * Seeds the LCR with integral value @p __x0, adjusted so that the
107 * ring identity is never a member of the convergence set.
109 template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
111 linear_congruential<_UIntType, __a, __c, __m>::
112 seed(unsigned long __x0)
114 if ((__detail::__mod<_UIntType, 1, 0, __m>(__c) == 0)
115 && (__detail::__mod<_UIntType, 1, 0, __m>(__x0) == 0))
116 _M_x = __detail::__mod<_UIntType, 1, 0, __m>(1);
118 _M_x = __detail::__mod<_UIntType, 1, 0, __m>(__x0);
122 * Seeds the LCR engine with a value generated by @p __g.
124 template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
127 linear_congruential<_UIntType, __a, __c, __m>::
128 seed(_Gen& __g, false_type)
130 _UIntType __x0 = __g();
131 if ((__detail::__mod<_UIntType, 1, 0, __m>(__c) == 0)
132 && (__detail::__mod<_UIntType, 1, 0, __m>(__x0) == 0))
133 _M_x = __detail::__mod<_UIntType, 1, 0, __m>(1);
135 _M_x = __detail::__mod<_UIntType, 1, 0, __m>(__x0);
139 * Gets the next generated value in sequence.
141 template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
142 typename linear_congruential<_UIntType, __a, __c, __m>::result_type
143 linear_congruential<_UIntType, __a, __c, __m>::
146 _M_x = __detail::__mod<_UIntType, __a, __c, __m>(_M_x);
150 template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m,
151 typename _CharT, typename _Traits>
152 std::basic_ostream<_CharT, _Traits>&
153 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
154 const linear_congruential<_UIntType, __a, __c, __m>& __lcr)
156 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
157 typedef typename __ostream_type::ios_base __ios_base;
159 const typename __ios_base::fmtflags __flags = __os.flags();
160 const _CharT __fill = __os.fill();
161 __os.flags(__ios_base::dec | __ios_base::fixed | __ios_base::left);
162 __os.fill(__os.widen(' '));
171 template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m,
172 typename _CharT, typename _Traits>
173 std::basic_istream<_CharT, _Traits>&
174 operator>>(std::basic_istream<_CharT, _Traits>& __is,
175 linear_congruential<_UIntType, __a, __c, __m>& __lcr)
177 typedef std::basic_istream<_CharT, _Traits> __istream_type;
178 typedef typename __istream_type::ios_base __ios_base;
180 const typename __ios_base::fmtflags __flags = __is.flags();
181 __is.flags(__ios_base::dec);
190 template<class _UIntType, int __w, int __n, int __m, int __r,
191 _UIntType __a, int __u, int __s,
192 _UIntType __b, int __t, _UIntType __c, int __l>
194 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
195 __b, __t, __c, __l>::word_size;
197 template<class _UIntType, int __w, int __n, int __m, int __r,
198 _UIntType __a, int __u, int __s,
199 _UIntType __b, int __t, _UIntType __c, int __l>
201 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
202 __b, __t, __c, __l>::state_size;
204 template<class _UIntType, int __w, int __n, int __m, int __r,
205 _UIntType __a, int __u, int __s,
206 _UIntType __b, int __t, _UIntType __c, int __l>
208 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
209 __b, __t, __c, __l>::shift_size;
211 template<class _UIntType, int __w, int __n, int __m, int __r,
212 _UIntType __a, int __u, int __s,
213 _UIntType __b, int __t, _UIntType __c, int __l>
215 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
216 __b, __t, __c, __l>::mask_bits;
218 template<class _UIntType, int __w, int __n, int __m, int __r,
219 _UIntType __a, int __u, int __s,
220 _UIntType __b, int __t, _UIntType __c, int __l>
222 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
223 __b, __t, __c, __l>::parameter_a;
225 template<class _UIntType, int __w, int __n, int __m, int __r,
226 _UIntType __a, int __u, int __s,
227 _UIntType __b, int __t, _UIntType __c, int __l>
229 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
230 __b, __t, __c, __l>::output_u;
232 template<class _UIntType, int __w, int __n, int __m, int __r,
233 _UIntType __a, int __u, int __s,
234 _UIntType __b, int __t, _UIntType __c, int __l>
236 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
237 __b, __t, __c, __l>::output_s;
239 template<class _UIntType, int __w, int __n, int __m, int __r,
240 _UIntType __a, int __u, int __s,
241 _UIntType __b, int __t, _UIntType __c, int __l>
243 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
244 __b, __t, __c, __l>::output_b;
246 template<class _UIntType, int __w, int __n, int __m, int __r,
247 _UIntType __a, int __u, int __s,
248 _UIntType __b, int __t, _UIntType __c, int __l>
250 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
251 __b, __t, __c, __l>::output_t;
253 template<class _UIntType, int __w, int __n, int __m, int __r,
254 _UIntType __a, int __u, int __s,
255 _UIntType __b, int __t, _UIntType __c, int __l>
257 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
258 __b, __t, __c, __l>::output_c;
260 template<class _UIntType, int __w, int __n, int __m, int __r,
261 _UIntType __a, int __u, int __s,
262 _UIntType __b, int __t, _UIntType __c, int __l>
264 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
265 __b, __t, __c, __l>::output_l;
267 template<class _UIntType, int __w, int __n, int __m, int __r,
268 _UIntType __a, int __u, int __s,
269 _UIntType __b, int __t, _UIntType __c, int __l>
271 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
272 __b, __t, __c, __l>::
273 seed(unsigned long __value)
275 _M_x[0] = __detail::__mod<_UIntType, 1, 0,
276 __detail::_Shift<_UIntType, __w>::__value>(__value);
278 for (int __i = 1; __i < state_size; ++__i)
280 _UIntType __x = _M_x[__i - 1];
281 __x ^= __x >> (__w - 2);
284 _M_x[__i] = __detail::__mod<_UIntType, 1, 0,
285 __detail::_Shift<_UIntType, __w>::__value>(__x);
290 template<class _UIntType, int __w, int __n, int __m, int __r,
291 _UIntType __a, int __u, int __s,
292 _UIntType __b, int __t, _UIntType __c, int __l>
295 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
296 __b, __t, __c, __l>::
297 seed(_Gen& __gen, false_type)
299 for (int __i = 0; __i < state_size; ++__i)
300 _M_x[__i] = __detail::__mod<_UIntType, 1, 0,
301 __detail::_Shift<_UIntType, __w>::__value>(__gen());
305 template<class _UIntType, int __w, int __n, int __m, int __r,
306 _UIntType __a, int __u, int __s,
307 _UIntType __b, int __t, _UIntType __c, int __l>
309 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
310 __b, __t, __c, __l>::result_type
311 mersenne_twister<_UIntType, __w, __n, __m, __r, __a, __u, __s,
312 __b, __t, __c, __l>::
315 // Reload the vector - cost is O(n) amortized over n calls.
316 if (_M_p >= state_size)
318 const _UIntType __upper_mask = (~_UIntType()) << __r;
319 const _UIntType __lower_mask = ~__upper_mask;
321 for (int __k = 0; __k < (__n - __m); ++__k)
323 _UIntType __y = ((_M_x[__k] & __upper_mask)
324 | (_M_x[__k + 1] & __lower_mask));
325 _M_x[__k] = (_M_x[__k + __m] ^ (__y >> 1)
326 ^ ((__y & 0x01) ? __a : 0));
329 for (int __k = (__n - __m); __k < (__n - 1); ++__k)
331 _UIntType __y = ((_M_x[__k] & __upper_mask)
332 | (_M_x[__k + 1] & __lower_mask));
333 _M_x[__k] = (_M_x[__k + (__m - __n)] ^ (__y >> 1)
334 ^ ((__y & 0x01) ? __a : 0));
337 _UIntType __y = ((_M_x[__n - 1] & __upper_mask)
338 | (_M_x[0] & __lower_mask));
339 _M_x[__n - 1] = (_M_x[__m - 1] ^ (__y >> 1)
340 ^ ((__y & 0x01) ? __a : 0));
344 // Calculate o(x(i)).
345 result_type __z = _M_x[_M_p++];
347 __z ^= (__z << __s) & __b;
348 __z ^= (__z << __t) & __c;
354 template<class _UIntType, int __w, int __n, int __m, int __r,
355 _UIntType __a, int __u, int __s, _UIntType __b, int __t,
356 _UIntType __c, int __l,
357 typename _CharT, typename _Traits>
358 std::basic_ostream<_CharT, _Traits>&
359 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
360 const mersenne_twister<_UIntType, __w, __n, __m,
361 __r, __a, __u, __s, __b, __t, __c, __l>& __x)
363 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
364 typedef typename __ostream_type::ios_base __ios_base;
366 const typename __ios_base::fmtflags __flags = __os.flags();
367 const _CharT __fill = __os.fill();
368 const _CharT __space = __os.widen(' ');
369 __os.flags(__ios_base::dec | __ios_base::fixed | __ios_base::left);
372 for (int __i = 0; __i < __n - 1; ++__i)
373 __os << __x._M_x[__i] << __space;
374 __os << __x._M_x[__n - 1];
381 template<class _UIntType, int __w, int __n, int __m, int __r,
382 _UIntType __a, int __u, int __s, _UIntType __b, int __t,
383 _UIntType __c, int __l,
384 typename _CharT, typename _Traits>
385 std::basic_istream<_CharT, _Traits>&
386 operator>>(std::basic_istream<_CharT, _Traits>& __is,
387 mersenne_twister<_UIntType, __w, __n, __m,
388 __r, __a, __u, __s, __b, __t, __c, __l>& __x)
390 typedef std::basic_istream<_CharT, _Traits> __istream_type;
391 typedef typename __istream_type::ios_base __ios_base;
393 const typename __ios_base::fmtflags __flags = __is.flags();
394 __is.flags(__ios_base::dec | __ios_base::skipws);
396 for (int __i = 0; __i < __n; ++__i)
397 __is >> __x._M_x[__i];
404 template<typename _IntType, _IntType __m, int __s, int __r>
406 subtract_with_carry<_IntType, __m, __s, __r>::modulus;
408 template<typename _IntType, _IntType __m, int __s, int __r>
410 subtract_with_carry<_IntType, __m, __s, __r>::long_lag;
412 template<typename _IntType, _IntType __m, int __s, int __r>
414 subtract_with_carry<_IntType, __m, __s, __r>::short_lag;
416 template<typename _IntType, _IntType __m, int __s, int __r>
418 subtract_with_carry<_IntType, __m, __s, __r>::
419 seed(unsigned long __value)
424 std::tr1::linear_congruential<unsigned long, 40014, 0, 2147483563>
427 for (int __i = 0; __i < long_lag; ++__i)
428 _M_x[__i] = __detail::__mod<_UIntType, 1, 0, modulus>(__lcg());
430 _M_carry = (_M_x[long_lag - 1] == 0) ? 1 : 0;
434 template<typename _IntType, _IntType __m, int __s, int __r>
437 subtract_with_carry<_IntType, __m, __s, __r>::
438 seed(_Gen& __gen, false_type)
440 const int __n = (std::numeric_limits<_UIntType>::digits + 31) / 32;
442 for (int __i = 0; __i < long_lag; ++__i)
445 _UIntType __factor = 1;
446 for (int __j = 0; __j < __n; ++__j)
448 __tmp += __detail::__mod<__detail::_UInt32Type, 1, 0, 0>
449 (__gen()) * __factor;
450 __factor *= __detail::_Shift<_UIntType, 32>::__value;
452 _M_x[__i] = __detail::__mod<_UIntType, 1, 0, modulus>(__tmp);
454 _M_carry = (_M_x[long_lag - 1] == 0) ? 1 : 0;
458 template<typename _IntType, _IntType __m, int __s, int __r>
459 typename subtract_with_carry<_IntType, __m, __s, __r>::result_type
460 subtract_with_carry<_IntType, __m, __s, __r>::
463 // Derive short lag index from current index.
464 int __ps = _M_p - short_lag;
468 // Calculate new x(i) without overflow or division.
469 // NB: Thanks to the requirements for _IntType, _M_x[_M_p] + _M_carry
472 if (_M_x[__ps] >= _M_x[_M_p] + _M_carry)
474 __xi = _M_x[__ps] - _M_x[_M_p] - _M_carry;
479 __xi = modulus - _M_x[_M_p] - _M_carry + _M_x[__ps];
484 // Adjust current index to loop around in ring buffer.
485 if (++_M_p >= long_lag)
491 template<typename _IntType, _IntType __m, int __s, int __r,
492 typename _CharT, typename _Traits>
493 std::basic_ostream<_CharT, _Traits>&
494 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
495 const subtract_with_carry<_IntType, __m, __s, __r>& __x)
497 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
498 typedef typename __ostream_type::ios_base __ios_base;
500 const typename __ios_base::fmtflags __flags = __os.flags();
501 const _CharT __fill = __os.fill();
502 const _CharT __space = __os.widen(' ');
503 __os.flags(__ios_base::dec | __ios_base::fixed | __ios_base::left);
506 for (int __i = 0; __i < __r; ++__i)
507 __os << __x._M_x[__i] << __space;
508 __os << __x._M_carry;
515 template<typename _IntType, _IntType __m, int __s, int __r,
516 typename _CharT, typename _Traits>
517 std::basic_istream<_CharT, _Traits>&
518 operator>>(std::basic_istream<_CharT, _Traits>& __is,
519 subtract_with_carry<_IntType, __m, __s, __r>& __x)
521 typedef std::basic_ostream<_CharT, _Traits> __istream_type;
522 typedef typename __istream_type::ios_base __ios_base;
524 const typename __ios_base::fmtflags __flags = __is.flags();
525 __is.flags(__ios_base::dec | __ios_base::skipws);
527 for (int __i = 0; __i < __r; ++__i)
528 __is >> __x._M_x[__i];
529 __is >> __x._M_carry;
536 template<typename _RealType, int __w, int __s, int __r>
538 subtract_with_carry_01<_RealType, __w, __s, __r>::word_size;
540 template<typename _RealType, int __w, int __s, int __r>
542 subtract_with_carry_01<_RealType, __w, __s, __r>::long_lag;
544 template<typename _RealType, int __w, int __s, int __r>
546 subtract_with_carry_01<_RealType, __w, __s, __r>::short_lag;
548 template<typename _RealType, int __w, int __s, int __r>
550 subtract_with_carry_01<_RealType, __w, __s, __r>::
551 _M_initialize_npows()
553 for (int __j = 0; __j < __n; ++__j)
554 #if _GLIBCXX_USE_C99_MATH_TR1
555 _M_npows[__j] = std::tr1::ldexp(_RealType(1), -__w + __j * 32);
557 _M_npows[__j] = std::pow(_RealType(2), -__w + __j * 32);
561 template<typename _RealType, int __w, int __s, int __r>
563 subtract_with_carry_01<_RealType, __w, __s, __r>::
564 seed(unsigned long __value)
569 // _GLIBCXX_RESOLVE_LIB_DEFECTS
570 // 512. Seeding subtract_with_carry_01 from a single unsigned long.
571 std::tr1::linear_congruential<unsigned long, 40014, 0, 2147483563>
577 template<typename _RealType, int __w, int __s, int __r>
580 subtract_with_carry_01<_RealType, __w, __s, __r>::
581 seed(_Gen& __gen, false_type)
583 for (int __i = 0; __i < long_lag; ++__i)
585 for (int __j = 0; __j < __n - 1; ++__j)
586 _M_x[__i][__j] = __detail::__mod<_UInt32Type, 1, 0, 0>(__gen());
587 _M_x[__i][__n - 1] = __detail::__mod<_UInt32Type, 1, 0,
588 __detail::_Shift<_UInt32Type, __w % 32>::__value>(__gen());
592 for (int __j = 0; __j < __n; ++__j)
593 if (_M_x[long_lag - 1][__j] != 0)
602 template<typename _RealType, int __w, int __s, int __r>
603 typename subtract_with_carry_01<_RealType, __w, __s, __r>::result_type
604 subtract_with_carry_01<_RealType, __w, __s, __r>::
607 // Derive short lag index from current index.
608 int __ps = _M_p - short_lag;
612 _UInt32Type __new_carry;
613 for (int __j = 0; __j < __n - 1; ++__j)
615 if (_M_x[__ps][__j] > _M_x[_M_p][__j]
616 || (_M_x[__ps][__j] == _M_x[_M_p][__j] && _M_carry == 0))
621 _M_x[_M_p][__j] = _M_x[__ps][__j] - _M_x[_M_p][__j] - _M_carry;
622 _M_carry = __new_carry;
625 if (_M_x[__ps][__n - 1] > _M_x[_M_p][__n - 1]
626 || (_M_x[__ps][__n - 1] == _M_x[_M_p][__n - 1] && _M_carry == 0))
631 _M_x[_M_p][__n - 1] = __detail::__mod<_UInt32Type, 1, 0,
632 __detail::_Shift<_UInt32Type, __w % 32>::__value>
633 (_M_x[__ps][__n - 1] - _M_x[_M_p][__n - 1] - _M_carry);
634 _M_carry = __new_carry;
636 result_type __ret = 0.0;
637 for (int __j = 0; __j < __n; ++__j)
638 __ret += _M_x[_M_p][__j] * _M_npows[__j];
640 // Adjust current index to loop around in ring buffer.
641 if (++_M_p >= long_lag)
647 template<typename _RealType, int __w, int __s, int __r,
648 typename _CharT, typename _Traits>
649 std::basic_ostream<_CharT, _Traits>&
650 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
651 const subtract_with_carry_01<_RealType, __w, __s, __r>& __x)
653 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
654 typedef typename __ostream_type::ios_base __ios_base;
656 const typename __ios_base::fmtflags __flags = __os.flags();
657 const _CharT __fill = __os.fill();
658 const _CharT __space = __os.widen(' ');
659 __os.flags(__ios_base::dec | __ios_base::fixed | __ios_base::left);
662 for (int __i = 0; __i < __r; ++__i)
663 for (int __j = 0; __j < __x.__n; ++__j)
664 __os << __x._M_x[__i][__j] << __space;
665 __os << __x._M_carry;
672 template<typename _RealType, int __w, int __s, int __r,
673 typename _CharT, typename _Traits>
674 std::basic_istream<_CharT, _Traits>&
675 operator>>(std::basic_istream<_CharT, _Traits>& __is,
676 subtract_with_carry_01<_RealType, __w, __s, __r>& __x)
678 typedef std::basic_istream<_CharT, _Traits> __istream_type;
679 typedef typename __istream_type::ios_base __ios_base;
681 const typename __ios_base::fmtflags __flags = __is.flags();
682 __is.flags(__ios_base::dec | __ios_base::skipws);
684 for (int __i = 0; __i < __r; ++__i)
685 for (int __j = 0; __j < __x.__n; ++__j)
686 __is >> __x._M_x[__i][__j];
687 __is >> __x._M_carry;
693 template<class _UniformRandomNumberGenerator, int __p, int __r>
695 discard_block<_UniformRandomNumberGenerator, __p, __r>::block_size;
697 template<class _UniformRandomNumberGenerator, int __p, int __r>
699 discard_block<_UniformRandomNumberGenerator, __p, __r>::used_block;
701 template<class _UniformRandomNumberGenerator, int __p, int __r>
702 typename discard_block<_UniformRandomNumberGenerator,
703 __p, __r>::result_type
704 discard_block<_UniformRandomNumberGenerator, __p, __r>::
707 if (_M_n >= used_block)
709 while (_M_n < block_size)
720 template<class _UniformRandomNumberGenerator, int __p, int __r,
721 typename _CharT, typename _Traits>
722 std::basic_ostream<_CharT, _Traits>&
723 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
724 const discard_block<_UniformRandomNumberGenerator,
727 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
728 typedef typename __ostream_type::ios_base __ios_base;
730 const typename __ios_base::fmtflags __flags = __os.flags();
731 const _CharT __fill = __os.fill();
732 const _CharT __space = __os.widen(' ');
733 __os.flags(__ios_base::dec | __ios_base::fixed
737 __os << __x._M_b << __space << __x._M_n;
744 template<class _UniformRandomNumberGenerator, int __p, int __r,
745 typename _CharT, typename _Traits>
746 std::basic_istream<_CharT, _Traits>&
747 operator>>(std::basic_istream<_CharT, _Traits>& __is,
748 discard_block<_UniformRandomNumberGenerator, __p, __r>& __x)
750 typedef std::basic_istream<_CharT, _Traits> __istream_type;
751 typedef typename __istream_type::ios_base __ios_base;
753 const typename __ios_base::fmtflags __flags = __is.flags();
754 __is.flags(__ios_base::dec | __ios_base::skipws);
756 __is >> __x._M_b >> __x._M_n;
763 template<class _UniformRandomNumberGenerator1, int __s1,
764 class _UniformRandomNumberGenerator2, int __s2>
766 xor_combine<_UniformRandomNumberGenerator1, __s1,
767 _UniformRandomNumberGenerator2, __s2>::shift1;
769 template<class _UniformRandomNumberGenerator1, int __s1,
770 class _UniformRandomNumberGenerator2, int __s2>
772 xor_combine<_UniformRandomNumberGenerator1, __s1,
773 _UniformRandomNumberGenerator2, __s2>::shift2;
775 template<class _UniformRandomNumberGenerator1, int __s1,
776 class _UniformRandomNumberGenerator2, int __s2>
778 xor_combine<_UniformRandomNumberGenerator1, __s1,
779 _UniformRandomNumberGenerator2, __s2>::
782 const int __w = std::numeric_limits<result_type>::digits;
784 const result_type __m1 =
785 std::min(result_type(_M_b1.max() - _M_b1.min()),
786 __detail::_Shift<result_type, __w - __s1>::__value - 1);
788 const result_type __m2 =
789 std::min(result_type(_M_b2.max() - _M_b2.min()),
790 __detail::_Shift<result_type, __w - __s2>::__value - 1);
792 // NB: In TR1 s1 is not required to be >= s2.
794 _M_max = _M_initialize_max_aux(__m2, __m1, __s2 - __s1) << __s1;
796 _M_max = _M_initialize_max_aux(__m1, __m2, __s1 - __s2) << __s2;
799 template<class _UniformRandomNumberGenerator1, int __s1,
800 class _UniformRandomNumberGenerator2, int __s2>
801 typename xor_combine<_UniformRandomNumberGenerator1, __s1,
802 _UniformRandomNumberGenerator2, __s2>::result_type
803 xor_combine<_UniformRandomNumberGenerator1, __s1,
804 _UniformRandomNumberGenerator2, __s2>::
805 _M_initialize_max_aux(result_type __a, result_type __b, int __d)
807 const result_type __two2d = result_type(1) << __d;
808 const result_type __c = __a * __two2d;
810 if (__a == 0 || __b < __two2d)
813 const result_type __t = std::max(__c, __b);
814 const result_type __u = std::min(__c, __b);
816 result_type __ub = __u;
818 for (__p = 0; __ub != 1; __ub >>= 1)
821 const result_type __two2p = result_type(1) << __p;
822 const result_type __k = __t / __two2p;
825 return (__k + 1) * __two2p - 1;
828 return (__k + 1) * __two2p + _M_initialize_max_aux((__t % __two2p)
832 return (__k + 1) * __two2p + _M_initialize_max_aux((__u % __two2p)
837 template<class _UniformRandomNumberGenerator1, int __s1,
838 class _UniformRandomNumberGenerator2, int __s2,
839 typename _CharT, typename _Traits>
840 std::basic_ostream<_CharT, _Traits>&
841 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
842 const xor_combine<_UniformRandomNumberGenerator1, __s1,
843 _UniformRandomNumberGenerator2, __s2>& __x)
845 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
846 typedef typename __ostream_type::ios_base __ios_base;
848 const typename __ios_base::fmtflags __flags = __os.flags();
849 const _CharT __fill = __os.fill();
850 const _CharT __space = __os.widen(' ');
851 __os.flags(__ios_base::dec | __ios_base::fixed | __ios_base::left);
854 __os << __x.base1() << __space << __x.base2();
861 template<class _UniformRandomNumberGenerator1, int __s1,
862 class _UniformRandomNumberGenerator2, int __s2,
863 typename _CharT, typename _Traits>
864 std::basic_istream<_CharT, _Traits>&
865 operator>>(std::basic_istream<_CharT, _Traits>& __is,
866 xor_combine<_UniformRandomNumberGenerator1, __s1,
867 _UniformRandomNumberGenerator2, __s2>& __x)
869 typedef std::basic_istream<_CharT, _Traits> __istream_type;
870 typedef typename __istream_type::ios_base __ios_base;
872 const typename __ios_base::fmtflags __flags = __is.flags();
873 __is.flags(__ios_base::skipws);
875 __is >> __x._M_b1 >> __x._M_b2;
882 template<typename _IntType>
883 template<typename _UniformRandomNumberGenerator>
884 typename uniform_int<_IntType>::result_type
885 uniform_int<_IntType>::
886 _M_call(_UniformRandomNumberGenerator& __urng,
887 result_type __min, result_type __max, true_type)
889 // XXX Must be fixed to work well for *arbitrary* __urng.max(),
890 // __urng.min(), __max, __min. Currently works fine only in the
891 // most common case __urng.max() - __urng.min() >= __max - __min,
892 // with __urng.max() > __urng.min() >= 0.
893 typedef typename __gnu_cxx::__add_unsigned<typename
894 _UniformRandomNumberGenerator::result_type>::__type __urntype;
895 typedef typename __gnu_cxx::__add_unsigned<result_type>::__type
897 typedef typename __gnu_cxx::__conditional_type<(sizeof(__urntype)
899 __urntype, __utype>::__type __uctype;
903 const __urntype __urnmin = __urng.min();
904 const __urntype __urnmax = __urng.max();
905 const __urntype __urnrange = __urnmax - __urnmin;
906 const __uctype __urange = __max - __min;
907 const __uctype __udenom = (__urnrange <= __urange
908 ? 1 : __urnrange / (__urange + 1));
910 __ret = (__urntype(__urng()) - __urnmin) / __udenom;
911 while (__ret > __max - __min);
913 return __ret + __min;
916 template<typename _IntType, typename _CharT, typename _Traits>
917 std::basic_ostream<_CharT, _Traits>&
918 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
919 const uniform_int<_IntType>& __x)
921 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
922 typedef typename __ostream_type::ios_base __ios_base;
924 const typename __ios_base::fmtflags __flags = __os.flags();
925 const _CharT __fill = __os.fill();
926 const _CharT __space = __os.widen(' ');
927 __os.flags(__ios_base::scientific | __ios_base::left);
930 __os << __x.min() << __space << __x.max();
937 template<typename _IntType, typename _CharT, typename _Traits>
938 std::basic_istream<_CharT, _Traits>&
939 operator>>(std::basic_istream<_CharT, _Traits>& __is,
940 uniform_int<_IntType>& __x)
942 typedef std::basic_istream<_CharT, _Traits> __istream_type;
943 typedef typename __istream_type::ios_base __ios_base;
945 const typename __ios_base::fmtflags __flags = __is.flags();
946 __is.flags(__ios_base::dec | __ios_base::skipws);
948 __is >> __x._M_min >> __x._M_max;
955 template<typename _CharT, typename _Traits>
956 std::basic_ostream<_CharT, _Traits>&
957 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
958 const bernoulli_distribution& __x)
960 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
961 typedef typename __ostream_type::ios_base __ios_base;
963 const typename __ios_base::fmtflags __flags = __os.flags();
964 const _CharT __fill = __os.fill();
965 const std::streamsize __precision = __os.precision();
966 __os.flags(__ios_base::scientific | __ios_base::left);
967 __os.fill(__os.widen(' '));
968 __os.precision(__gnu_cxx::__numeric_traits<double>::__max_digits10);
974 __os.precision(__precision);
979 template<typename _IntType, typename _RealType>
980 template<class _UniformRandomNumberGenerator>
981 typename geometric_distribution<_IntType, _RealType>::result_type
982 geometric_distribution<_IntType, _RealType>::
983 operator()(_UniformRandomNumberGenerator& __urng)
985 // About the epsilon thing see this thread:
986 // http://gcc.gnu.org/ml/gcc-patches/2006-10/msg00971.html
987 const _RealType __naf =
988 (1 - std::numeric_limits<_RealType>::epsilon()) / 2;
989 // The largest _RealType convertible to _IntType.
990 const _RealType __thr =
991 std::numeric_limits<_IntType>::max() + __naf;
995 __cand = std::ceil(std::log(__urng()) / _M_log_p);
996 while (__cand >= __thr);
998 return result_type(__cand + __naf);
1001 template<typename _IntType, typename _RealType,
1002 typename _CharT, typename _Traits>
1003 std::basic_ostream<_CharT, _Traits>&
1004 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1005 const geometric_distribution<_IntType, _RealType>& __x)
1007 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
1008 typedef typename __ostream_type::ios_base __ios_base;
1010 const typename __ios_base::fmtflags __flags = __os.flags();
1011 const _CharT __fill = __os.fill();
1012 const std::streamsize __precision = __os.precision();
1013 __os.flags(__ios_base::scientific | __ios_base::left);
1014 __os.fill(__os.widen(' '));
1015 __os.precision(__gnu_cxx::__numeric_traits<_RealType>::__max_digits10);
1019 __os.flags(__flags);
1021 __os.precision(__precision);
1026 template<typename _IntType, typename _RealType>
1028 poisson_distribution<_IntType, _RealType>::
1031 #if _GLIBCXX_USE_C99_MATH_TR1
1034 const _RealType __m = std::floor(_M_mean);
1035 _M_lm_thr = std::log(_M_mean);
1036 _M_lfm = std::tr1::lgamma(__m + 1);
1037 _M_sm = std::sqrt(__m);
1039 const _RealType __pi_4 = 0.7853981633974483096156608458198757L;
1040 const _RealType __dx = std::sqrt(2 * __m * std::log(32 * __m
1042 _M_d = std::tr1::round(std::max(_RealType(6),
1043 std::min(__m, __dx)));
1044 const _RealType __cx = 2 * __m + _M_d;
1045 _M_scx = std::sqrt(__cx / 2);
1048 _M_c2b = std::sqrt(__pi_4 * __cx) * std::exp(_M_1cx);
1049 _M_cb = 2 * __cx * std::exp(-_M_d * _M_1cx * (1 + _M_d / 2)) / _M_d;
1053 _M_lm_thr = std::exp(-_M_mean);
1057 * A rejection algorithm when mean >= 12 and a simple method based
1058 * upon the multiplication of uniform random variates otherwise.
1059 * NB: The former is available only if _GLIBCXX_USE_C99_MATH_TR1
1063 * Devroye, L. Non-Uniform Random Variates Generation. Springer-Verlag,
1064 * New York, 1986, Ch. X, Sects. 3.3 & 3.4 (+ Errata!).
1066 template<typename _IntType, typename _RealType>
1067 template<class _UniformRandomNumberGenerator>
1068 typename poisson_distribution<_IntType, _RealType>::result_type
1069 poisson_distribution<_IntType, _RealType>::
1070 operator()(_UniformRandomNumberGenerator& __urng)
1072 #if _GLIBCXX_USE_C99_MATH_TR1
1077 // See comments above...
1078 const _RealType __naf =
1079 (1 - std::numeric_limits<_RealType>::epsilon()) / 2;
1080 const _RealType __thr =
1081 std::numeric_limits<_IntType>::max() + __naf;
1083 const _RealType __m = std::floor(_M_mean);
1085 const _RealType __spi_2 = 1.2533141373155002512078826424055226L;
1086 const _RealType __c1 = _M_sm * __spi_2;
1087 const _RealType __c2 = _M_c2b + __c1;
1088 const _RealType __c3 = __c2 + 1;
1089 const _RealType __c4 = __c3 + 1;
1091 const _RealType __e178 = 1.0129030479320018583185514777512983L;
1092 const _RealType __c5 = __c4 + __e178;
1093 const _RealType __c = _M_cb + __c5;
1094 const _RealType __2cx = 2 * (2 * __m + _M_d);
1096 bool __reject = true;
1099 const _RealType __u = __c * __urng();
1100 const _RealType __e = -std::log(__urng());
1102 _RealType __w = 0.0;
1106 const _RealType __n = _M_nd(__urng);
1107 const _RealType __y = -std::abs(__n) * _M_sm - 1;
1108 __x = std::floor(__y);
1109 __w = -__n * __n / 2;
1113 else if (__u <= __c2)
1115 const _RealType __n = _M_nd(__urng);
1116 const _RealType __y = 1 + std::abs(__n) * _M_scx;
1117 __x = std::ceil(__y);
1118 __w = __y * (2 - __y) * _M_1cx;
1122 else if (__u <= __c3)
1123 // NB: This case not in the book, nor in the Errata,
1124 // but should be ok...
1126 else if (__u <= __c4)
1128 else if (__u <= __c5)
1132 const _RealType __v = -std::log(__urng());
1133 const _RealType __y = _M_d + __v * __2cx / _M_d;
1134 __x = std::ceil(__y);
1135 __w = -_M_d * _M_1cx * (1 + __y / 2);
1138 __reject = (__w - __e - __x * _M_lm_thr
1139 > _M_lfm - std::tr1::lgamma(__x + __m + 1));
1141 __reject |= __x + __m >= __thr;
1145 return result_type(__x + __m + __naf);
1151 _RealType __prod = 1.0;
1158 while (__prod > _M_lm_thr);
1164 template<typename _IntType, typename _RealType,
1165 typename _CharT, typename _Traits>
1166 std::basic_ostream<_CharT, _Traits>&
1167 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1168 const poisson_distribution<_IntType, _RealType>& __x)
1170 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
1171 typedef typename __ostream_type::ios_base __ios_base;
1173 const typename __ios_base::fmtflags __flags = __os.flags();
1174 const _CharT __fill = __os.fill();
1175 const std::streamsize __precision = __os.precision();
1176 const _CharT __space = __os.widen(' ');
1177 __os.flags(__ios_base::scientific | __ios_base::left);
1179 __os.precision(__gnu_cxx::__numeric_traits<_RealType>::__max_digits10);
1181 __os << __x.mean() << __space << __x._M_nd;
1183 __os.flags(__flags);
1185 __os.precision(__precision);
1189 template<typename _IntType, typename _RealType,
1190 typename _CharT, typename _Traits>
1191 std::basic_istream<_CharT, _Traits>&
1192 operator>>(std::basic_istream<_CharT, _Traits>& __is,
1193 poisson_distribution<_IntType, _RealType>& __x)
1195 typedef std::basic_istream<_CharT, _Traits> __istream_type;
1196 typedef typename __istream_type::ios_base __ios_base;
1198 const typename __ios_base::fmtflags __flags = __is.flags();
1199 __is.flags(__ios_base::skipws);
1201 __is >> __x._M_mean >> __x._M_nd;
1202 __x._M_initialize();
1204 __is.flags(__flags);
1209 template<typename _IntType, typename _RealType>
1211 binomial_distribution<_IntType, _RealType>::
1214 const _RealType __p12 = _M_p <= 0.5 ? _M_p : 1.0 - _M_p;
1218 #if _GLIBCXX_USE_C99_MATH_TR1
1219 if (_M_t * __p12 >= 8)
1222 const _RealType __np = std::floor(_M_t * __p12);
1223 const _RealType __pa = __np / _M_t;
1224 const _RealType __1p = 1 - __pa;
1226 const _RealType __pi_4 = 0.7853981633974483096156608458198757L;
1227 const _RealType __d1x =
1228 std::sqrt(__np * __1p * std::log(32 * __np
1229 / (81 * __pi_4 * __1p)));
1230 _M_d1 = std::tr1::round(std::max(_RealType(1), __d1x));
1231 const _RealType __d2x =
1232 std::sqrt(__np * __1p * std::log(32 * _M_t * __1p
1233 / (__pi_4 * __pa)));
1234 _M_d2 = std::tr1::round(std::max(_RealType(1), __d2x));
1237 const _RealType __spi_2 = 1.2533141373155002512078826424055226L;
1238 _M_s1 = std::sqrt(__np * __1p) * (1 + _M_d1 / (4 * __np));
1239 _M_s2 = std::sqrt(__np * __1p) * (1 + _M_d2 / (4 * _M_t * __1p));
1240 _M_c = 2 * _M_d1 / __np;
1241 _M_a1 = std::exp(_M_c) * _M_s1 * __spi_2;
1242 const _RealType __a12 = _M_a1 + _M_s2 * __spi_2;
1243 const _RealType __s1s = _M_s1 * _M_s1;
1244 _M_a123 = __a12 + (std::exp(_M_d1 / (_M_t * __1p))
1246 * std::exp(-_M_d1 * _M_d1 / (2 * __s1s)));
1247 const _RealType __s2s = _M_s2 * _M_s2;
1248 _M_s = (_M_a123 + 2 * __s2s / _M_d2
1249 * std::exp(-_M_d2 * _M_d2 / (2 * __s2s)));
1250 _M_lf = (std::tr1::lgamma(__np + 1)
1251 + std::tr1::lgamma(_M_t - __np + 1));
1252 _M_lp1p = std::log(__pa / __1p);
1254 _M_q = -std::log(1 - (__p12 - __pa) / __1p);
1258 _M_q = -std::log(1 - __p12);
1261 template<typename _IntType, typename _RealType>
1262 template<class _UniformRandomNumberGenerator>
1263 typename binomial_distribution<_IntType, _RealType>::result_type
1264 binomial_distribution<_IntType, _RealType>::
1265 _M_waiting(_UniformRandomNumberGenerator& __urng, _IntType __t)
1268 _RealType __sum = 0;
1272 const _RealType __e = -std::log(__urng());
1273 __sum += __e / (__t - __x);
1276 while (__sum <= _M_q);
1282 * A rejection algorithm when t * p >= 8 and a simple waiting time
1283 * method - the second in the referenced book - otherwise.
1284 * NB: The former is available only if _GLIBCXX_USE_C99_MATH_TR1
1288 * Devroye, L. Non-Uniform Random Variates Generation. Springer-Verlag,
1289 * New York, 1986, Ch. X, Sect. 4 (+ Errata!).
1291 template<typename _IntType, typename _RealType>
1292 template<class _UniformRandomNumberGenerator>
1293 typename binomial_distribution<_IntType, _RealType>::result_type
1294 binomial_distribution<_IntType, _RealType>::
1295 operator()(_UniformRandomNumberGenerator& __urng)
1298 const _RealType __p12 = _M_p <= 0.5 ? _M_p : 1.0 - _M_p;
1300 #if _GLIBCXX_USE_C99_MATH_TR1
1305 // See comments above...
1306 const _RealType __naf =
1307 (1 - std::numeric_limits<_RealType>::epsilon()) / 2;
1308 const _RealType __thr =
1309 std::numeric_limits<_IntType>::max() + __naf;
1311 const _RealType __np = std::floor(_M_t * __p12);
1312 const _RealType __pa = __np / _M_t;
1315 const _RealType __spi_2 = 1.2533141373155002512078826424055226L;
1316 const _RealType __a1 = _M_a1;
1317 const _RealType __a12 = __a1 + _M_s2 * __spi_2;
1318 const _RealType __a123 = _M_a123;
1319 const _RealType __s1s = _M_s1 * _M_s1;
1320 const _RealType __s2s = _M_s2 * _M_s2;
1325 const _RealType __u = _M_s * __urng();
1331 const _RealType __n = _M_nd(__urng);
1332 const _RealType __y = _M_s1 * std::abs(__n);
1333 __reject = __y >= _M_d1;
1336 const _RealType __e = -std::log(__urng());
1337 __x = std::floor(__y);
1338 __v = -__e - __n * __n / 2 + _M_c;
1341 else if (__u <= __a12)
1343 const _RealType __n = _M_nd(__urng);
1344 const _RealType __y = _M_s2 * std::abs(__n);
1345 __reject = __y >= _M_d2;
1348 const _RealType __e = -std::log(__urng());
1349 __x = std::floor(-__y);
1350 __v = -__e - __n * __n / 2;
1353 else if (__u <= __a123)
1355 const _RealType __e1 = -std::log(__urng());
1356 const _RealType __e2 = -std::log(__urng());
1358 const _RealType __y = _M_d1 + 2 * __s1s * __e1 / _M_d1;
1359 __x = std::floor(__y);
1360 __v = (-__e2 + _M_d1 * (1 / (_M_t - __np)
1361 -__y / (2 * __s1s)));
1366 const _RealType __e1 = -std::log(__urng());
1367 const _RealType __e2 = -std::log(__urng());
1369 const _RealType __y = _M_d2 + 2 * __s2s * __e1 / _M_d2;
1370 __x = std::floor(-__y);
1371 __v = -__e2 - _M_d2 * __y / (2 * __s2s);
1375 __reject = __reject || __x < -__np || __x > _M_t - __np;
1378 const _RealType __lfx =
1379 std::tr1::lgamma(__np + __x + 1)
1380 + std::tr1::lgamma(_M_t - (__np + __x) + 1);
1381 __reject = __v > _M_lf - __lfx + __x * _M_lp1p;
1384 __reject |= __x + __np >= __thr;
1388 __x += __np + __naf;
1390 const _IntType __z = _M_waiting(__urng, _M_t - _IntType(__x));
1391 __ret = _IntType(__x) + __z;
1395 __ret = _M_waiting(__urng, _M_t);
1398 __ret = _M_t - __ret;
1402 template<typename _IntType, typename _RealType,
1403 typename _CharT, typename _Traits>
1404 std::basic_ostream<_CharT, _Traits>&
1405 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1406 const binomial_distribution<_IntType, _RealType>& __x)
1408 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
1409 typedef typename __ostream_type::ios_base __ios_base;
1411 const typename __ios_base::fmtflags __flags = __os.flags();
1412 const _CharT __fill = __os.fill();
1413 const std::streamsize __precision = __os.precision();
1414 const _CharT __space = __os.widen(' ');
1415 __os.flags(__ios_base::scientific | __ios_base::left);
1417 __os.precision(__gnu_cxx::__numeric_traits<_RealType>::__max_digits10);
1419 __os << __x.t() << __space << __x.p()
1420 << __space << __x._M_nd;
1422 __os.flags(__flags);
1424 __os.precision(__precision);
1428 template<typename _IntType, typename _RealType,
1429 typename _CharT, typename _Traits>
1430 std::basic_istream<_CharT, _Traits>&
1431 operator>>(std::basic_istream<_CharT, _Traits>& __is,
1432 binomial_distribution<_IntType, _RealType>& __x)
1434 typedef std::basic_istream<_CharT, _Traits> __istream_type;
1435 typedef typename __istream_type::ios_base __ios_base;
1437 const typename __ios_base::fmtflags __flags = __is.flags();
1438 __is.flags(__ios_base::dec | __ios_base::skipws);
1440 __is >> __x._M_t >> __x._M_p >> __x._M_nd;
1441 __x._M_initialize();
1443 __is.flags(__flags);
1448 template<typename _RealType, typename _CharT, typename _Traits>
1449 std::basic_ostream<_CharT, _Traits>&
1450 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1451 const uniform_real<_RealType>& __x)
1453 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
1454 typedef typename __ostream_type::ios_base __ios_base;
1456 const typename __ios_base::fmtflags __flags = __os.flags();
1457 const _CharT __fill = __os.fill();
1458 const std::streamsize __precision = __os.precision();
1459 const _CharT __space = __os.widen(' ');
1460 __os.flags(__ios_base::scientific | __ios_base::left);
1462 __os.precision(__gnu_cxx::__numeric_traits<_RealType>::__max_digits10);
1464 __os << __x.min() << __space << __x.max();
1466 __os.flags(__flags);
1468 __os.precision(__precision);
1472 template<typename _RealType, typename _CharT, typename _Traits>
1473 std::basic_istream<_CharT, _Traits>&
1474 operator>>(std::basic_istream<_CharT, _Traits>& __is,
1475 uniform_real<_RealType>& __x)
1477 typedef std::basic_istream<_CharT, _Traits> __istream_type;
1478 typedef typename __istream_type::ios_base __ios_base;
1480 const typename __ios_base::fmtflags __flags = __is.flags();
1481 __is.flags(__ios_base::skipws);
1483 __is >> __x._M_min >> __x._M_max;
1485 __is.flags(__flags);
1490 template<typename _RealType, typename _CharT, typename _Traits>
1491 std::basic_ostream<_CharT, _Traits>&
1492 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1493 const exponential_distribution<_RealType>& __x)
1495 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
1496 typedef typename __ostream_type::ios_base __ios_base;
1498 const typename __ios_base::fmtflags __flags = __os.flags();
1499 const _CharT __fill = __os.fill();
1500 const std::streamsize __precision = __os.precision();
1501 __os.flags(__ios_base::scientific | __ios_base::left);
1502 __os.fill(__os.widen(' '));
1503 __os.precision(__gnu_cxx::__numeric_traits<_RealType>::__max_digits10);
1505 __os << __x.lambda();
1507 __os.flags(__flags);
1509 __os.precision(__precision);
1515 * Polar method due to Marsaglia.
1517 * Devroye, L. Non-Uniform Random Variates Generation. Springer-Verlag,
1518 * New York, 1986, Ch. V, Sect. 4.4.
1520 template<typename _RealType>
1521 template<class _UniformRandomNumberGenerator>
1522 typename normal_distribution<_RealType>::result_type
1523 normal_distribution<_RealType>::
1524 operator()(_UniformRandomNumberGenerator& __urng)
1528 if (_M_saved_available)
1530 _M_saved_available = false;
1535 result_type __x, __y, __r2;
1538 __x = result_type(2.0) * __urng() - 1.0;
1539 __y = result_type(2.0) * __urng() - 1.0;
1540 __r2 = __x * __x + __y * __y;
1542 while (__r2 > 1.0 || __r2 == 0.0);
1544 const result_type __mult = std::sqrt(-2 * std::log(__r2) / __r2);
1545 _M_saved = __x * __mult;
1546 _M_saved_available = true;
1547 __ret = __y * __mult;
1550 __ret = __ret * _M_sigma + _M_mean;
1554 template<typename _RealType, typename _CharT, typename _Traits>
1555 std::basic_ostream<_CharT, _Traits>&
1556 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1557 const normal_distribution<_RealType>& __x)
1559 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
1560 typedef typename __ostream_type::ios_base __ios_base;
1562 const typename __ios_base::fmtflags __flags = __os.flags();
1563 const _CharT __fill = __os.fill();
1564 const std::streamsize __precision = __os.precision();
1565 const _CharT __space = __os.widen(' ');
1566 __os.flags(__ios_base::scientific | __ios_base::left);
1568 __os.precision(__gnu_cxx::__numeric_traits<_RealType>::__max_digits10);
1570 __os << __x._M_saved_available << __space
1571 << __x.mean() << __space
1573 if (__x._M_saved_available)
1574 __os << __space << __x._M_saved;
1576 __os.flags(__flags);
1578 __os.precision(__precision);
1582 template<typename _RealType, typename _CharT, typename _Traits>
1583 std::basic_istream<_CharT, _Traits>&
1584 operator>>(std::basic_istream<_CharT, _Traits>& __is,
1585 normal_distribution<_RealType>& __x)
1587 typedef std::basic_istream<_CharT, _Traits> __istream_type;
1588 typedef typename __istream_type::ios_base __ios_base;
1590 const typename __ios_base::fmtflags __flags = __is.flags();
1591 __is.flags(__ios_base::dec | __ios_base::skipws);
1593 __is >> __x._M_saved_available >> __x._M_mean
1595 if (__x._M_saved_available)
1596 __is >> __x._M_saved;
1598 __is.flags(__flags);
1603 template<typename _RealType>
1605 gamma_distribution<_RealType>::
1609 _M_l_d = std::sqrt(2 * _M_alpha - 1);
1611 _M_l_d = (std::pow(_M_alpha, _M_alpha / (1 - _M_alpha))
1616 * Cheng's rejection algorithm GB for alpha >= 1 and a modification
1617 * of Vaduva's rejection from Weibull algorithm due to Devroye for
1621 * Cheng, R. C. The Generation of Gamma Random Variables with Non-integral
1622 * Shape Parameter. Applied Statistics, 26, 71-75, 1977.
1624 * Vaduva, I. Computer Generation of Gamma Gandom Variables by Rejection
1625 * and Composition Procedures. Math. Operationsforschung and Statistik,
1626 * Series in Statistics, 8, 545-576, 1977.
1628 * Devroye, L. Non-Uniform Random Variates Generation. Springer-Verlag,
1629 * New York, 1986, Ch. IX, Sect. 3.4 (+ Errata!).
1631 template<typename _RealType>
1632 template<class _UniformRandomNumberGenerator>
1633 typename gamma_distribution<_RealType>::result_type
1634 gamma_distribution<_RealType>::
1635 operator()(_UniformRandomNumberGenerator& __urng)
1643 const result_type __b = _M_alpha
1644 - result_type(1.3862943611198906188344642429163531L);
1645 const result_type __c = _M_alpha + _M_l_d;
1646 const result_type __1l = 1 / _M_l_d;
1649 const result_type __k = 2.5040773967762740733732583523868748L;
1653 const result_type __u = __urng();
1654 const result_type __v = __urng();
1656 const result_type __y = __1l * std::log(__v / (1 - __v));
1657 __x = _M_alpha * std::exp(__y);
1659 const result_type __z = __u * __v * __v;
1660 const result_type __r = __b + __c * __y - __x;
1662 __reject = __r < result_type(4.5) * __z - __k;
1664 __reject = __r < std::log(__z);
1670 const result_type __c = 1 / _M_alpha;
1674 const result_type __z = -std::log(__urng());
1675 const result_type __e = -std::log(__urng());
1677 __x = std::pow(__z, __c);
1679 __reject = __z + __e < _M_l_d + __x;
1687 template<typename _RealType, typename _CharT, typename _Traits>
1688 std::basic_ostream<_CharT, _Traits>&
1689 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1690 const gamma_distribution<_RealType>& __x)
1692 typedef std::basic_ostream<_CharT, _Traits> __ostream_type;
1693 typedef typename __ostream_type::ios_base __ios_base;
1695 const typename __ios_base::fmtflags __flags = __os.flags();
1696 const _CharT __fill = __os.fill();
1697 const std::streamsize __precision = __os.precision();
1698 __os.flags(__ios_base::scientific | __ios_base::left);
1699 __os.fill(__os.widen(' '));
1700 __os.precision(__gnu_cxx::__numeric_traits<_RealType>::__max_digits10);
1702 __os << __x.alpha();
1704 __os.flags(__flags);
1706 __os.precision(__precision);