libcxx/include/__random/mersenne_twister_engine.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H
  10 #define _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H
  11
  12 #include <__algorithm/equal.h>
  13 #include <__algorithm/min.h>
  14 #include <__config>
  15 #include <__random/is_seed_sequence.h>
  16 #include <cstddef>
  17 #include <cstdint>
  18 #include <iosfwd>
  19 #include <limits>
  20
  21 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  22 #  pragma GCC system_header
  23 #endif
  24
  25 _LIBCPP_PUSH_MACROS
  26 #include <__undef_macros>
  27
  28 _LIBCPP_BEGIN_NAMESPACE_STD
  29
  30 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
  31           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
  32           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
  33 class _LIBCPP_TEMPLATE_VIS mersenne_twister_engine;
  34
  35 template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
  36           _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
  37           _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
  38 _LIBCPP_HIDE_FROM_ABI bool
  39 operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
  40                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
  41            const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
  42                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
  43
  44 template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
  45           _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
  46           _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
  47 _LIBCPP_INLINE_VISIBILITY
  48 bool
  49 operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
  50                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
  51            const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
  52                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
  53
  54 template <class _CharT, class _Traits,
  55           class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
  56           _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
  57           _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
  58 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
  59 operator<<(basic_ostream<_CharT, _Traits>& __os,
  60            const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
  61                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
  62
  63 template <class _CharT, class _Traits,
  64           class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
  65           _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
  66           _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
  67 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
  68 operator>>(basic_istream<_CharT, _Traits>& __is,
  69            mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
  70                                    _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
  71
  72 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
  73           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
  74           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
  75 class _LIBCPP_TEMPLATE_VIS mersenne_twister_engine
  76 {
  77 public:
  78     // types
  79     typedef _UIntType result_type;
  80
  81 private:
  82     result_type __x_[__n];
  83     size_t      __i_;
  84
  85     static_assert(  0 <  __m, "mersenne_twister_engine invalid parameters");
  86     static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");
  87     static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
  88     static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");
  89     static_assert(  2 <= __w, "mersenne_twister_engine invalid parameters");
  90     static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");
  91     static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");
  92     static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");
  93     static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");
  94     static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");
  95 public:
  96     static _LIBCPP_CONSTEXPR const result_type _Min = 0;
  97     static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
  98                                                       (result_type(1) << __w) - result_type(1);
  99     static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");
 100     static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");
 101     static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");
 102     static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");
 103     static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");
 104     static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");
 105
 106     // engine characteristics
 107     static _LIBCPP_CONSTEXPR const size_t word_size = __w;
 108     static _LIBCPP_CONSTEXPR const size_t state_size = __n;
 109     static _LIBCPP_CONSTEXPR const size_t shift_size = __m;
 110     static _LIBCPP_CONSTEXPR const size_t mask_bits = __r;
 111     static _LIBCPP_CONSTEXPR const result_type xor_mask = __a;
 112     static _LIBCPP_CONSTEXPR const size_t tempering_u = __u;
 113     static _LIBCPP_CONSTEXPR const result_type tempering_d = __d;
 114     static _LIBCPP_CONSTEXPR const size_t tempering_s = __s;
 115     static _LIBCPP_CONSTEXPR const result_type tempering_b = __b;
 116     static _LIBCPP_CONSTEXPR const size_t tempering_t = __t;
 117     static _LIBCPP_CONSTEXPR const result_type tempering_c = __c;
 118     static _LIBCPP_CONSTEXPR const size_t tempering_l = __l;
 119     static _LIBCPP_CONSTEXPR const result_type initialization_multiplier = __f;
 120     _LIBCPP_INLINE_VISIBILITY
 121     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
 122     _LIBCPP_INLINE_VISIBILITY
 123     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
 124     static _LIBCPP_CONSTEXPR const result_type default_seed = 5489u;
 125
 126     // constructors and seeding functions
 127 #ifndef _LIBCPP_CXX03_LANG
 128     _LIBCPP_INLINE_VISIBILITY
 129     mersenne_twister_engine() : mersenne_twister_engine(default_seed) {}
 130     _LIBCPP_INLINE_VISIBILITY
 131     explicit mersenne_twister_engine(result_type __sd) { seed(__sd); }
 132 #else
 133     _LIBCPP_INLINE_VISIBILITY
 134     explicit mersenne_twister_engine(result_type __sd = default_seed) {
 135       seed(__sd);
 136     }
 137 #endif
 138     template<class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value, int> = 0>
 139         _LIBCPP_INLINE_VISIBILITY
 140         explicit mersenne_twister_engine(_Sseq& __q)
 141         {seed(__q);}
 142     _LIBCPP_HIDE_FROM_ABI void seed(result_type __sd = default_seed);
 143     template<class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value, int> = 0>
 144         _LIBCPP_INLINE_VISIBILITY
 145         void
 146         seed(_Sseq& __q)
 147             {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
 148
 149     // generating functions
 150     _LIBCPP_HIDE_FROM_ABI result_type operator()();
 151     _LIBCPP_INLINE_VISIBILITY
 152     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
 153
 154     template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
 155               _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
 156               _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
 157     friend
 158     bool
 159     operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 160                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
 161                const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 162                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
 163
 164     template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
 165               _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
 166               _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
 167     friend
 168     bool
 169     operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 170                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
 171                const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 172                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
 173
 174     template <class _CharT, class _Traits,
 175               class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
 176               _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
 177               _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
 178     friend
 179     basic_ostream<_CharT, _Traits>&
 180     operator<<(basic_ostream<_CharT, _Traits>& __os,
 181                const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 182                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
 183
 184     template <class _CharT, class _Traits,
 185               class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
 186               _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
 187               _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
 188     friend
 189     basic_istream<_CharT, _Traits>&
 190     operator>>(basic_istream<_CharT, _Traits>& __is,
 191                mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 192                                        _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
 193 private:
 194
 195     template<class _Sseq>
 196     _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
 197     template<class _Sseq>
 198     _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
 199
 200     template <size_t __count, __enable_if_t<__count < __w, int> = 0>
 201         _LIBCPP_INLINE_VISIBILITY
 202         static
 203         result_type
 204         __lshift(result_type __x) {return (__x << __count) & _Max;}
 205
 206     template <size_t __count, __enable_if_t<(__count >= __w), int> = 0>
 207         _LIBCPP_INLINE_VISIBILITY
 208         static
 209         result_type
 210         __lshift(result_type) {return result_type(0);}
 211
 212     template <size_t __count, __enable_if_t<__count < _Dt, int> = 0>
 213         _LIBCPP_INLINE_VISIBILITY
 214         static
 215         result_type
 216         __rshift(result_type __x) {return __x >> __count;}
 217
 218     template <size_t __count, __enable_if_t<(__count >= _Dt), int> = 0>
 219         _LIBCPP_INLINE_VISIBILITY
 220         static
 221         result_type
 222         __rshift(result_type) {return result_type(0);}
 223 };
 224
 225 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 226           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 227           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 228     _LIBCPP_CONSTEXPR const size_t
 229     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::word_size;
 230
 231 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 232           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 233           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 234     _LIBCPP_CONSTEXPR const size_t
 235     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::state_size;
 236
 237 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 238           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 239           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 240     _LIBCPP_CONSTEXPR const size_t
 241     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::shift_size;
 242
 243 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 244           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 245           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 246     _LIBCPP_CONSTEXPR const size_t
 247     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::mask_bits;
 248
 249 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 250           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 251           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 252     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
 253     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::xor_mask;
 254
 255 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 256           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 257           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 258     _LIBCPP_CONSTEXPR const size_t
 259     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_u;
 260
 261 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 262           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 263           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 264     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
 265     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_d;
 266
 267 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 268           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 269           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 270     _LIBCPP_CONSTEXPR const size_t
 271     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_s;
 272
 273 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 274           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 275           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 276     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
 277     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_b;
 278
 279 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 280           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 281           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 282     _LIBCPP_CONSTEXPR const size_t
 283     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_t;
 284
 285 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 286           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 287           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 288     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
 289     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_c;
 290
 291 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 292           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 293           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 294     _LIBCPP_CONSTEXPR const size_t
 295     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_l;
 296
 297 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 298           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 299           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 300     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
 301     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::initialization_multiplier;
 302
 303 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 304           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 305           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 306     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
 307     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::default_seed;
 308
 309 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 310           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 311           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 312 void
 313 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
 314     __t, __c, __l, __f>::seed(result_type __sd)
 315     _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
 316 {   // __w >= 2
 317     __x_[0] = __sd & _Max;
 318     for (size_t __i = 1; __i < __n; ++__i)
 319         __x_[__i] = (__f * (__x_[__i-1] ^ __rshift<__w - 2>(__x_[__i-1])) + __i) & _Max;
 320     __i_ = 0;
 321 }
 322
 323 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 324           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 325           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 326 template<class _Sseq>
 327 void
 328 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
 329     __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 1>)
 330 {
 331     const unsigned __k = 1;
 332     uint32_t __ar[__n * __k];
 333     __q.generate(__ar, __ar + __n * __k);
 334     for (size_t __i = 0; __i < __n; ++__i)
 335         __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
 336     const result_type __mask = __r == _Dt ? result_type(~0) :
 337                                        (result_type(1) << __r) - result_type(1);
 338     __i_ = 0;
 339     if ((__x_[0] & ~__mask) == 0)
 340     {
 341         for (size_t __i = 1; __i < __n; ++__i)
 342             if (__x_[__i] != 0)
 343                 return;
 344         __x_[0] = result_type(1) << (__w - 1);
 345     }
 346 }
 347
 348 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 349           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 350           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 351 template<class _Sseq>
 352 void
 353 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
 354     __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 2>)
 355 {
 356     const unsigned __k = 2;
 357     uint32_t __ar[__n * __k];
 358     __q.generate(__ar, __ar + __n * __k);
 359     for (size_t __i = 0; __i < __n; ++__i)
 360         __x_[__i] = static_cast<result_type>(
 361             (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
 362     const result_type __mask = __r == _Dt ? result_type(~0) :
 363                                        (result_type(1) << __r) - result_type(1);
 364     __i_ = 0;
 365     if ((__x_[0] & ~__mask) == 0)
 366     {
 367         for (size_t __i = 1; __i < __n; ++__i)
 368             if (__x_[__i] != 0)
 369                 return;
 370         __x_[0] = result_type(1) << (__w - 1);
 371     }
 372 }
 373
 374 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
 375           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 376           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
 377 _UIntType
 378 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
 379     __t, __c, __l, __f>::operator()()
 380 {
 381     const size_t __j = (__i_ + 1) % __n;
 382     const result_type __mask = __r == _Dt ? result_type(~0) :
 383                                        (result_type(1) << __r) - result_type(1);
 384     const result_type __yp = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);
 385     const size_t __k = (__i_ + __m) % __n;
 386     __x_[__i_] = __x_[__k] ^ __rshift<1>(__yp) ^ (__a * (__yp & 1));
 387     result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d);
 388     __i_ = __j;
 389     __z ^= __lshift<__s>(__z) & __b;
 390     __z ^= __lshift<__t>(__z) & __c;
 391     return __z ^ __rshift<__l>(__z);
 392 }
 393
 394 template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
 395           _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
 396           _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
 397 _LIBCPP_HIDE_FROM_ABI bool
 398 operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 399                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
 400            const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 401                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __y)
 402 {
 403     if (__x.__i_ == __y.__i_)
 404         return _VSTD::equal(__x.__x_, __x.__x_ + _Np, __y.__x_);
 405     if (__x.__i_ == 0 || __y.__i_ == 0)
 406     {
 407         size_t __j = _VSTD::min(_Np - __x.__i_, _Np - __y.__i_);
 408         if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
 409                          __y.__x_ + __y.__i_))
 410             return false;
 411         if (__x.__i_ == 0)
 412             return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Np, __y.__x_);
 413         return _VSTD::equal(__x.__x_, __x.__x_ + (_Np - __j), __y.__x_ + __j);
 414     }
 415     if (__x.__i_ < __y.__i_)
 416     {
 417         size_t __j = _Np - __y.__i_;
 418         if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
 419                          __y.__x_ + __y.__i_))
 420             return false;
 421         if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Np,
 422                          __y.__x_))
 423             return false;
 424         return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
 425                            __y.__x_ + (_Np - (__x.__i_ + __j)));
 426     }
 427     size_t __j = _Np - __x.__i_;
 428     if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
 429                      __x.__x_ + __x.__i_))
 430         return false;
 431     if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Np,
 432                      __x.__x_))
 433         return false;
 434     return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
 435                        __x.__x_ + (_Np - (__y.__i_ + __j)));
 436 }
 437
 438 template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
 439           _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
 440           _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
 441 inline _LIBCPP_INLINE_VISIBILITY
 442 bool
 443 operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 444                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
 445            const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 446                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __y)
 447 {
 448     return !(__x == __y);
 449 }
 450
 451 template <class _CharT, class _Traits,
 452           class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
 453           _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
 454           _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
 455 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
 456 operator<<(basic_ostream<_CharT, _Traits>& __os,
 457            const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 458                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x)
 459 {
 460     __save_flags<_CharT, _Traits> __lx(__os);
 461     typedef basic_ostream<_CharT, _Traits> _Ostream;
 462     __os.flags(_Ostream::dec | _Ostream::left);
 463     _CharT __sp = __os.widen(' ');
 464     __os.fill(__sp);
 465     __os << __x.__x_[__x.__i_];
 466     for (size_t __j = __x.__i_ + 1; __j < _Np; ++__j)
 467         __os << __sp << __x.__x_[__j];
 468     for (size_t __j = 0; __j < __x.__i_; ++__j)
 469         __os << __sp << __x.__x_[__j];
 470     return __os;
 471 }
 472
 473 template <class _CharT, class _Traits,
 474           class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
 475           _UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
 476           _UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
 477 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
 478 operator>>(basic_istream<_CharT, _Traits>& __is,
 479            mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
 480                                    _Bp, _Tp, _Cp, _Lp, _Fp>& __x)
 481 {
 482     __save_flags<_CharT, _Traits> __lx(__is);
 483     typedef basic_istream<_CharT, _Traits> _Istream;
 484     __is.flags(_Istream::dec | _Istream::skipws);
 485     _UInt __t[_Np];
 486     for (size_t __i = 0; __i < _Np; ++__i)
 487         __is >> __t[__i];
 488     if (!__is.fail())
 489     {
 490         for (size_t __i = 0; __i < _Np; ++__i)
 491             __x.__x_[__i] = __t[__i];
 492         __x.__i_ = 0;
 493     }
 494     return __is;
 495 }
 496
 497 typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
 498                                 0x9908b0df, 11, 0xffffffff,
 499                                 7,  0x9d2c5680,
 500                                 15, 0xefc60000,
 501                                 18, 1812433253>                         mt19937;
 502 typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
 503                                 0xb5026f5aa96619e9ULL, 29, 0x5555555555555555ULL,
 504                                 17, 0x71d67fffeda60000ULL,
 505                                 37, 0xfff7eee000000000ULL,
 506                                 43, 6364136223846793005ULL>          mt19937_64;
 507
 508 _LIBCPP_END_NAMESPACE_STD
 509
 510 _LIBCPP_POP_MACROS
 511
 512 #endif // _LIBCPP___RANDOM_MERSENNE_TWISTER_ENGINE_H