Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-05-03 08:13:38 

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 
0009 #ifndef _LIBCPP___CXX03___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H
0010 #define _LIBCPP___CXX03___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H
0011 
0012 #include <__cxx03/__config>
0013 #include <__cxx03/__random/is_seed_sequence.h>
0014 #include <__cxx03/__type_traits/enable_if.h>
0015 #include <__cxx03/__type_traits/integral_constant.h>
0016 #include <__cxx03/__type_traits/is_unsigned.h>
0017 #include <__cxx03/cstdint>
0018 #include <__cxx03/iosfwd>
0019 
0020 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0021 #  pragma GCC system_header
0022 #endif
0023 
0024 _LIBCPP_PUSH_MACROS
0025 #include <__cxx03/__undef_macros>
0026 
0027 _LIBCPP_BEGIN_NAMESPACE_STD
0028 
0029 enum __lce_alg_type {
0030   _LCE_Full,
0031   _LCE_Part,
0032   _LCE_Schrage,
0033   _LCE_Promote,
0034 };
0035 
0036 template <unsigned long long __a,
0037           unsigned long long __c,
0038           unsigned long long __m,
0039           unsigned long long _Mp,
0040           bool _HasOverflow = (__a != 0ull && (__m & (__m - 1ull)) != 0ull),      // a != 0, m != 0, m != 2^n
0041           bool _Full        = (!_HasOverflow || __m - 1ull <= (_Mp - __c) / __a), // (a * x + c) % m works
0042           bool _Part        = (!_HasOverflow || __m - 1ull <= _Mp / __a),         // (a * x) % m works
0043           bool _Schrage     = (_HasOverflow && __m % __a <= __m / __a)>               // r <= q
0044 struct __lce_alg_picker {
0045   static _LIBCPP_CONSTEXPR const __lce_alg_type __mode =
0046       _Full      ? _LCE_Full
0047       : _Part    ? _LCE_Part
0048       : _Schrage ? _LCE_Schrage
0049                  : _LCE_Promote;
0050 
0051 #ifdef _LIBCPP_HAS_NO_INT128
0052   static_assert(_Mp != (unsigned long long)(-1) || _Full || _Part || _Schrage,
0053                 "The current values for a, c, and m are not currently supported on platforms without __int128");
0054 #endif
0055 };
0056 
0057 template <unsigned long long __a,
0058           unsigned long long __c,
0059           unsigned long long __m,
0060           unsigned long long _Mp,
0061           __lce_alg_type _Mode = __lce_alg_picker<__a, __c, __m, _Mp>::__mode>
0062 struct __lce_ta;
0063 
0064 // 64
0065 
0066 #ifndef _LIBCPP_HAS_NO_INT128
0067 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
0068 struct __lce_ta<_Ap, _Cp, _Mp, (unsigned long long)(-1), _LCE_Promote> {
0069   typedef unsigned long long result_type;
0070   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __xp) {
0071     __extension__ using __calc_type = unsigned __int128;
0072     const __calc_type __a           = static_cast<__calc_type>(_Ap);
0073     const __calc_type __c           = static_cast<__calc_type>(_Cp);
0074     const __calc_type __m           = static_cast<__calc_type>(_Mp);
0075     const __calc_type __x           = static_cast<__calc_type>(__xp);
0076     return static_cast<result_type>((__a * __x + __c) % __m);
0077   }
0078 };
0079 #endif
0080 
0081 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
0082 struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Schrage> {
0083   typedef unsigned long long result_type;
0084   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0085     // Schrage's algorithm
0086     const result_type __q  = __m / __a;
0087     const result_type __r  = __m % __a;
0088     const result_type __t0 = __a * (__x % __q);
0089     const result_type __t1 = __r * (__x / __q);
0090     __x                    = __t0 + (__t0 < __t1) * __m - __t1;
0091     __x += __c - (__x >= __m - __c) * __m;
0092     return __x;
0093   }
0094 };
0095 
0096 template <unsigned long long __a, unsigned long long __m>
0097 struct __lce_ta<__a, 0ull, __m, (unsigned long long)(-1), _LCE_Schrage> {
0098   typedef unsigned long long result_type;
0099   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0100     // Schrage's algorithm
0101     const result_type __q  = __m / __a;
0102     const result_type __r  = __m % __a;
0103     const result_type __t0 = __a * (__x % __q);
0104     const result_type __t1 = __r * (__x / __q);
0105     __x                    = __t0 + (__t0 < __t1) * __m - __t1;
0106     return __x;
0107   }
0108 };
0109 
0110 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
0111 struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Part> {
0112   typedef unsigned long long result_type;
0113   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0114     // Use (((a*x) % m) + c) % m
0115     __x = (__a * __x) % __m;
0116     __x += __c - (__x >= __m - __c) * __m;
0117     return __x;
0118   }
0119 };
0120 
0121 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
0122 struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Full> {
0123   typedef unsigned long long result_type;
0124   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return (__a * __x + __c) % __m; }
0125 };
0126 
0127 template <unsigned long long __a, unsigned long long __c>
0128 struct __lce_ta<__a, __c, 0ull, (unsigned long long)(-1), _LCE_Full> {
0129   typedef unsigned long long result_type;
0130   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return __a * __x + __c; }
0131 };
0132 
0133 // 32
0134 
0135 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
0136 struct __lce_ta<__a, __c, __m, unsigned(-1), _LCE_Promote> {
0137   typedef unsigned result_type;
0138   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0139     return static_cast<result_type>(__lce_ta<__a, __c, __m, (unsigned long long)(-1)>::next(__x));
0140   }
0141 };
0142 
0143 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
0144 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Schrage> {
0145   typedef unsigned result_type;
0146   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0147     const result_type __a = static_cast<result_type>(_Ap);
0148     const result_type __c = static_cast<result_type>(_Cp);
0149     const result_type __m = static_cast<result_type>(_Mp);
0150     // Schrage's algorithm
0151     const result_type __q  = __m / __a;
0152     const result_type __r  = __m % __a;
0153     const result_type __t0 = __a * (__x % __q);
0154     const result_type __t1 = __r * (__x / __q);
0155     __x                    = __t0 + (__t0 < __t1) * __m - __t1;
0156     __x += __c - (__x >= __m - __c) * __m;
0157     return __x;
0158   }
0159 };
0160 
0161 template <unsigned long long _Ap, unsigned long long _Mp>
0162 struct __lce_ta<_Ap, 0ull, _Mp, unsigned(-1), _LCE_Schrage> {
0163   typedef unsigned result_type;
0164   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0165     const result_type __a = static_cast<result_type>(_Ap);
0166     const result_type __m = static_cast<result_type>(_Mp);
0167     // Schrage's algorithm
0168     const result_type __q  = __m / __a;
0169     const result_type __r  = __m % __a;
0170     const result_type __t0 = __a * (__x % __q);
0171     const result_type __t1 = __r * (__x / __q);
0172     __x                    = __t0 + (__t0 < __t1) * __m - __t1;
0173     return __x;
0174   }
0175 };
0176 
0177 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
0178 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Part> {
0179   typedef unsigned result_type;
0180   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0181     const result_type __a = static_cast<result_type>(_Ap);
0182     const result_type __c = static_cast<result_type>(_Cp);
0183     const result_type __m = static_cast<result_type>(_Mp);
0184     // Use (((a*x) % m) + c) % m
0185     __x = (__a * __x) % __m;
0186     __x += __c - (__x >= __m - __c) * __m;
0187     return __x;
0188   }
0189 };
0190 
0191 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
0192 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Full> {
0193   typedef unsigned result_type;
0194   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0195     const result_type __a = static_cast<result_type>(_Ap);
0196     const result_type __c = static_cast<result_type>(_Cp);
0197     const result_type __m = static_cast<result_type>(_Mp);
0198     return (__a * __x + __c) % __m;
0199   }
0200 };
0201 
0202 template <unsigned long long _Ap, unsigned long long _Cp>
0203 struct __lce_ta<_Ap, _Cp, 0ull, unsigned(-1), _LCE_Full> {
0204   typedef unsigned result_type;
0205   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0206     const result_type __a = static_cast<result_type>(_Ap);
0207     const result_type __c = static_cast<result_type>(_Cp);
0208     return __a * __x + __c;
0209   }
0210 };
0211 
0212 // 16
0213 
0214 template <unsigned long long __a, unsigned long long __c, unsigned long long __m, __lce_alg_type __mode>
0215 struct __lce_ta<__a, __c, __m, (unsigned short)(-1), __mode> {
0216   typedef unsigned short result_type;
0217   _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
0218     return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(-1)>::next(__x));
0219   }
0220 };
0221 
0222 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0223 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine;
0224 
0225 template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>
0226 _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
0227 operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
0228 
0229 template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>
0230 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
0231 operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
0232 
0233 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0234 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine {
0235 public:
0236   // types
0237   typedef _UIntType result_type;
0238 
0239 private:
0240   result_type __x_;
0241 
0242   static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(-1);
0243 
0244   static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
0245   static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
0246   static_assert(is_unsigned<_UIntType>::value, "_UIntType must be unsigned type");
0247 
0248 public:
0249   static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u : 0u;
0250   static _LIBCPP_CONSTEXPR const result_type _Max = __m - _UIntType(1u);
0251   static_assert(_Min < _Max, "linear_congruential_engine invalid parameters");
0252 
0253   // engine characteristics
0254   static _LIBCPP_CONSTEXPR const result_type multiplier = __a;
0255   static _LIBCPP_CONSTEXPR const result_type increment  = __c;
0256   static _LIBCPP_CONSTEXPR const result_type modulus    = __m;
0257   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
0258   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
0259   static _LIBCPP_CONSTEXPR const result_type default_seed = 1u;
0260 
0261   // constructors and seeding functions
0262 #ifndef _LIBCPP_CXX03_LANG
0263   _LIBCPP_HIDE_FROM_ABI linear_congruential_engine() : linear_congruential_engine(default_seed) {}
0264   _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s) { seed(__s); }
0265 #else
0266   _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s = default_seed) { seed(__s); }
0267 #endif
0268   template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0>
0269   _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(_Sseq& __q) {
0270     seed(__q);
0271   }
0272   _LIBCPP_HIDE_FROM_ABI void seed(result_type __s = default_seed) {
0273     seed(integral_constant<bool, __m == 0>(), integral_constant<bool, __c == 0>(), __s);
0274   }
0275   template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0>
0276   _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {
0277     __seed(
0278         __q,
0279         integral_constant<unsigned,
0280                           1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1) / 32 : (__m > 0x100000000ull))>());
0281   }
0282 
0283   // generating functions
0284   _LIBCPP_HIDE_FROM_ABI result_type operator()() {
0285     return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_));
0286   }
0287   _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {
0288     for (; __z; --__z)
0289       operator()();
0290   }
0291 
0292   friend _LIBCPP_HIDE_FROM_ABI bool
0293   operator==(const linear_congruential_engine& __x, const linear_congruential_engine& __y) {
0294     return __x.__x_ == __y.__x_;
0295   }
0296   friend _LIBCPP_HIDE_FROM_ABI bool
0297   operator!=(const linear_congruential_engine& __x, const linear_congruential_engine& __y) {
0298     return !(__x == __y);
0299   }
0300 
0301 private:
0302   _LIBCPP_HIDE_FROM_ABI void seed(true_type, true_type, result_type __s) { __x_ = __s == 0 ? 1 : __s; }
0303   _LIBCPP_HIDE_FROM_ABI void seed(true_type, false_type, result_type __s) { __x_ = __s; }
0304   _LIBCPP_HIDE_FROM_ABI void seed(false_type, true_type, result_type __s) { __x_ = __s % __m == 0 ? 1 : __s % __m; }
0305   _LIBCPP_HIDE_FROM_ABI void seed(false_type, false_type, result_type __s) { __x_ = __s % __m; }
0306 
0307   template <class _Sseq>
0308   _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
0309   template <class _Sseq>
0310   _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
0311 
0312   template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>
0313   friend basic_ostream<_CharT, _Traits>&
0314   operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
0315 
0316   template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>
0317   friend basic_istream<_CharT, _Traits>&
0318   operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
0319 };
0320 
0321 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0322 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
0323     linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier;
0324 
0325 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0326 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
0327     linear_congruential_engine<_UIntType, __a, __c, __m>::increment;
0328 
0329 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0330 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
0331     linear_congruential_engine<_UIntType, __a, __c, __m>::modulus;
0332 
0333 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0334 _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
0335     linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed;
0336 
0337 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0338 template <class _Sseq>
0339 void linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, integral_constant<unsigned, 1>) {
0340   const unsigned __k = 1;
0341   uint32_t __ar[__k + 3];
0342   __q.generate(__ar, __ar + __k + 3);
0343   result_type __s = static_cast<result_type>(__ar[3] % __m);
0344   __x_            = __c == 0 && __s == 0 ? result_type(1) : __s;
0345 }
0346 
0347 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0348 template <class _Sseq>
0349 void linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, integral_constant<unsigned, 2>) {
0350   const unsigned __k = 2;
0351   uint32_t __ar[__k + 3];
0352   __q.generate(__ar, __ar + __k + 3);
0353   result_type __s = static_cast<result_type>((__ar[3] + ((uint64_t)__ar[4] << 32)) % __m);
0354   __x_            = __c == 0 && __s == 0 ? result_type(1) : __s;
0355 }
0356 
0357 template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0358 inline _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
0359 operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_UIntType, __a, __c, __m>& __x) {
0360   __save_flags<_CharT, _Traits> __lx(__os);
0361   typedef basic_ostream<_CharT, _Traits> _Ostream;
0362   __os.flags(_Ostream::dec | _Ostream::left);
0363   __os.fill(__os.widen(' '));
0364   return __os << __x.__x_;
0365 }
0366 
0367 template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
0368 _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
0369 operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_UIntType, __a, __c, __m>& __x) {
0370   __save_flags<_CharT, _Traits> __lx(__is);
0371   typedef basic_istream<_CharT, _Traits> _Istream;
0372   __is.flags(_Istream::dec | _Istream::skipws);
0373   _UIntType __t;
0374   __is >> __t;
0375   if (!__is.fail())
0376     __x.__x_ = __t;
0377   return __is;
0378 }
0379 
0380 typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> minstd_rand0;
0381 typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> minstd_rand;
0382 
0383 _LIBCPP_END_NAMESPACE_STD
0384 
0385 _LIBCPP_POP_MACROS
0386 
0387 #endif // _LIBCPP___CXX03___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!