Warning: This file is not a C or C++ file. It does not have highlighting.

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

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of libcxx/include/__cxx03/__random/linear_congruential_engine.h