Created
May 26, 2018 06:36
-
-
Save twoscomplement/de1c21324ba84704086eb37995582d46 to your computer and use it in GitHub Desktop.
Investigation of <random>
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <random> | |
#include <stdlib.h> | |
#include <cstdint> | |
#include <limits> | |
#include <type_traits> | |
#include <algorithm> | |
#include <string> | |
namespace __detail { | |
template<typename _UIntType, size_t __w, | |
bool = __w < static_cast<size_t> | |
(std::numeric_limits<_UIntType>::digits)> | |
struct _Shift | |
{ static const _UIntType __value = 0; }; | |
template<typename _UIntType, size_t __w> | |
struct _Shift<_UIntType, __w, true> | |
{ static const _UIntType __value = _UIntType(1) << __w; }; | |
template<int __s, | |
int __which = ((__s <= 8 * sizeof (int)) | |
+ (__s <= 8 * sizeof (long)) | |
+ (__s <= 8 * sizeof (long long)) | |
+ (__s <= 128))> | |
struct _Select_uint_least_t | |
{ | |
static_assert(__which < 0, | |
"sorry, would be too much trouble for a slow result"); | |
}; | |
template<int __s> | |
struct _Select_uint_least_t<__s, 4> | |
{ typedef unsigned int type; }; | |
template<int __s> | |
struct _Select_uint_least_t<__s, 3> | |
{ typedef unsigned long type; }; | |
template<int __s> | |
struct _Select_uint_least_t<__s, 2> | |
{ typedef unsigned long long type; }; | |
template<int __s> | |
struct _Select_uint_least_t<__s, 1> | |
{ typedef unsigned __int128 type; }; | |
template<typename _Tp, _Tp __m, _Tp __a, _Tp __c, | |
bool __big_enough = (!(__m & (__m - 1)) | |
|| (_Tp(-1) - __c) / __a >= __m - 1), | |
bool __schrage_ok = __m % __a < __m / __a> | |
struct _Mod | |
{ | |
typedef typename _Select_uint_least_t<std::__lg(__a) | |
+ std::__lg(__m) + 2>::type _Tp2; | |
static _Tp | |
__calc(_Tp __x) | |
{ return static_cast<_Tp>((_Tp2(__a) * __x + __c) % __m); } | |
}; | |
template<typename _Tp, _Tp __m, _Tp __a, _Tp __c> | |
struct _Mod<_Tp, __m, __a, __c, false, true> | |
{ | |
static _Tp | |
__calc(_Tp __x); | |
}; | |
template<typename _Tp, _Tp __m, _Tp __a, _Tp __c, bool __s> | |
struct _Mod<_Tp, __m, __a, __c, true, __s> | |
{ | |
static _Tp | |
__calc(_Tp __x) | |
{ | |
_Tp __res = __a * __x + __c; | |
if (__m) | |
__res %= __m; | |
return __res; | |
} | |
}; | |
template<typename _Tp, _Tp __m, _Tp __a = 1, _Tp __c = 0> | |
inline _Tp | |
__mod(_Tp __x) | |
{ return _Mod<_Tp, __m, __a, __c>::__calc(__x); } | |
} | |
template<typename _UIntType, size_t __w, | |
size_t __n, size_t __m, size_t __r, | |
_UIntType __a, size_t __u, _UIntType __d, size_t __s, | |
_UIntType __b, size_t __t, | |
_UIntType __c, size_t __l, _UIntType __f> | |
class mersenne_twister_engine | |
{ | |
public: | |
typedef _UIntType result_type; | |
static constexpr size_t state_size = __n; | |
static constexpr result_type default_seed = 5489u; | |
explicit mersenne_twister_engine(result_type __sd = default_seed) { seed(__sd); } | |
static constexpr result_type min() { return 0; } | |
static constexpr result_type max() { return __detail::_Shift<_UIntType, __w>::__value - 1; } | |
void seed(result_type __sd = default_seed); | |
result_type operator()(); | |
private: | |
void _M_gen_rand(); | |
_UIntType _M_x[state_size]; | |
size_t _M_p; | |
}; | |
template<typename _UIntType, size_t __w, | |
size_t __n, size_t __m, size_t __r, | |
_UIntType __a, size_t __u, _UIntType __d, size_t __s, | |
_UIntType __b, size_t __t, _UIntType __c, size_t __l, | |
_UIntType __f> | |
void | |
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, | |
__s, __b, __t, __c, __l, __f>::_M_gen_rand(void) | |
{ | |
const _UIntType __upper_mask = (~_UIntType()) << __r; | |
const _UIntType __lower_mask = ~__upper_mask; | |
for (size_t __k = 0; __k < (__n - __m); ++__k) | |
{ | |
_UIntType __y = ((_M_x[__k] & __upper_mask) | |
| (_M_x[__k + 1] & __lower_mask)); | |
_M_x[__k] = (_M_x[__k + __m] ^ (__y >> 1) | |
^ ((__y & 0x01) ? __a : 0)); | |
} | |
for (size_t __k = (__n - __m); __k < (__n - 1); ++__k) | |
{ | |
_UIntType __y = ((_M_x[__k] & __upper_mask) | |
| (_M_x[__k + 1] & __lower_mask)); | |
_M_x[__k] = (_M_x[__k + (__m - __n)] ^ (__y >> 1) | |
^ ((__y & 0x01) ? __a : 0)); | |
} | |
_UIntType __y = ((_M_x[__n - 1] & __upper_mask) | (_M_x[0] & __lower_mask)); | |
_M_x[__n - 1] = (_M_x[__m - 1] ^ (__y >> 1) ^ ((__y & 0x01) ? __a : 0)); | |
_M_p = 0; | |
} | |
template<typename _UIntType, size_t __w, | |
size_t __n, size_t __m, size_t __r, | |
_UIntType __a, size_t __u, _UIntType __d, size_t __s, | |
_UIntType __b, size_t __t, _UIntType __c, size_t __l, | |
_UIntType __f> | |
typename | |
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, | |
__s, __b, __t, __c, __l, __f>::result_type | |
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, | |
__s, __b, __t, __c, __l, __f>::operator()() | |
{ | |
if (_M_p >= state_size) | |
_M_gen_rand(); | |
result_type __z = _M_x[_M_p++]; | |
__z ^= (__z >> __u) & __d; | |
__z ^= (__z << __s) & __b; | |
__z ^= (__z << __t) & __c; | |
__z ^= (__z >> __l); | |
return __z; | |
} | |
using mt19937 = mersenne_twister_engine<std::uint_fast32_t, 32, 624, 397, 31, | |
0x9908b0df, 11, | |
0xffffffff, 7, | |
0x9d2c5680, 15, | |
0xefc60000, 18, 1812433253>; | |
class random_device { | |
public: | |
typedef unsigned int result_type; | |
explicit random_device() { _M_init(); } | |
//explicit random_device(const std::string& __token = "default") { _M_init(__token); } | |
~random_device() { _M_fini(); } | |
result_type operator()() { return this->_M_getval(); } | |
random_device(const random_device&) = delete; | |
void operator=(const random_device&) = delete; | |
static constexpr result_type min() | |
{ return std::numeric_limits<result_type>::min(); } | |
static constexpr result_type max() | |
{ return std::numeric_limits<result_type>::max(); } | |
private: | |
void _M_init(); | |
void _M_fini(); | |
result_type _M_getval(); | |
union { | |
void* _M_file; | |
mt19937 _M_mt; | |
}; | |
}; | |
template<typename _IntType = int> | |
class uniform_int_distribution { | |
public: | |
typedef _IntType result_type; | |
struct param_type | |
{ | |
typedef uniform_int_distribution<_IntType> distribution_type; | |
explicit param_type(_IntType __a = 0, _IntType __b = std::numeric_limits<_IntType>::max()) | |
: _M_a(__a), _M_b(__b) {} | |
result_type a() const { return _M_a; } | |
result_type b() const { return _M_b; } | |
friend bool operator==(const param_type& __p1, const param_type& __p2) | |
{ return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; } | |
friend bool operator!=(const param_type& __p1, const param_type& __p2) | |
{ return !(__p1 == __p2); } | |
private: | |
_IntType _M_a; | |
_IntType _M_b; | |
}; | |
public: | |
explicit uniform_int_distribution(_IntType __a = 0, _IntType __b = std::numeric_limits<_IntType>::max()) | |
: _M_param(__a, __b) { } | |
template<typename _UniformRandomNumberGenerator> | |
result_type operator()(_UniformRandomNumberGenerator& __urng) | |
{ return this->operator()(__urng, _M_param); } | |
template<typename _UniformRandomNumberGenerator> | |
result_type operator()(_UniformRandomNumberGenerator& __urng, const param_type& __p); | |
private: | |
param_type _M_param; | |
}; | |
template<typename _IntType> | |
template<typename _UniformRandomNumberGenerator> | |
typename uniform_int_distribution<_IntType>::result_type | |
uniform_int_distribution<_IntType>::operator()(_UniformRandomNumberGenerator& __urng, const param_type& __param) | |
{ | |
typedef typename _UniformRandomNumberGenerator::result_type _Gresult_type; | |
typedef typename std::make_unsigned<result_type>::type __utype; | |
typedef typename std::common_type<_Gresult_type, __utype>::type __uctype; | |
const __uctype __urngmin = __urng.min(); | |
const __uctype __urngmax = __urng.max(); | |
const __uctype __urngrange = __urngmax - __urngmin; | |
const __uctype __urange = __uctype(__param.b()) - __uctype(__param.a()); | |
__uctype __ret; | |
if (__urngrange > __urange) | |
{ | |
const __uctype __uerange = __urange + 1; | |
const __uctype __scaling = __urngrange / __uerange; | |
const __uctype __past = __uerange * __scaling; | |
do | |
__ret = __uctype(__urng()) - __urngmin; | |
while (__ret >= __past); | |
__ret /= __scaling; | |
} | |
else if (__urngrange < __urange) | |
{ | |
__uctype __tmp; | |
do | |
{ | |
const __uctype __uerngrange = __urngrange + 1; | |
__tmp = (__uerngrange * operator()(__urng, param_type(0, __urange / __uerngrange))); | |
__ret = __tmp + (__uctype(__urng()) - __urngmin); | |
} | |
while (__ret > __urange || __ret < __tmp); | |
} | |
else | |
__ret = __uctype(__urng()) - __urngmin; | |
return __ret + __param.a(); | |
} | |
template<typename _UIntType, | |
size_t __w, size_t __n, size_t __m, size_t __r, | |
_UIntType __a, size_t __u, _UIntType __d, size_t __s, | |
_UIntType __b, size_t __t, _UIntType __c, size_t __l, | |
_UIntType __f> | |
void | |
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, | |
__s, __b, __t, __c, __l, __f>::seed(result_type __sd) | |
{ | |
_M_x[0] = __detail::__mod<_UIntType, | |
__detail::_Shift<_UIntType, __w>::__value>(__sd); | |
for (size_t __i = 1; __i < state_size; ++__i) | |
{ | |
_UIntType __x = _M_x[__i - 1]; | |
__x ^= __x >> (__w - 2); | |
__x *= __f; | |
__x += __detail::__mod<_UIntType, __n>(__i); | |
_M_x[__i] = __detail::__mod<_UIntType, | |
__detail::_Shift<_UIntType, __w>::__value>(__x); | |
} | |
_M_p = state_size; | |
} | |
int MyEyes() | |
{ | |
#if 1 | |
auto x = []() { | |
random_device rd; | |
mt19937 gen(rd()); | |
uniform_int_distribution<> dis(0, RAND_MAX); | |
return dis(gen); | |
}; | |
#else | |
auto x = []() { | |
std::random_device rd; | |
std::mt19937 gen(rd()); | |
std::uniform_int_distribution<> dis(0, RAND_MAX); | |
return dis(gen); | |
}; | |
#endif | |
return x(); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment