libcxx/include/__random/linear_congruential_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_LINEAR_CONGRUENTIAL_ENGINE_H
  10 #define _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H
  11
  12 #include <__config>
  13 #include <__random/is_seed_sequence.h>
  14 #include <__type_traits/enable_if.h>
  15 #include <__type_traits/integral_constant.h>
  16 #include <__type_traits/is_unsigned.h>
  17 #include <cstdint>
  18 #include <iosfwd>
  19
  20 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  21 #  pragma GCC system_header
  22 #endif
  23
  24 _LIBCPP_PUSH_MACROS
  25 #include <__undef_macros>
  26
  27 _LIBCPP_BEGIN_NAMESPACE_STD
  28
  29 template <unsigned long long __a, unsigned long long __c,
  30           unsigned long long __m, unsigned long long _Mp,
  31           bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_Mp-__c)/__a),
  32           bool _OverflowOK = ((__m | (__m-1)) > __m), // m = 2^n
  33           bool _SchrageOK = (__a != 0 && __m != 0 && __m % __a <= __m / __a)> // r <= q
  34 struct __lce_alg_picker
  35 {
  36     static_assert(__a != 0 || __m != 0 || !_MightOverflow || _OverflowOK || _SchrageOK,
  37                   "The current values of a, c, and m cannot generate a number "
  38                   "within bounds of linear_congruential_engine.");
  39
  40     static _LIBCPP_CONSTEXPR const bool __use_schrage = _MightOverflow &&
  41                                                         !_OverflowOK &&
  42                                                         _SchrageOK;
  43 };
  44
  45 template <unsigned long long __a, unsigned long long __c,
  46           unsigned long long __m, unsigned long long _Mp,
  47           bool _UseSchrage = __lce_alg_picker<__a, __c, __m, _Mp>::__use_schrage>
  48 struct __lce_ta;
  49
  50 // 64
  51
  52 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
  53 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true>
  54 {
  55     typedef unsigned long long result_type;
  56     _LIBCPP_INLINE_VISIBILITY
  57     static result_type next(result_type __x)
  58     {
  59         // Schrage's algorithm
  60         const result_type __q = __m / __a;
  61         const result_type __r = __m % __a;
  62         const result_type __t0 = __a * (__x % __q);
  63         const result_type __t1 = __r * (__x / __q);
  64         __x = __t0 + (__t0 < __t1) * __m - __t1;
  65         __x += __c - (__x >= __m - __c) * __m;
  66         return __x;
  67     }
  68 };
  69
  70 template <unsigned long long __a, unsigned long long __m>
  71 struct __lce_ta<__a, 0, __m, (unsigned long long)(~0), true>
  72 {
  73     typedef unsigned long long result_type;
  74     _LIBCPP_INLINE_VISIBILITY
  75     static result_type next(result_type __x)
  76     {
  77         // Schrage's algorithm
  78         const result_type __q = __m / __a;
  79         const result_type __r = __m % __a;
  80         const result_type __t0 = __a * (__x % __q);
  81         const result_type __t1 = __r * (__x / __q);
  82         __x = __t0 + (__t0 < __t1) * __m - __t1;
  83         return __x;
  84     }
  85 };
  86
  87 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
  88 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false>
  89 {
  90     typedef unsigned long long result_type;
  91     _LIBCPP_INLINE_VISIBILITY
  92     static result_type next(result_type __x)
  93     {
  94         return (__a * __x + __c) % __m;
  95     }
  96 };
  97
  98 template <unsigned long long __a, unsigned long long __c>
  99 struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false>
 100 {
 101     typedef unsigned long long result_type;
 102     _LIBCPP_INLINE_VISIBILITY
 103     static result_type next(result_type __x)
 104     {
 105         return __a * __x + __c;
 106     }
 107 };
 108
 109 // 32
 110
 111 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
 112 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), true>
 113 {
 114     typedef unsigned result_type;
 115     _LIBCPP_INLINE_VISIBILITY
 116     static result_type next(result_type __x)
 117     {
 118         const result_type __a = static_cast<result_type>(_Ap);
 119         const result_type __c = static_cast<result_type>(_Cp);
 120         const result_type __m = static_cast<result_type>(_Mp);
 121         // Schrage's algorithm
 122         const result_type __q = __m / __a;
 123         const result_type __r = __m % __a;
 124         const result_type __t0 = __a * (__x % __q);
 125         const result_type __t1 = __r * (__x / __q);
 126         __x = __t0 + (__t0 < __t1) * __m - __t1;
 127         __x += __c - (__x >= __m - __c) * __m;
 128         return __x;
 129     }
 130 };
 131
 132 template <unsigned long long _Ap, unsigned long long _Mp>
 133 struct __lce_ta<_Ap, 0, _Mp, unsigned(~0), true>
 134 {
 135     typedef unsigned result_type;
 136     _LIBCPP_INLINE_VISIBILITY
 137     static result_type next(result_type __x)
 138     {
 139         const result_type __a = static_cast<result_type>(_Ap);
 140         const result_type __m = static_cast<result_type>(_Mp);
 141         // Schrage's algorithm
 142         const result_type __q = __m / __a;
 143         const result_type __r = __m % __a;
 144         const result_type __t0 = __a * (__x % __q);
 145         const result_type __t1 = __r * (__x / __q);
 146         __x = __t0 + (__t0 < __t1) * __m - __t1;
 147         return __x;
 148     }
 149 };
 150
 151 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
 152 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), false>
 153 {
 154     typedef unsigned result_type;
 155     _LIBCPP_INLINE_VISIBILITY
 156     static result_type next(result_type __x)
 157     {
 158         const result_type __a = static_cast<result_type>(_Ap);
 159         const result_type __c = static_cast<result_type>(_Cp);
 160         const result_type __m = static_cast<result_type>(_Mp);
 161         return (__a * __x + __c) % __m;
 162     }
 163 };
 164
 165 template <unsigned long long _Ap, unsigned long long _Cp>
 166 struct __lce_ta<_Ap, _Cp, 0, unsigned(~0), false>
 167 {
 168     typedef unsigned result_type;
 169     _LIBCPP_INLINE_VISIBILITY
 170     static result_type next(result_type __x)
 171     {
 172         const result_type __a = static_cast<result_type>(_Ap);
 173         const result_type __c = static_cast<result_type>(_Cp);
 174         return __a * __x + __c;
 175     }
 176 };
 177
 178 // 16
 179
 180 template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b>
 181 struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b>
 182 {
 183     typedef unsigned short result_type;
 184     _LIBCPP_INLINE_VISIBILITY
 185     static result_type next(result_type __x)
 186     {
 187         return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x));
 188     }
 189 };
 190
 191 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 192 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine;
 193
 194 template <class _CharT, class _Traits,
 195           class _Up, _Up _Ap, _Up _Cp, _Up _Np>
 196 _LIBCPP_INLINE_VISIBILITY
 197 basic_ostream<_CharT, _Traits>&
 198 operator<<(basic_ostream<_CharT, _Traits>& __os,
 199            const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
 200
 201 template <class _CharT, class _Traits,
 202           class _Up, _Up _Ap, _Up _Cp, _Up _Np>
 203 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
 204 operator>>(basic_istream<_CharT, _Traits>& __is,
 205            linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
 206
 207 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 208 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine
 209 {
 210 public:
 211     // types
 212     typedef _UIntType result_type;
 213
 214 private:
 215     result_type __x_;
 216
 217     static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(~0);
 218
 219     static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
 220     static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
 221     static_assert(is_unsigned<_UIntType>::value, "_UIntType must be unsigned type");
 222 public:
 223     static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u : 0u;
 224     static _LIBCPP_CONSTEXPR const result_type _Max = __m - _UIntType(1u);
 225     static_assert(_Min < _Max,           "linear_congruential_engine invalid parameters");
 226
 227     // engine characteristics
 228     static _LIBCPP_CONSTEXPR const result_type multiplier = __a;
 229     static _LIBCPP_CONSTEXPR const result_type increment = __c;
 230     static _LIBCPP_CONSTEXPR const result_type modulus = __m;
 231     _LIBCPP_INLINE_VISIBILITY
 232     static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
 233     _LIBCPP_INLINE_VISIBILITY
 234     static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
 235     static _LIBCPP_CONSTEXPR const result_type default_seed = 1u;
 236
 237     // constructors and seeding functions
 238 #ifndef _LIBCPP_CXX03_LANG
 239     _LIBCPP_INLINE_VISIBILITY
 240     linear_congruential_engine() : linear_congruential_engine(default_seed) {}
 241     _LIBCPP_INLINE_VISIBILITY
 242     explicit linear_congruential_engine(result_type __s) { seed(__s); }
 243 #else
 244     _LIBCPP_INLINE_VISIBILITY
 245     explicit linear_congruential_engine(result_type __s = default_seed) {
 246       seed(__s);
 247     }
 248 #endif
 249     template<class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0>
 250         _LIBCPP_INLINE_VISIBILITY
 251         explicit linear_congruential_engine(_Sseq& __q)
 252         {seed(__q);}
 253     _LIBCPP_INLINE_VISIBILITY
 254     void seed(result_type __s = default_seed)
 255         {seed(integral_constant<bool, __m == 0>(),
 256               integral_constant<bool, __c == 0>(), __s);}
 257     template<class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0>
 258         _LIBCPP_INLINE_VISIBILITY
 259         void
 260         seed(_Sseq& __q)
 261             {__seed(__q, integral_constant<unsigned,
 262                 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32
 263                              :  (__m > 0x100000000ull))>());}
 264
 265     // generating functions
 266     _LIBCPP_INLINE_VISIBILITY
 267     result_type operator()()
 268         {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_));}
 269     _LIBCPP_INLINE_VISIBILITY
 270     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
 271
 272     friend _LIBCPP_INLINE_VISIBILITY
 273     bool operator==(const linear_congruential_engine& __x,
 274                     const linear_congruential_engine& __y)
 275         {return __x.__x_ == __y.__x_;}
 276     friend _LIBCPP_INLINE_VISIBILITY
 277     bool operator!=(const linear_congruential_engine& __x,
 278                     const linear_congruential_engine& __y)
 279         {return !(__x == __y);}
 280
 281 private:
 282
 283     _LIBCPP_INLINE_VISIBILITY
 284     void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;}
 285     _LIBCPP_INLINE_VISIBILITY
 286     void seed(true_type, false_type, result_type __s) {__x_ = __s;}
 287     _LIBCPP_INLINE_VISIBILITY
 288     void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ?
 289                                                                  1 : __s % __m;}
 290     _LIBCPP_INLINE_VISIBILITY
 291     void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;}
 292
 293     template<class _Sseq>
 294     _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
 295     template<class _Sseq>
 296     _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
 297
 298     template <class _CharT, class _Traits,
 299               class _Up, _Up _Ap, _Up _Cp, _Up _Np>
 300     friend
 301     basic_ostream<_CharT, _Traits>&
 302     operator<<(basic_ostream<_CharT, _Traits>& __os,
 303                const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
 304
 305     template <class _CharT, class _Traits,
 306               class _Up, _Up _Ap, _Up _Cp, _Up _Np>
 307     friend
 308     basic_istream<_CharT, _Traits>&
 309     operator>>(basic_istream<_CharT, _Traits>& __is,
 310                linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
 311 };
 312
 313 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 314     _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
 315     linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier;
 316
 317 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 318     _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
 319     linear_congruential_engine<_UIntType, __a, __c, __m>::increment;
 320
 321 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 322     _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
 323     linear_congruential_engine<_UIntType, __a, __c, __m>::modulus;
 324
 325 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 326     _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
 327     linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed;
 328
 329 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 330 template<class _Sseq>
 331 void
 332 linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
 333                                                  integral_constant<unsigned, 1>)
 334 {
 335     const unsigned __k = 1;
 336     uint32_t __ar[__k+3];
 337     __q.generate(__ar, __ar + __k + 3);
 338     result_type __s = static_cast<result_type>(__ar[3] % __m);
 339     __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
 340 }
 341
 342 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 343 template<class _Sseq>
 344 void
 345 linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
 346                                                  integral_constant<unsigned, 2>)
 347 {
 348     const unsigned __k = 2;
 349     uint32_t __ar[__k+3];
 350     __q.generate(__ar, __ar + __k + 3);
 351     result_type __s = static_cast<result_type>((__ar[3] +
 352                                               ((uint64_t)__ar[4] << 32)) % __m);
 353     __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
 354 }
 355
 356 template <class _CharT, class _Traits,
 357           class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 358 inline _LIBCPP_INLINE_VISIBILITY
 359 basic_ostream<_CharT, _Traits>&
 360 operator<<(basic_ostream<_CharT, _Traits>& __os,
 361            const linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
 362 {
 363     __save_flags<_CharT, _Traits> __lx(__os);
 364     typedef basic_ostream<_CharT, _Traits> _Ostream;
 365     __os.flags(_Ostream::dec | _Ostream::left);
 366     __os.fill(__os.widen(' '));
 367     return __os << __x.__x_;
 368 }
 369
 370 template <class _CharT, class _Traits,
 371           class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 372 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
 373 operator>>(basic_istream<_CharT, _Traits>& __is,
 374            linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
 375 {
 376     __save_flags<_CharT, _Traits> __lx(__is);
 377     typedef basic_istream<_CharT, _Traits> _Istream;
 378     __is.flags(_Istream::dec | _Istream::skipws);
 379     _UIntType __t;
 380     __is >> __t;
 381     if (!__is.fail())
 382         __x.__x_ = __t;
 383     return __is;
 384 }
 385
 386 typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
 387                                                                    minstd_rand0;
 388 typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
 389                                                                     minstd_rand;
 390
 391 _LIBCPP_END_NAMESPACE_STD
 392
 393 _LIBCPP_POP_MACROS
 394
 395 #endif // _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H