Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009 #ifndef ApproxMVBB_RandomGenerator_hpp
00010 #define ApproxMVBB_RandomGenerator_hpp
00011
00012 #include "ApproxMVBB/Config/Config.hpp"
00013 #include "ApproxMVBB/Common/StaticAssert.hpp"
00014 #include ApproxMVBB_TypeDefs_INCLUDE_FILE
00015
00016 #include <type_traits>
00017 #include <cstdint>
00018 #include <random>
00019 #include <limits>
00020 #include <ctime>
00021
00022 namespace ApproxMVBB{
00023 namespace RandomGenerators{
00024
00034 class APPROXMVBB_EXPORT SplitMix64{
00035 private:
00036 uint64_t x;
00037 public:
00038
00039 SplitMix64(const SplitMix64 & gen) = default;
00040 SplitMix64(SplitMix64 && gen) = default;
00041
00042 SplitMix64(uint64_t seed);
00043 void seed(uint64_t seed);
00044 uint64_t operator()();
00045
00046
00047 using result_type = uint64_t;
00048 static constexpr result_type min(){ return std::numeric_limits<result_type>::min(); }
00049 static constexpr result_type max(){ return std::numeric_limits<result_type>::max(); }
00050 };
00051
00052
00062 class APPROXMVBB_EXPORT XorShift128Plus{
00063 private:
00064 uint64_t s[2];
00065
00066 public:
00067 XorShift128Plus(const XorShift128Plus & gen) = default;
00068 XorShift128Plus(XorShift128Plus && gen) = default;
00069
00070 XorShift128Plus(uint64_t seed);
00072 XorShift128Plus();
00073
00074 void seed(uint64_t seed);
00076 uint64_t operator()();
00077
00081 void jump();
00082
00083
00084 using result_type = uint64_t;
00085 static constexpr result_type min(){ return std::numeric_limits<result_type>::min(); }
00086 static constexpr result_type max(){ return std::numeric_limits<result_type>::max(); }
00087 };
00088
00089
00090
00091
00092
00093
00094
00095
00096 class APPROXMVBB_EXPORT XorShift1024Star{
00097
00098 private:
00099 uint64_t s[16];
00100 int p = 0;
00101
00102 public:
00103 XorShift1024Star(const XorShift1024Star & gen) = default;
00104 XorShift1024Star(XorShift1024Star && gen) = default;
00105
00106
00107 XorShift1024Star(uint64_t seed);
00109 XorShift1024Star();
00110
00111 void seed(uint64_t seed);
00113 uint64_t operator()();
00114
00118 void jump();
00119
00120
00121 using result_type = uint64_t;
00122 static constexpr result_type min(){ return std::numeric_limits<result_type>::min(); }
00123 static constexpr result_type max(){ return std::numeric_limits<result_type>::max(); }
00124 };
00125
00127 template<typename T>
00128 class AlmostUniformUIntDistribution{
00129 public:
00130 ApproxMVBB_STATIC_ASSERT( std::is_unsigned<T>::value )
00131
00132 AlmostUniformUIntDistribution(T min,T max): m_min(min), m_max(max) {
00133 m_nRange = m_max - m_min + 1;
00134 }
00135
00136 template<typename G>
00137 T operator()(G & g){
00138 return ((double)g() / ((double)(G::max()-G::min()) + 1.0)) * m_nRange + m_min;
00139 }
00140
00141 private:
00142 T m_min,m_max,m_nRange;
00143 };
00144
00146 template<typename T>
00147 class AlmostUniformRealDistribution{
00148 public:
00149 ApproxMVBB_STATIC_ASSERT( std::is_floating_point<T>::value )
00150
00151 AlmostUniformRealDistribution(T min,T max): m_min(min), m_max(max) {
00152 m_nRange = m_max - m_min + 1;
00153 }
00154
00155 template<typename G>
00156 T operator()(G & g){
00157 return ((T)g() / (T)(G::max()-G::min())) * m_nRange + m_min;
00158 }
00159
00160 private:
00161 T m_min,m_max,m_nRange;
00162 };
00163
00165 static const uint64_t defaultSeed = 314159;
00166 using DefaultRandomGen = XorShift128Plus;
00167
00169 #ifdef ApproxMVBB_BUILD_TESTS
00170 #warning "ApproxMVBB: Using non-standart uniform distributions for testing!"
00171 template<typename T>
00172 using DefaultUniformUIntDistribution = AlmostUniformUIntDistribution<T>;
00173 template<typename T>
00174 using DefaultUniformRealDistribution = AlmostUniformRealDistribution<T>;
00175 #else
00176 template<typename T>
00177 using DefaultUniformUIntDistribution = std::uniform_int_distribution<T>;
00178 template<typename T>
00179 using DefaultUniformRealDistribution = std::uniform_real_distribution<T>;
00180 #endif
00181
00182
00183 }
00184 }
00185
00186
00187
00188 namespace ApproxMVBB{
00189 namespace RandomGenerators{
00190
00191
00192 inline SplitMix64::SplitMix64(uint64_t sd) :x(sd) {}
00193
00194 inline void SplitMix64::seed(uint64_t sd){ x = sd;}
00195
00196 inline uint64_t SplitMix64::operator()() {
00197 uint64_t z = (x += UINT64_C(0x9E3779B97F4A7C15));
00198 z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9);
00199 z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB);
00200 return z ^ (z >> 31);
00201 }
00202
00203
00204 inline XorShift128Plus::XorShift128Plus(uint64_t sd){
00205 seed(sd);
00206 }
00207
00209 inline XorShift128Plus::XorShift128Plus(){
00210 seed(time(NULL));
00211 }
00212
00213 inline void XorShift128Plus::seed(uint64_t sd){
00214 s[0] = SplitMix64{sd}();
00215 s[1] = s[0] ;
00216 }
00217
00219 inline uint64_t XorShift128Plus::operator()(){
00220 uint64_t s1 = s[0];
00221 const uint64_t s0 = s[1];
00222 s[0] = s0;
00223 s1 ^= s1 << 23;
00224 s[1] = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5);
00225 return s[1] + s0;
00226 }
00227
00228
00229
00230 inline void XorShift128Plus::jump() {
00231 static const uint64_t JUMP[] = { 0x8a5cd789635d2dff, 0x121fd2155c472f96 };
00232
00233 uint64_t s0 = 0;
00234 uint64_t s1 = 0;
00235 for(unsigned int i = 0; i < sizeof(JUMP) / sizeof (*JUMP); i++)
00236 for(int b = 0; b < 64; b++) {
00237 if (JUMP[i] & 1ULL << b) {
00238 s0 ^= s[0];
00239 s1 ^= s[1];
00240 }
00241 this->operator()();
00242 }
00243
00244 s[0] = s0;
00245 s[1] = s1;
00246 }
00247
00248
00249
00250 inline XorShift1024Star::XorShift1024Star(uint64_t sd){
00251 seed(sd);
00252 }
00253
00255 inline XorShift1024Star::XorShift1024Star(){
00256 seed(time(NULL));
00257 }
00258
00259 inline void XorShift1024Star::seed(uint64_t sd){
00260 uint64_t ss = SplitMix64{sd}();
00261 for(auto & v : s){
00262 v = ss;
00263 }
00264 }
00265
00267 inline uint64_t XorShift1024Star::operator()() {
00268 const uint64_t s0 = s[p];
00269 uint64_t s1 = s[p = (p + 1) & 15];
00270 s1 ^= s1 << 31;
00271 s[p] = s1 ^ s0 ^ (s1 >> 11) ^ (s0 >> 30);
00272 return s[p] * UINT64_C(1181783497276652981);
00273 }
00274
00275
00276
00280 inline void XorShift1024Star::jump() {
00281 static const uint64_t JUMP[] = { 0x84242f96eca9c41d,
00282 0xa3c65b8776f96855, 0x5b34a39f070b5837, 0x4489affce4f31a1e,
00283 0x2ffeeb0a48316f40, 0xdc2d9891fe68c022, 0x3659132bb12fea70,
00284 0xaac17d8efa43cab8, 0xc4cb815590989b13, 0x5ee975283d71c93b,
00285 0x691548c86c1bd540, 0x7910c41d10a1e6a5, 0x0b5fc64563b3e2a8,
00286 0x047f7684e9fc949d, 0xb99181f2d8f685ca, 0x284600e3f30e38c3
00287 };
00288
00289 uint64_t t[16] = { 0 };
00290 for(unsigned int i = 0; i < sizeof(JUMP) / sizeof (*JUMP); i++)
00291 for(int b = 0; b < 64; b++) {
00292 if (JUMP[i] & 1ULL << b)
00293 for(int j = 0; j < 16; j++)
00294 t[j] ^= s[(j + p) & 15];
00295 this->operator()();
00296 }
00297
00298 for(int j = 0; j < 16; j++)
00299 s[(j + p) & 15] = t[j];
00300 }
00301
00302 }
00303 }
00304
00305 #endif