Engine.hpp (9786B)
1 /* 2 Copyright 2010-2011, D. E. Shaw Research. 3 All rights reserved. 4 5 Redistribution and use in source and binary forms, with or without 6 modification, are permitted provided that the following conditions are 7 met: 8 9 * Redistributions of source code must retain the above copyright 10 notice, this list of conditions, and the following disclaimer. 11 12 * Redistributions in binary form must reproduce the above copyright 13 notice, this list of conditions, and the following disclaimer in the 14 documentation and/or other materials provided with the distribution. 15 16 * Neither the name of D. E. Shaw Research nor the names of its 17 contributors may be used to endorse or promote products derived from 18 this software without specific prior written permission. 19 20 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 23 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 24 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 25 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 26 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 30 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 #ifndef __Engine_dot_hpp_ 33 #define __Engine_dot_hpp_ 34 35 #include "../features/compilerfeatures.h" 36 #include "../array.h" 37 #include <limits> 38 #include <stdexcept> 39 #include <sstream> 40 #include <algorithm> 41 #include <vector> 42 #if R123_USE_CXX11_TYPE_TRAITS 43 #include <type_traits> 44 #endif 45 46 namespace r123{ 47 /** 48 If G satisfies the requirements of a CBRNG, and has a ctr_type whose 49 value_type is an unsigned integral type, then Engine<G> satisfies 50 the requirements of a C++11 "Uniform Random Number Engine" and can 51 be used in any context where such an object is expected. 52 53 Note that wrapping a counter based RNG with a traditional API in 54 this way obscures much of the power of counter based PRNGs. 55 Nevertheless, it may be of value in applications that are already 56 coded to work with the C++11 random number engines. 57 58 The MicroURNG template in MicroURNG.hpp 59 provides the more limited functionality of a C++11 "Uniform 60 Random Number Generator", but leaves the application in control 61 of counters and keys and hence may be preferable to the Engine template. 62 For example, a MicroURNG allows one to use C++11 "Random Number 63 Distributions" without giving up control over the counters 64 and keys. 65 */ 66 67 template<typename CBRNG> 68 struct Engine { 69 typedef CBRNG cbrng_type; 70 typedef typename CBRNG::ctr_type ctr_type; 71 typedef typename CBRNG::key_type key_type; 72 typedef typename CBRNG::ukey_type ukey_type; 73 typedef typename ctr_type::value_type result_type; 74 75 protected: 76 cbrng_type b; 77 key_type key; 78 ctr_type c; 79 ctr_type v; 80 81 void fix_invariant(){ 82 if( v.back() != 0 ) { 83 result_type vv = v.back(); 84 v = b(c, key); 85 v.back() = vv; 86 } 87 } 88 public: 89 explicit Engine() : b(), c() { 90 ukey_type x = {{}}; 91 v.back() = 0; 92 key = x; 93 } 94 explicit Engine(result_type r) : b(), c() { 95 ukey_type x = {{typename ukey_type::value_type(r)}}; 96 v.back() = 0; 97 key = x; 98 } 99 // 26.5.3 says that the SeedSeq templates shouldn't particpate in 100 // overload resolution unless the type qualifies as a SeedSeq. 101 // How that is determined is unspecified, except that "as a 102 // minimum a type shall not qualify as a SeedSeq if it is 103 // implicitly convertible to a result_type." 104 // 105 // First, we make sure that even the non-const copy constructor 106 // works as expected. In addition, if we've got C++11 107 // type_traits, we use enable_if and is_convertible to implement 108 // the convertible-to-result_type restriction. Otherwise, the 109 // template is unconditional and will match in some surpirsing 110 // and undesirable situations. 111 Engine(Engine& e) : b(e.b), key(e.key), c(e.c){ 112 v.back() = e.v.back(); 113 fix_invariant(); 114 } 115 Engine(const Engine& e) : b(e.b), key(e.key), c(e.c){ 116 v.back() = e.v.back(); 117 fix_invariant(); 118 } 119 #if __cplusplus >= 201103L 120 Engine& operator=(const Engine&) = default; 121 Engine& operator=(Engine&&) = default; 122 #endif 123 124 template <typename SeedSeq> 125 explicit Engine(SeedSeq &s 126 #if R123_USE_CXX11_TYPE_TRAITS 127 , typename std::enable_if<!std::is_convertible<SeedSeq, result_type>::value>::type* =0 128 #endif 129 ) 130 : b(), c() { 131 ukey_type ukey = ukey_type::seed(s); 132 key = ukey; 133 v.back() = 0; 134 } 135 void seed(result_type r){ 136 *this = Engine(r); 137 } 138 template <typename SeedSeq> 139 void seed(SeedSeq &s 140 #if R123_USE_CXX11_TYPE_TRAITS 141 , typename std::enable_if<!std::is_convertible<SeedSeq, result_type>::value>::type* =0 142 #endif 143 ){ 144 *this = Engine(s); 145 } 146 void seed(){ 147 *this = Engine(); 148 } 149 friend bool operator==(const Engine& lhs, const Engine& rhs){ 150 return lhs.c==rhs.c && lhs.v.back() == rhs.v.back() && lhs.key == rhs.key; 151 } 152 friend bool operator!=(const Engine& lhs, const Engine& rhs){ 153 return lhs.c!=rhs.c || lhs.v.back()!=rhs.v.back() || lhs.key!=rhs.key; 154 } 155 156 friend std::ostream& operator<<(std::ostream& os, const Engine& be){ 157 return os << be.c << " " << be.key << " " << be.v.back(); 158 } 159 160 friend std::istream& operator>>(std::istream& is, Engine& be){ 161 is >> be.c >> be.key >> be.v.back(); 162 be.fix_invariant(); 163 return is; 164 } 165 166 // The <random> shipped with MacOS Xcode 4.5.2 imposes a 167 // non-standard requirement that URNGs also have static data 168 // members: _Min and _Max. Later versions of libc++ impose the 169 // requirement only when constexpr isn't supported. Although the 170 // Xcode 4.5.2 requirement is clearly non-standard, it is unlikely 171 // to be fixed and it is very easy work around. We certainly 172 // don't want to go to great lengths to accommodate every buggy 173 // library we come across, but in this particular case, the effort 174 // is low and the benefit is high, so it's worth doing. Thanks to 175 // Yan Zhou for pointing this out to us. See similar code in 176 // ../MicroURNG.hpp 177 const static result_type _Min = 0; 178 const static result_type _Max = ~((result_type)0); 179 180 static R123_CONSTEXPR result_type min R123_NO_MACRO_SUBST () { return _Min; } 181 static R123_CONSTEXPR result_type max R123_NO_MACRO_SUBST () { return _Max; } 182 183 result_type operator()(){ 184 if( c.size() == 1 ) // short-circuit the scalar case. Compilers aren't mind-readers. 185 return b(c.incr(), key)[0]; 186 result_type& elem = v.back(); 187 if( elem == 0 ){ 188 v = b(c.incr(), key); 189 result_type ret = v.back(); 190 elem = c.size()-1; 191 return ret; 192 } 193 return v[--elem]; 194 } 195 196 void discard(R123_ULONG_LONG skip){ 197 // don't forget: elem counts down 198 size_t nelem = c.size(); 199 size_t sub = skip % nelem; 200 result_type& elem = v.back(); 201 skip /= nelem; 202 if (elem < sub) { 203 elem += nelem; 204 skip++; 205 } 206 elem -= sub; 207 c.incr(skip); 208 fix_invariant(); 209 } 210 211 //-------------------------- 212 // Some bonus methods, not required for a Random Number 213 // Engine 214 215 // Constructors and seed() method for ukey_type seem useful 216 // We need const and non-const to supersede the SeedSeq template. 217 explicit Engine(const ukey_type &uk) : key(uk), c(){ v.back() = 0; } 218 explicit Engine(ukey_type &uk) : key(uk), c(){ v.back() = 0; } 219 void seed(const ukey_type& uk){ 220 *this = Engine(uk); 221 } 222 void seed(ukey_type& uk){ 223 *this = Engine(uk); 224 } 225 226 #if R123_USE_CXX11_TYPE_TRAITS 227 template <typename DUMMY=void> 228 explicit Engine(const key_type& k, 229 typename std::enable_if<!std::is_same<ukey_type, key_type>::value, DUMMY>::type* = 0) 230 : key(k), c(){ v.back() = 0; } 231 232 template <typename DUMMY=void> 233 void seed(const key_type& k, 234 typename std::enable_if<!std::is_same<ukey_type, key_type>::value, DUMMY>::type* = 0){ 235 *this = Engine(k); 236 } 237 #endif 238 239 // Forward the e(counter) to the CBRNG we are templated 240 // on, using the current value of the key. 241 ctr_type operator()(const ctr_type& c) const{ 242 return b(c, key); 243 } 244 245 key_type getkey() const{ 246 return key; 247 } 248 249 // N.B. setkey(k) is different from seed(k) because seed(k) zeros 250 // the counter (per the C++11 requirements for an Engine), whereas 251 // setkey does not. 252 void setkey(const key_type& k){ 253 key = k; 254 fix_invariant(); 255 } 256 257 // Maybe the caller want's to know the details of 258 // the internal state, e.g., so it can call a different 259 // bijection with the same counter. 260 std::pair<ctr_type, result_type> getcounter() const { 261 return std::make_pair(c, v.back()); 262 } 263 264 // And the inverse. 265 void setcounter(const ctr_type& _c, result_type _elem){ 266 static const size_t nelem = c.size(); 267 if( _elem >= nelem ) 268 throw std::range_error("Engine::setcounter called with elem out of range"); 269 c = _c; 270 v.back() = _elem; 271 fix_invariant(); 272 } 273 274 void setcounter(const std::pair<ctr_type, result_type>& ce){ 275 setcounter(ce.first, ce.second); 276 } 277 }; 278 } // namespace r123 279 280 #endif