1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
|
#ifndef UTIL_RANDOM_H
#define UTIL_RANDOM_H
#include <cstdlib>
#include <limits>
namespace util
{
/** Thread-safe, cross-platform random number generator.
*
* This is not for proper security-grade randomness, but should be "good
* enough" for producing arbitrary values of various numeric types.
*
* Before starting, call rand_init() to seed the randomizer. There is no need
* to do this more than once; in fact doing it more often is likely to make the
* randomizer less effective. Once that is done, call the rand(), rand_excl(),
* and rand_incl() functions as needed to generate pseudo-random numbers.
*
* Probability distribution is roughly uniform, but for integral types is
* skewed slightly towards lower numbers depending on how close "top" comes to
* RAND_MAX.
*
* For floating-point types, resolution is limited; there will actually be
* only RAND_MAX different possible values.
*/
/** Initialize randomizer with a fixed seed.
*
* After this, unless the randomizer gets seeded again, consecutive calls to
* the random functions will return a sequence of pseudo-random numbers
* determined by the seed. Every time the randomizer is seeded with this same
* seed, it will again start returning the same sequence of numbers.
*/
void rand_init(unsigned int);
/** Initialize randomizer based on current time.
*
* Call this to make the randomizer return hard-to-predict numbers. It won't
* produce high-grade randomness, but enough to make the program act
* differently on different runs.
*
* The seed will be based on the current time in seconds. So calling it twice
* within the same second will just reset the randomizer to where it was before.
* Don't do that.
*/
void rand_init();
/** Return a pseudorandom number between 0 and RAND_MAX inclusive.
*
* Initialize (seed) the randomizer before starting to call this.
*/
template<typename T> inline T rand();
/** Return a pseudorandom number in the half-open interval [bottom, top).
*
* Generates a value between "bottom" (inclusive) and "top" (exclusive),
* assuming that (top - bottom) <= RAND_MAX.
*/
template<typename T> inline T rand_excl(T bottom, T top);
/** Return a pseudorandom number in the half-open interval [0, top).
*
* Generates a value between 0 (inclusive) and "top" (exclusive), assuming that
* bottom <= RAND_MAX.
*/
template<typename T> inline T rand_excl(T top);
/** Return a pseudorandom number in the open interval [bottom, top].
*
* Generates a value between "bottom" and "top" inclusive, assuming that
* (top - bottom) < RAND_MAX.
*/
template<typename T> inline T rand_incl(T bottom, T top);
/** Return a pseudorandom number in the open interval [0, top].
*
* Generates a value between 0 and "top" inclusive, assuming that
* bottom < RAND_MAX.
*/
template<typename T> inline T rand_incl(T top);
/** Return a pseudorandom number which may be larger than RAND_MAX.
*
* The requested type must be integral, and its size must be an even multiple
* of the size of an int. The return value will combine one or more random
* ints into a single value, which could get quite large.
*
* The result is nonnegative. Because the constituent ints are also
* nonnegative, the most significant bit in each of the ints will be zero,
* so for a wider type, there will be "gaps" in the range of possible outputs.
*/
template<typename T> inline T wide_rand();
/** Return a pseudorandom number in [0, top), not limited to RAND_MAX.
*
* Works like wide_rand(), but if the requested type is wider than an int, it
* accommodates larger top values than an int can represent.
*/
template<typename T> inline T wide_rand_excl(T top);
/** Return a pseudorandom number in [bottom, top), not limited to RAND_MAX.
*
* Works like wide_rand(), but if the requested type is wider than an int, it
* accommodates larger value ranges than an int can represent.
*/
template<typename T> inline T wide_rand_excl(T bottom, T top);
/** Return a pseudorandom number in [0, top], not limited to RAND_MAX.
*
* Works like wide_rand(), but if the requested type is wider than an int, it
* accommodates larger top values than an int can represent.
*/
template<typename T> inline T wide_rand_incl(T top);
/** Return a pseudorandom number in [bottom, top], not limited to RAND_MAX.
*
* Works like wide_rand(), but if the requested type is wider than an int, it
* accommodates larger top values than an int can represent.
*/
template<typename T> inline T wide_rand_incl(T bottom, T top);
/// Implementation detail. For the random module's internal use only.
namespace internal
{
/// The central call to the randomizer upon which this whole module is built.
int rand_int();
/// Helper template: customize random values to required ranges.
template<typename T, bool is_integer_type> struct random_scaler;
/// Specialized random_scaler for integral types.
template<typename T> struct random_scaler<T, true>
{
static T rnd_excl(T value, T range) { return value % range; }
static T rnd_incl(T value, T range) { return value % (range + 1); }
};
/// Specialized random_scaler for non-integral types.
template<typename T> struct random_scaler<T, false>
{
static T rnd_excl(T value, T range)
{
// Promote RAND_MAX to T before adding one to avoid overflow.
return range * value / (T(RAND_MAX) + 1);
}
static T rnd_incl(T value, T range) { return range * value / RAND_MAX; }
};
/// Helper for filling a wider variable with random ints.
template<typename T, size_t remaining_ints> struct wide_random_collector
{
static T generate()
{
T one_int = util::rand<T>() << (8 * sizeof(int));
return one_int | wide_random_collector<T, remaining_ints-1>::generate();
}
};
/// Specialized wide_random_collector for generating just a single int.
template<typename T> struct wide_random_collector<T, 1>
{
static T generate() { return util::rand<T>(); }
};
} // namespace internal
template<typename T> inline T rand()
{
return T(util::internal::rand_int());
}
template<typename T> inline T rand_excl(T top)
{
typedef internal::random_scaler<T, std::numeric_limits<T>::is_integer> scaler;
return scaler::rnd_excl(util::rand<T>(), top);
}
template<typename T> inline T rand_excl(T bottom, T top)
{
return bottom + rand_excl(top - bottom);
}
template<typename T> inline T rand_incl(T top)
{
typedef internal::random_scaler<T, std::numeric_limits<T>::is_integer> scaler;
return scaler::rnd_incl(util::rand<T>(), top);
}
template<typename T> inline T rand_incl(T bottom, T top)
{
return bottom + rand_incl(top - bottom);
}
template<typename T> inline T wide_rand()
{
return internal::wide_random_collector<T, sizeof(T)/sizeof(int)>::generate();
}
template<typename T> inline T wide_rand_excl(T top)
{
typedef internal::random_scaler<T, std::numeric_limits<T>::is_integer> scaler;
return scaler::rnd_excl(util::wide_rand<T>(), top);
}
template<typename T> inline T wide_rand_excl(T bottom, T top)
{
return bottom + wide_rand_excl(top - bottom);
}
template<typename T> inline T wide_rand_incl(T top)
{
typedef internal::random_scaler<T, std::numeric_limits<T>::is_integer> scaler;
return scaler::rnd_incl(util::wide_rand<T>(), top);
}
template<typename T> inline T wide_rand_incl(T bottom, T top)
{
return bottom + wide_rand_incl(top - bottom);
}
} // namespace util
#endif
|
