| //===----------------------------------------------------------------------===// | |
| // | |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
| // See https://llvm.org/LICENSE.txt for license information. | |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
| // | |
| //===----------------------------------------------------------------------===// | |
| #ifndef _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H | |
| #define _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H | |
| #include <__config> | |
| #include <__random/is_seed_sequence.h> | |
| #include <__type_traits/enable_if.h> | |
| #include <__type_traits/integral_constant.h> | |
| #include <__type_traits/is_unsigned.h> | |
| #include <cstdint> | |
| #include <iosfwd> | |
| #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) | |
| # pragma GCC system_header | |
| #endif | |
| _LIBCPP_PUSH_MACROS | |
| #include <__undef_macros> | |
| _LIBCPP_BEGIN_NAMESPACE_STD | |
| enum __lce_alg_type { | |
| _LCE_Full, | |
| _LCE_Part, | |
| _LCE_Schrage, | |
| _LCE_Promote, | |
| }; | |
| template <unsigned long long __a, | |
| unsigned long long __c, | |
| unsigned long long __m, | |
| unsigned long long _Mp, | |
| bool _HasOverflow = (__a != 0ull && (__m & (__m - 1ull)) != 0ull), // a != 0, m != 0, m != 2^n | |
| bool _Full = (!_HasOverflow || __m - 1ull <= (_Mp - __c) / __a), // (a * x + c) % m works | |
| bool _Part = (!_HasOverflow || __m - 1ull <= _Mp / __a), // (a * x) % m works | |
| bool _Schrage = (_HasOverflow && __m % __a <= __m / __a)> // r <= q | |
| struct __lce_alg_picker { | |
| static _LIBCPP_CONSTEXPR const __lce_alg_type __mode = | |
| _Full ? _LCE_Full | |
| : _Part ? _LCE_Part | |
| : _Schrage ? _LCE_Schrage | |
| : _LCE_Promote; | |
| #if !_LIBCPP_HAS_INT128 | |
| static_assert(_Mp != (unsigned long long)(-1) || _Full || _Part || _Schrage, | |
| "The current values for a, c, and m are not currently supported on platforms without __int128"); | |
| #endif | |
| }; | |
| template <unsigned long long __a, | |
| unsigned long long __c, | |
| unsigned long long __m, | |
| unsigned long long _Mp, | |
| __lce_alg_type _Mode = __lce_alg_picker<__a, __c, __m, _Mp>::__mode> | |
| struct __lce_ta; | |
| // 64 | |
| #if _LIBCPP_HAS_INT128 | |
| template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> | |
| struct __lce_ta<_Ap, _Cp, _Mp, (unsigned long long)(-1), _LCE_Promote> { | |
| typedef unsigned long long result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __xp) { | |
| __extension__ using __calc_type = unsigned __int128; | |
| const __calc_type __a = static_cast<__calc_type>(_Ap); | |
| const __calc_type __c = static_cast<__calc_type>(_Cp); | |
| const __calc_type __m = static_cast<__calc_type>(_Mp); | |
| const __calc_type __x = static_cast<__calc_type>(__xp); | |
| return static_cast<result_type>((__a * __x + __c) % __m); | |
| } | |
| }; | |
| #endif | |
| template <unsigned long long __a, unsigned long long __c, unsigned long long __m> | |
| struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Schrage> { | |
| typedef unsigned long long result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| // Schrage's algorithm | |
| const result_type __q = __m / __a; | |
| const result_type __r = __m % __a; | |
| const result_type __t0 = __a * (__x % __q); | |
| const result_type __t1 = __r * (__x / __q); | |
| __x = __t0 + (__t0 < __t1) * __m - __t1; | |
| __x += __c - (__x >= __m - __c) * __m; | |
| return __x; | |
| } | |
| }; | |
| template <unsigned long long __a, unsigned long long __m> | |
| struct __lce_ta<__a, 0ull, __m, (unsigned long long)(-1), _LCE_Schrage> { | |
| typedef unsigned long long result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| // Schrage's algorithm | |
| const result_type __q = __m / __a; | |
| const result_type __r = __m % __a; | |
| const result_type __t0 = __a * (__x % __q); | |
| const result_type __t1 = __r * (__x / __q); | |
| __x = __t0 + (__t0 < __t1) * __m - __t1; | |
| return __x; | |
| } | |
| }; | |
| template <unsigned long long __a, unsigned long long __c, unsigned long long __m> | |
| struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Part> { | |
| typedef unsigned long long result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| // Use (((a*x) % m) + c) % m | |
| __x = (__a * __x) % __m; | |
| __x += __c - (__x >= __m - __c) * __m; | |
| return __x; | |
| } | |
| }; | |
| template <unsigned long long __a, unsigned long long __c, unsigned long long __m> | |
| struct __lce_ta<__a, __c, __m, (unsigned long long)(-1), _LCE_Full> { | |
| typedef unsigned long long result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return (__a * __x + __c) % __m; } | |
| }; | |
| template <unsigned long long __a, unsigned long long __c> | |
| struct __lce_ta<__a, __c, 0ull, (unsigned long long)(-1), _LCE_Full> { | |
| typedef unsigned long long result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { return __a * __x + __c; } | |
| }; | |
| // 32 | |
| template <unsigned long long __a, unsigned long long __c, unsigned long long __m> | |
| struct __lce_ta<__a, __c, __m, unsigned(-1), _LCE_Promote> { | |
| typedef unsigned result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| return static_cast<result_type>(__lce_ta<__a, __c, __m, (unsigned long long)(-1)>::next(__x)); | |
| } | |
| }; | |
| template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> | |
| struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Schrage> { | |
| typedef unsigned result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| const result_type __a = static_cast<result_type>(_Ap); | |
| const result_type __c = static_cast<result_type>(_Cp); | |
| const result_type __m = static_cast<result_type>(_Mp); | |
| // Schrage's algorithm | |
| const result_type __q = __m / __a; | |
| const result_type __r = __m % __a; | |
| const result_type __t0 = __a * (__x % __q); | |
| const result_type __t1 = __r * (__x / __q); | |
| __x = __t0 + (__t0 < __t1) * __m - __t1; | |
| __x += __c - (__x >= __m - __c) * __m; | |
| return __x; | |
| } | |
| }; | |
| template <unsigned long long _Ap, unsigned long long _Mp> | |
| struct __lce_ta<_Ap, 0ull, _Mp, unsigned(-1), _LCE_Schrage> { | |
| typedef unsigned result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| const result_type __a = static_cast<result_type>(_Ap); | |
| const result_type __m = static_cast<result_type>(_Mp); | |
| // Schrage's algorithm | |
| const result_type __q = __m / __a; | |
| const result_type __r = __m % __a; | |
| const result_type __t0 = __a * (__x % __q); | |
| const result_type __t1 = __r * (__x / __q); | |
| __x = __t0 + (__t0 < __t1) * __m - __t1; | |
| return __x; | |
| } | |
| }; | |
| template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> | |
| struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Part> { | |
| typedef unsigned result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| const result_type __a = static_cast<result_type>(_Ap); | |
| const result_type __c = static_cast<result_type>(_Cp); | |
| const result_type __m = static_cast<result_type>(_Mp); | |
| // Use (((a*x) % m) + c) % m | |
| __x = (__a * __x) % __m; | |
| __x += __c - (__x >= __m - __c) * __m; | |
| return __x; | |
| } | |
| }; | |
| template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp> | |
| struct __lce_ta<_Ap, _Cp, _Mp, unsigned(-1), _LCE_Full> { | |
| typedef unsigned result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| const result_type __a = static_cast<result_type>(_Ap); | |
| const result_type __c = static_cast<result_type>(_Cp); | |
| const result_type __m = static_cast<result_type>(_Mp); | |
| return (__a * __x + __c) % __m; | |
| } | |
| }; | |
| template <unsigned long long _Ap, unsigned long long _Cp> | |
| struct __lce_ta<_Ap, _Cp, 0ull, unsigned(-1), _LCE_Full> { | |
| typedef unsigned result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| const result_type __a = static_cast<result_type>(_Ap); | |
| const result_type __c = static_cast<result_type>(_Cp); | |
| return __a * __x + __c; | |
| } | |
| }; | |
| // 16 | |
| template <unsigned long long __a, unsigned long long __c, unsigned long long __m, __lce_alg_type __mode> | |
| struct __lce_ta<__a, __c, __m, (unsigned short)(-1), __mode> { | |
| typedef unsigned short result_type; | |
| _LIBCPP_HIDE_FROM_ABI static result_type next(result_type __x) { | |
| return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(-1)>::next(__x)); | |
| } | |
| }; | |
| template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> | |
| class linear_congruential_engine; | |
| template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> | |
| _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& | |
| operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); | |
| template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> | |
| _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& | |
| operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); | |
| template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> | |
| class linear_congruential_engine { | |
| public: | |
| // types | |
| typedef _UIntType result_type; | |
| private: | |
| result_type __x_; | |
| static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(-1); | |
| static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters"); | |
| static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters"); | |
| static_assert(is_unsigned<_UIntType>::value, "_UIntType must be unsigned type"); | |
| public: | |
| static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u : 0u; | |
| static _LIBCPP_CONSTEXPR const result_type _Max = __m - _UIntType(1u); | |
| static_assert(_Min < _Max, "linear_congruential_engine invalid parameters"); | |
| // engine characteristics | |
| static inline _LIBCPP_CONSTEXPR const result_type multiplier = __a; | |
| static inline _LIBCPP_CONSTEXPR const result_type increment = __c; | |
| static inline _LIBCPP_CONSTEXPR const result_type modulus = __m; | |
| _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type min() { return _Min; } | |
| _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR result_type max() { return _Max; } | |
| static inline _LIBCPP_CONSTEXPR const result_type default_seed = 1u; | |
| // constructors and seeding functions | |
| #ifndef _LIBCPP_CXX03_LANG | |
| _LIBCPP_HIDE_FROM_ABI linear_congruential_engine() : linear_congruential_engine(default_seed) {} | |
| _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s) { seed(__s); } | |
| #else | |
| _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(result_type __s = default_seed) { seed(__s); } | |
| #endif | |
| template <class _Sseq, __enable_if_t<__is_seed_sequence_v<_Sseq, linear_congruential_engine>, int> = 0> | |
| _LIBCPP_HIDE_FROM_ABI explicit linear_congruential_engine(_Sseq& __q) { | |
| seed(__q); | |
| } | |
| _LIBCPP_HIDE_FROM_ABI void seed(result_type __s = default_seed) { | |
| if _LIBCPP_CONSTEXPR (__m == 0) { | |
| if _LIBCPP_CONSTEXPR (__c == 0) | |
| __x_ = __s == 0 ? 1 : __s; | |
| else | |
| __x_ = __s; | |
| } else { | |
| if _LIBCPP_CONSTEXPR (__c == 0) | |
| __x_ = __s % __m == 0 ? 1 : __s % __m; | |
| else | |
| __x_ = __s % __m; | |
| } | |
| } | |
| template <class _Sseq, __enable_if_t<__is_seed_sequence_v<_Sseq, linear_congruential_engine>, int> = 0> | |
| _LIBCPP_HIDE_FROM_ABI void seed(_Sseq& __q) { | |
| const _LIBCPP_CONSTEXPR unsigned __k = | |
| 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1) / 32 : (__m > 0x100000000ull)); | |
| static_assert(__k <= 2); | |
| uint32_t __ar[__k + 3]; | |
| __q.generate(__ar, __ar + __k + 3); | |
| result_type __s = static_cast<result_type>((__ar[3] + (__k == 1 ? 0 : (uint64_t)__ar[4] << 32)) % __m); | |
| __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; | |
| } | |
| // generating functions | |
| _LIBCPP_HIDE_FROM_ABI result_type operator()() { | |
| return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_)); | |
| } | |
| _LIBCPP_HIDE_FROM_ABI void discard(unsigned long long __z) { | |
| for (; __z; --__z) | |
| operator()(); | |
| } | |
| friend _LIBCPP_HIDE_FROM_ABI bool | |
| operator==(const linear_congruential_engine& __x, const linear_congruential_engine& __y) { | |
| return __x.__x_ == __y.__x_; | |
| } | |
| friend _LIBCPP_HIDE_FROM_ABI bool | |
| operator!=(const linear_congruential_engine& __x, const linear_congruential_engine& __y) { | |
| return !(__x == __y); | |
| } | |
| private: | |
| template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> | |
| friend basic_ostream<_CharT, _Traits>& | |
| operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&); | |
| template <class _CharT, class _Traits, class _Up, _Up _Ap, _Up _Cp, _Up _Np> | |
| friend basic_istream<_CharT, _Traits>& | |
| operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x); | |
| }; | |
| template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> | |
| inline _LIBCPP_HIDE_FROM_ABI basic_ostream<_CharT, _Traits>& | |
| operator<<(basic_ostream<_CharT, _Traits>& __os, const linear_congruential_engine<_UIntType, __a, __c, __m>& __x) { | |
| __save_flags<_CharT, _Traits> __lx(__os); | |
| typedef basic_ostream<_CharT, _Traits> _Ostream; | |
| __os.flags(_Ostream::dec | _Ostream::left); | |
| __os.fill(__os.widen(' ')); | |
| return __os << __x.__x_; | |
| } | |
| template <class _CharT, class _Traits, class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> | |
| _LIBCPP_HIDE_FROM_ABI basic_istream<_CharT, _Traits>& | |
| operator>>(basic_istream<_CharT, _Traits>& __is, linear_congruential_engine<_UIntType, __a, __c, __m>& __x) { | |
| __save_flags<_CharT, _Traits> __lx(__is); | |
| typedef basic_istream<_CharT, _Traits> _Istream; | |
| __is.flags(_Istream::dec | _Istream::skipws); | |
| _UIntType __t; | |
| __is >> __t; | |
| if (!__is.fail()) | |
| __x.__x_ = __t; | |
| return __is; | |
| } | |
| typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> minstd_rand0; | |
| typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> minstd_rand; | |
| _LIBCPP_END_NAMESPACE_STD | |
| _LIBCPP_POP_MACROS | |
| #endif // _LIBCPP___RANDOM_LINEAR_CONGRUENTIAL_ENGINE_H |