STXXL  1.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
rand.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/common/rand.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002, 2003, 2005 Roman Dementiev <[email protected]>
7  * Copyright (C) 2007 Andreas Beckmann <[email protected]>
8  * Copyright (C) 2013 Timo Bingmann <[email protected]>
9  *
10  * Distributed under the Boost Software License, Version 1.0.
11  * (See accompanying file LICENSE_1_0.txt or copy at
12  * http://www.boost.org/LICENSE_1_0.txt)
13  **************************************************************************/
14 
15 #ifndef STXXL_COMMON_RAND_HEADER
16 #define STXXL_COMMON_RAND_HEADER
17 
18 #include <cmath>
19 
20 #include <stxxl/bits/config.h>
22 #include <stxxl/bits/common/seed.h>
23 #include <stxxl/bits/namespace.h>
24 
25 #if STXXL_STD_RANDOM
26  #include <random>
27 #elif STXXL_BOOST_RANDOM
28  #include <boost/random.hpp>
29 #endif
30 
31 // Recommended seeding procedure:
32 // by default, the global seed is initialized from a high resolution timer and the process id
33 // 1. stxxl::set_seed(seed); // optionally, do this if you wan't to us a specific seed to replay a certain program run
34 // 2. seed = stxxl::get_next_seed(); // store/print/... this value can be used for step 1 to replay the program with a specific seed
35 // 3. stxxl::srandom_number32(); // seed the global state of stxxl::random_number32
36 // 4. create all the other prngs used.
37 
39 
40 extern unsigned ran32State;
41 
42 //! \addtogroup support
43 //! \{
44 
45 //! Fast uniform [0, 2^32) pseudo-random generator with period 2^32, random
46 //! bits: 32.
47 //! \warning Uses a global state and is not reentrant or thread-safe!
49 {
50  typedef unsigned value_type;
51 
52  //! Returns a random number from [0, 2^32)
53  inline value_type operator () () const
54  {
55  return (ran32State = 1664525 * ran32State + 1013904223);
56  }
57 
58  //! Returns a random number from [0, N)
59  inline value_type operator () (const value_type& N) const
60  {
61  return operator () () % N;
62  }
63 };
64 
65 //! Set a seed value for \c random_number32.
66 inline void srandom_number32(unsigned seed = 0)
67 {
68  if (!seed)
69  seed = get_next_seed();
70  ran32State = seed;
71 }
72 
73 //! Fast uniform [0, 2^32) pseudo-random generator with period 2^32, random
74 //! bits: 32.
75 //! Reentrant variant of random_number32 that keeps it's private state.
77 {
78  typedef unsigned value_type;
79  mutable unsigned state;
80 
81  random_number32_r(unsigned seed = 0)
82  {
83  if (!seed)
84  seed = get_next_seed();
85  state = seed;
86  }
87 
88  //! Returns a random number from [0, 2^32)
89  inline value_type operator () () const
90  {
91  return (state = 1664525 * state + 1013904223);
92  }
93 };
94 
95 //! Fast uniform [0, 255] pseudo-random generator with period 2^8, random bits:
96 //! 8 (one byte).
98 {
101  unsigned int m_pos;
102 
103 public:
104  typedef uint8 value_type;
105 
106  random_number8_r(unsigned seed = 0)
107  : m_rnd32(seed), m_pos(4)
108  { }
109 
110  //! Returns a random byte from [0, 255]
111  inline value_type operator () ()
112  {
113  if (++m_pos >= 4) {
114  m_value = m_rnd32();
115  m_pos = 0;
116  }
117  return ((uint8*)&m_value)[m_pos];
118  }
119 };
120 
121 //! Fast uniform [0.0, 1.0) pseudo-random generator
122 //! \warning Uses a global state and is not reentrant or thread-safe!
124 {
125  typedef double value_type;
127 
128  random_uniform_fast(unsigned /*seed*/ = 0)
129  { }
130 
131  //! Returns a random number from [0.0, 1.0)
132  inline value_type operator () () const
133  {
134  return (double(rnd32()) * (0.5 / 0x80000000));
135  }
136 };
137 
138 #if STXXL_MSVC
139 #pragma warning(push)
140 #pragma warning(disable:4512) // assignment operator could not be generated
141 #endif
142 
143 //! Slow and precise uniform [0.0, 1.0) pseudo-random generator
144 //! period: at least 2^48, random bits: at least 31
145 //!
146 //! \warning Seed is not the same as in the fast generator \c random_uniform_fast
148 {
149  typedef double value_type;
150 #if STXXL_STD_RANDOM
151  typedef std::default_random_engine gen_type;
152  mutable gen_type gen;
153  typedef std::uniform_real_distribution<> uni_type;
154  mutable uni_type uni;
155 
156  random_uniform_slow(unsigned seed = 0)
157  : gen(seed ? seed : get_next_seed()),
158  uni(0.0, 1.0)
159  { }
160 #elif STXXL_BOOST_RANDOM
161  typedef boost::minstd_rand base_generator_type;
162  base_generator_type generator;
163  boost::uniform_real<> uni_dist;
164  mutable boost::variate_generator<base_generator_type&, boost::uniform_real<> > uni;
165 
166  random_uniform_slow(unsigned seed = 0) : uni(generator, uni_dist)
167  {
168  if (!seed)
169  seed = get_next_seed();
170  uni.engine().seed(seed);
171  }
172 #else
173  mutable unsigned short state48[3];
174 /*
175  * embedded erand48.c
176  *
177  * Copyright (c) 1993 Martin Birgmeier
178  * All rights reserved.
179  *
180  * You may redistribute unmodified or modified versions of this source
181  * code provided that the above copyright notice and this and the
182  * following conditions are retained.
183  *
184  * This software is provided ``as is'', and comes with no warranties
185  * of any kind. I shall in no event be liable for anything that happens
186  * to anyone/anything when using this software.
187  */
188  static void
189  _dorand48(unsigned short xseed[3])
190  {
191  unsigned long accu;
192  unsigned short temp[2];
193 
194  static const unsigned short _mult[3] = { 0xe66d, 0xdeec, 0x0005 };
195  static const unsigned short _add = 0x000b;
196 
197  accu = (unsigned long)_mult[0] * (unsigned long)xseed[0]
198  + (unsigned long)_add;
199  temp[0] = (unsigned short)accu; /* lower 16 bits */
200  accu >>= sizeof(unsigned short) * 8;
201  accu += (unsigned long)_mult[0] * (unsigned long)xseed[1]
202  + (unsigned long)_mult[1] * (unsigned long)xseed[0];
203  temp[1] = (unsigned short)accu; /* middle 16 bits */
204  accu >>= sizeof(unsigned short) * 8;
205  accu += _mult[0] * xseed[2] + _mult[1] * xseed[1] + _mult[2] * xseed[0];
206  xseed[0] = temp[0];
207  xseed[1] = temp[1];
208  xseed[2] = (unsigned short)accu;
209  }
210 
211  static double
212  _erand48(unsigned short xseed[3])
213  {
214  _dorand48(xseed);
215  return ldexp((double)xseed[0], -48)
216  + ldexp((double)xseed[1], -32)
217  + ldexp((double)xseed[2], -16);
218  }
219 /* end erand48.c */
220 
221  random_uniform_slow(unsigned seed = 0)
222  {
223  if (!seed)
224  seed = get_next_seed();
225  state48[0] = (unsigned short)(seed & 0xffff);
226  state48[1] = (unsigned short)(seed >> 16);
227  state48[2] = 42;
228  _dorand48(state48);
229  }
230 #endif
231 
232  //! Returns a random number from [0.0, 1.0)
233  inline value_type operator () () const
234  {
235 #if STXXL_STD_RANDOM
236  return uni(gen);
237 #elif STXXL_BOOST_RANDOM
238  return uni();
239 #else
240  return _erand48(state48);
241 #endif
242  }
243 };
244 
245 //! Uniform [0, N) pseudo-random generator
246 template <class UniformRGen = random_uniform_fast>
248 {
249  typedef unsigned value_type;
250  UniformRGen uniform;
251 
252  random_number(unsigned seed = 0) : uniform(seed)
253  { }
254 
255  //! Returns a random number from [0, N)
256  inline value_type operator () (value_type N) const
257  {
258  return static_cast<value_type>(uniform() * double(N));
259  }
260 };
261 
262 //! Slow and precise uniform [0, 2^64) pseudo-random generator
264 {
267 
268  random_number64(unsigned seed = 0) : uniform(seed)
269  { }
270 
271  //! Returns a random number from [0, 2^64)
272  inline value_type operator () () const
273  {
274  return static_cast<value_type>(uniform() * (18446744073709551616.));
275  }
276 
277  //! Returns a random number from [0, N)
278  inline value_type operator () (value_type N) const
279  {
280  return static_cast<value_type>(uniform() * double(N));
281  }
282 };
283 
284 #if STXXL_MSVC
285 #pragma warning(pop) // assignment operator could not be generated
286 #endif
287 
288 //! \}
289 
291 
292 #endif // !STXXL_COMMON_RAND_HEADER
random_number64(unsigned seed=0)
Definition: rand.h:268
Uniform [0, N) pseudo-random generator.
Definition: rand.h:247
random_uniform_slow uniform
Definition: rand.h:266
unsigned int m_pos
Definition: rand.h:101
unsigned ran32State
Definition: rand.cpp:20
unsigned long long int uint64
Definition: types.h:39
Slow and precise uniform [0.0, 1.0) pseudo-random generator period: at least 2^48, random bits: at least 31.
Definition: rand.h:147
UniformRGen uniform
Definition: rand.h:250
unsigned get_next_seed()
get a seed value for prng initialization, subsequent calls return a sequence of different values ...
Definition: seed.cpp:73
random_number32_r m_rnd32
Definition: rand.h:99
unsigned value_type
Definition: rand.h:249
random_uniform_fast(unsigned=0)
Definition: rand.h:128
unsigned int uint32
Definition: types.h:37
static double _erand48(unsigned short xseed[3])
Definition: rand.h:212
random_uniform_slow(unsigned seed=0)
Definition: rand.h:221
Fast uniform [0, 255] pseudo-random generator with period 2^8, random bits: 8 (one byte)...
Definition: rand.h:97
random_number32_r(unsigned seed=0)
Definition: rand.h:81
unsigned char uint8
Definition: types.h:33
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
void srandom_number32(unsigned seed=0)
Set a seed value for random_number32.
Definition: rand.h:66
Fast uniform [0, 2^32) pseudo-random generator with period 2^32, random bits: 32. Reentrant variant o...
Definition: rand.h:76
Fast uniform [0, 2^32) pseudo-random generator with period 2^32, random bits: 32. ...
Definition: rand.h:48
random_number(unsigned seed=0)
Definition: rand.h:252
unsigned value_type
Definition: rand.h:78
random_number32 rnd32
Definition: rand.h:126
stxxl::uint64 value_type
Definition: rand.h:265
Fast uniform [0.0, 1.0) pseudo-random generator.
Definition: rand.h:123
unsigned value_type
Definition: rand.h:50
random_number8_r(unsigned seed=0)
Definition: rand.h:106
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
static void _dorand48(unsigned short xseed[3])
Definition: rand.h:189
Slow and precise uniform [0, 2^64) pseudo-random generator.
Definition: rand.h:263