CoCalc -- linear_congruential

GitHub Repository: freebsd/freebsd-src
Path: blob/main/contrib/llvm-project/libcxx/include/__random/linear_congruential_engine.h
³⁵²³³ views
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
enum __lce_alg_type {
30
  _LCE_Full,
31
  _LCE_Part,
32
  _LCE_Schrage,
33
  _LCE_Promote,
34
};
35

36
template <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
44
struct __lce_alg_picker {
45
  static _LIBCPP_CONSTEXPR const __lce_alg_type __mode =
46
      _Full      ? _LCE_Full
47
      : _Part    ? _LCE_Part
48
      : _Schrage ? _LCE_Schrage
49
                 : _LCE_Promote;
50

51
#ifdef _LIBCPP_HAS_NO_INT128
52
  static_assert(_Mp != (unsigned long long)(-1) || _Full || _Part || _Schrage,
53
                "The current values for a, c, and m are not currently supported on platforms without __int128");
54
#endif
55
};
56

57
template <unsigned long long __a,
58
          unsigned long long __c,
59
          unsigned long long __m,
60
          unsigned long long _Mp,
61
          __lce_alg_type _Mode = __lce_alg_picker<__a, __c, __m, _Mp>::__mode>
62
struct __lce_ta;
63

64
// 64
65

66
#ifndef _LIBCPP_HAS_NO_INT128
67
template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
68
struct __lce_ta<_Ap, _Cp, _Mp, (unsigned long long)(-1), _LCE_Promote> {
69
  typedef unsigned long long result_type;
70
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __xp) {
71
    __extension__ using __calc_type = unsigned __int128;
72
    const __calc_type __a           = static_cast<__calc_type>(_Ap);
73
    const __calc_type __c           = static_cast<__calc_type>(_Cp);
74
    const __calc_type __m           = static_cast<__calc_type>(_Mp);
75
    const __calc_type __x           = static_cast<__calc_type>(__xp);
76
    return static_cast<result_type>((__a * __x + __c) % __m);
77
  }
78
};
79
#endif
80

81
template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
82
struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Schrage> {
83
  typedef unsigned long long result_type;
84
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
85
    // Schrage's algorithm
86
    const result_type __q  = __m / __a;
87
    const result_type __r  = __m % __a;
88
    const result_type __t0 = __a * (__x % __q);
89
    const result_type __t1 = __r * (__x / __q);
90
    __x                    = __t0 + (__t0 < __t1) * __m - __t1;
91
    __x += __c - (__x >= __m - __c) * __m;
92
    return __x;
93
  }
94
};
95

96
template <unsigned long long __a, unsigned long long __m>
97
struct __lce_ta<__a, 0ull, __m, (unsigned long long)(-1), _LCE_Schrage> {
98
  typedef unsigned long long result_type;
99
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
100
    // Schrage's algorithm
101
    const result_type __q  = __m / __a;
102
    const result_type __r  = __m % __a;
103
    const result_type __t0 = __a * (__x % __q);
104
    const result_type __t1 = __r * (__x / __q);
105
    __x                    = __t0 + (__t0 < __t1) * __m - __t1;
106
    return __x;
107
  }
108
};
109

110
template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
111
struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Part> {
112
  typedef unsigned long long result_type;
113
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
114
    // Use (((a*x) % m) + c) % m
115
    __x = (__a * __x) % __m;
116
    __x += __c - (__x >= __m - __c) * __m;
117
    return __x;
118
  }
119
};
120

121
template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
122
struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Full> {
123
  typedef unsigned long long result_type;
124
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return (__a * __x + __c) % __m; }
125
};
126

127
template <unsigned long long __a, unsigned long long __c>
128
struct __lce_ta<__a, __c, 0ull, (unsigned long long)(-1), _LCE_Full> {
129
  typedef unsigned long long result_type;
130
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return __a * __x + __c; }
131
};
132

133
// 32
134

135
template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
136
struct __lce_ta<__a, __c, __m, unsigned(-1), _LCE_Promote> {
137
  typedef unsigned result_type;
138
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
139
    return static_cast<result_type>(__lce_ta<__a, __c, __m, (unsigned long long)(-1)>::next(__x));
140
  }
141
};
142

143
template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
144
struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Schrage> {
145
  typedef unsigned result_type;
146
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
147
    const result_type __a = static_cast<result_type>(_Ap);
148
    const result_type __c = static_cast<result_type>(_Cp);
149
    const result_type __m = static_cast<result_type>(_Mp);
150
    // Schrage's algorithm
151
    const result_type __q  = __m / __a;
152
    const result_type __r  = __m % __a;
153
    const result_type __t0 = __a * (__x % __q);
154
    const result_type __t1 = __r * (__x / __q);
155
    __x                    = __t0 + (__t0 < __t1) * __m - __t1;
156
    __x += __c - (__x >= __m - __c) * __m;
157
    return __x;
158
  }
159
};
160

161
template <unsigned long long _Ap, unsigned long long _Mp>
162
struct __lce_ta<_Ap, 0ull, _Mp, unsigned(-1), _LCE_Schrage> {
163
  typedef unsigned result_type;
164
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
165
    const result_type __a = static_cast<result_type>(_Ap);
166
    const result_type __m = static_cast<result_type>(_Mp);
167
    // Schrage's algorithm
168
    const result_type __q  = __m / __a;
169
    const result_type __r  = __m % __a;
170
    const result_type __t0 = __a * (__x % __q);
171
    const result_type __t1 = __r * (__x / __q);
172
    __x                    = __t0 + (__t0 < __t1) * __m - __t1;
173
    return __x;
174
  }
175
};
176

177
template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
178
struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Part> {
179
  typedef unsigned result_type;
180
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
181
    const result_type __a = static_cast<result_type>(_Ap);
182
    const result_type __c = static_cast<result_type>(_Cp);
183
    const result_type __m = static_cast<result_type>(_Mp);
184
    // Use (((a*x) % m) + c) % m
185
    __x = (__a * __x) % __m;
186
    __x += __c - (__x >= __m - __c) * __m;
187
    return __x;
188
  }
189
};
190

191
template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
192
struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Full> {
193
  typedef unsigned result_type;
194
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
195
    const result_type __a = static_cast<result_type>(_Ap);
196
    const result_type __c = static_cast<result_type>(_Cp);
197
    const result_type __m = static_cast<result_type>(_Mp);
198
    return (__a * __x + __c) % __m;
199
  }
200
};
201

202
template <unsigned long long _Ap, unsigned long long _Cp>
203
struct __lce_ta<_Ap, _Cp, 0ull, unsigned(-1), _LCE_Full> {
204
  typedef unsigned result_type;
205
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
206
    const result_type __a = static_cast<result_type>(_Ap);
207
    const result_type __c = static_cast<result_type>(_Cp);
208
    return __a * __x + __c;
209
  }
210
};
211

212
// 16
213

214
template <unsigned long long __a, unsigned long long __c, unsigned long long __m, __lce_alg_type __mode>
215
struct __lce_ta<__a, __c, __m, (unsigned short)(-1), __mode> {
216
  typedef unsigned short result_type;
217
  _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) {
218
    return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(-1)>::next(__x));
219
  }
220
};
221

222
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
223
class _LIBCPP_TEMPLATE_VIS linear_congruential_engine;
224

225
template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>
226
_LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
227
operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
228

229
template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>
230
_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
231
operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
232

233
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
234
class _LIBCPP_TEMPLATE_VIS linear_congruential_engine {
235
public:
236
  // types
237
  typedef _UIntType result_type;
238

239
private:
240
  result_type __x_;
241

242
  static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(-1);
243

244
  static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
245
  static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
246
  static_assert(is_unsigned<_UIntType>::value, "_UIntType must be unsigned type");
247

248
public:
249
  static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u : 0u;
250
  static _LIBCPP_CONSTEXPR const result_type _Max = __m - _UIntType(1u);
251
  static_assert(_Min < _Max, "linear_congruential_engine invalid parameters");
252

253
  // engine characteristics
254
  static _LIBCPP_CONSTEXPR const result_type multiplier = __a;
255
  static _LIBCPP_CONSTEXPR const result_type increment  = __c;
256
  static _LIBCPP_CONSTEXPR const result_type modulus    = __m;
257
  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
258
  _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
259
  static _LIBCPP_CONSTEXPR const result_type default_seed = 1u;
260

261
  // constructors and seeding functions
262
#ifndef _LIBCPP_CXX03_LANG
263
  _LIBCPP_HIDE_FROM_ABI linear_congruential_engine() : linear_congruential_engine(default_seed) {}
264
  _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s) { seed(__s); }
265
#else
266
  _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s = default_seed) { seed(__s); }
267
#endif
268
  template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0>
269
  _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(_Sseq& __q) {
270
    seed(__q);
271
  }
272
  _LIBCPP_HIDE_FROM_ABI void seed(result_type __s = default_seed) {
273
    seed(integral_constant<bool, __m == 0>(), integral_constant<bool, __c == 0>(), __s);
274
  }
275
  template <class _Sseq, __enable_if_t<__is_seed_sequence<_Sseq, linear_congruential_engine>::value, int> = 0>
276
  _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) {
277
    __seed(
278
        __q,
279
        integral_constant<unsigned,
280
                          1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1) / 32 : (__m > 0x100000000ull))>());
281
  }
282

283
  // generating functions
284
  _LIBCPP_HIDE_FROM_ABI result_type operator()() {
285
    return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_));
286
  }
287
  _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) {
288
    for (; __z; --__z)
289
      operator()();
290
  }
291

292
  friend _LIBCPP_HIDE_FROM_ABI bool
293
  operator==(const linear_congruential_engine& __x, const linear_congruential_engine& __y) {
294
    return __x.__x_ == __y.__x_;
295
  }
296
  friend _LIBCPP_HIDE_FROM_ABI bool
297
  operator!=(const linear_congruential_engine& __x, const linear_congruential_engine& __y) {
298
    return !(__x == __y);
299
  }
300

301
private:
302
  _LIBCPP_HIDE_FROM_ABI void seed(true_type, true_type, result_type __s) { __x_ = __s == 0 ? 1 : __s; }
303
  _LIBCPP_HIDE_FROM_ABI void seed(true_type, false_type, result_type __s) { __x_ = __s; }
304
  _LIBCPP_HIDE_FROM_ABI void seed(false_type, true_type, result_type __s) { __x_ = __s % __m == 0 ? 1 : __s % __m; }
305
  _LIBCPP_HIDE_FROM_ABI void seed(false_type, false_type, result_type __s) { __x_ = __s % __m; }
306

307
  template <class _Sseq>
308
  _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
309
  template <class _Sseq>
310
  _LIBCPP_HIDE_FROM_ABI void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
311

312
  template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>
313
  friend basic_ostream<_CharT, _Traits>&
314
  operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
315

316
  template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np>
317
  friend basic_istream<_CharT, _Traits>&
318
  operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
319
};
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>::multiplier;
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>::increment;
328

329
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
330
_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
331
    linear_congruential_engine<_UIntType, __a, __c, __m>::modulus;
332

333
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
334
_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
335
    linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed;
336

337
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
338
template <class _Sseq>
339
void linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, integral_constant<unsigned, 1>) {
340
  const unsigned __k = 1;
341
  uint32_t __ar[__k + 3];
342
  __q.generate(__ar, __ar + __k + 3);
343
  result_type __s = static_cast<result_type>(__ar[3] % __m);
344
  __x_            = __c == 0 && __s == 0 ? result_type(1) : __s;
345
}
346

347
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
348
template <class _Sseq>
349
void linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, integral_constant<unsigned, 2>) {
350
  const unsigned __k = 2;
351
  uint32_t __ar[__k + 3];
352
  __q.generate(__ar, __ar + __k + 3);
353
  result_type __s = static_cast<result_type>((__ar[3] + ((uint64_t)__ar[4] << 32)) % __m);
354
  __x_            = __c == 0 && __s == 0 ? result_type(1) : __s;
355
}
356

357
template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
358
inline _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>&
359
operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_UIntType, __a, __c, __m>& __x) {
360
  __save_flags<_CharT, _Traits> __lx(__os);
361
  typedef basic_ostream<_CharT, _Traits> _Ostream;
362
  __os.flags(_Ostream::dec | _Ostream::left);
363
  __os.fill(__os.widen(' '));
364
  return __os << __x.__x_;
365
}
366

367
template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
368
_LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>&
369
operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_UIntType, __a, __c, __m>& __x) {
370
  __save_flags<_CharT, _Traits> __lx(__is);
371
  typedef basic_istream<_CharT, _Traits> _Istream;
372
  __is.flags(_Istream::dec | _Istream::skipws);
373
  _UIntType __t;
374
  __is >> __t;
375
  if (!__is.fail())
376
    __x.__x_ = __t;
377
  return __is;
378
}
379

380
typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> minstd_rand0;
381
typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> minstd_rand;
382

383
_LIBCPP_END_NAMESPACE_STD
384

385
_LIBCPP_POP_MACROS
386

387
#endif // _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H
388

389
Product

Resources

Company
