linear_congruential_engine.h 14 KB

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