1 /* File: z-rand.c */
2
3 /* Purpose: a simple random number generator -BEN- */
4
5 #include "z-rand.h"
6
7
8
9
10 /*
11 * Angband 2.7.9 introduced a new (optimized) random number generator,
12 * based loosely on the old "random.c" from Berkeley but with some major
13 * optimizations and algorithm changes. See below for more details.
14 *
15 * Code by myself (benh@voicenet.com) and Randy (randy@stat.tamu.edu).
16 *
17 * This code provides (1) a "decent" RNG, based on the "BSD-degree-63-RNG"
18 * used in Angband 2.7.8, but rather optimized, and (2) a "simple" RNG,
19 * based on the simple "LCRNG" currently used in Angband, but "corrected"
20 * to give slightly better values. Both of these are available in two
21 * flavors, first, the simple "mod" flavor, which is fast, but slightly
22 * biased at high values, and second, the simple "div" flavor, which is
23 * less fast (and potentially non-terminating) but which is not biased
24 * and is much less subject to low-bit-non-randomness problems.
25 *
26 * You can select your favorite flavor by proper definition of the
27 * "rand_int()" macro in the "defines.h" file.
28 *
29 * Note that, in Angband 2.8.0, the "state" table will be saved in the
30 * savefile, so a special "initialization" phase will be necessary.
31 *
32 * Note the use of the "simple" RNG, first you activate it via
33 * "Rand_quick = TRUE" and "Rand_value = seed" and then it is used
34 * automatically used instead of the "complex" RNG, and when you are
35 * done, you de-activate it via "Rand_quick = FALSE" or choose a new
36 * seed via "Rand_value = seed".
37 */
38
39 /* Use the better and faster SIMD oriented Fast Mersenne Twister instead
40 * of the old RNG */
41 #define USE_SFMT
42
43 #ifdef USE_SFMT
44 #include "SFMT.h"
45 #endif
46
47
48 /*
49 * Random Number Generator -- Linear Congruent RNG
50 */
51 #define LCRNG(X) ((X) * 1103515245 + 12345)
52
53
54
55 /*
56 * Use the "simple" LCRNG
57 */
58 bool Rand_quick = TRUE;
59
60
61 /*
62 * Current "value" of the "simple" RNG
63 */
64 u32b Rand_value;
65
66
67 /*
68 * Current "index" for the "complex" RNG
69 */
70 u16b Rand_place;
71
72 /*
73 * Current "state" table for the "complex" RNG
74 */
75 u32b Rand_state[RAND_DEG];
76
77
78
79 /*
80 * Initialize the "complex" RNG using a new seed
81 */
Rand_state_init(u32b seed)82 void Rand_state_init(u32b seed)
83 {
84 #ifdef USE_SFMT
85 /* SFMT initialization */
86 init_gen_rand(seed);
87 #else
88 int i, j;
89
90 /* Seed the table */
91 Rand_state[0] = seed;
92
93 /* Propagate the seed */
94 for (i = 1; i < RAND_DEG; i++) Rand_state[i] = LCRNG(Rand_state[i-1]);
95
96 /* Cycle the table ten times per degree */
97 for (i = 0; i < RAND_DEG * 10; i++)
98 {
99 /* Acquire the next index */
100 j = Rand_place + 1;
101 if (j == RAND_DEG) j = 0;
102
103 /* Update the table, extract an entry */
104 Rand_state[j] += Rand_state[Rand_place];
105
106 /* Advance the index */
107 Rand_place = j;
108 }
109 #endif
110 }
111
112
113 /*
114 * Extract a "random" number from 0 to m-1, via "modulus"
115 *
116 * Note that "m" should probably be less than 500000, or the
117 * results may be rather biased towards low values.
118 */
Rand_mod(s32b m)119 s32b Rand_mod(s32b m)
120 {
121 u32b r;
122
123 /* Hack -- simple case */
124 if (m <= 1) return (0);
125
126 /* Use the "simple" RNG */
127 if (Rand_quick)
128 {
129 /* Cycle the generator */
130 r = (Rand_value = LCRNG(Rand_value));
131
132 /* Mutate a 28-bit "random" number */
133 r = ((r >> 4) % m);
134 }
135
136 /* Use the "complex" RNG */
137 else
138 {
139 #ifdef USE_SFMT
140 /* Use the SFMT */
141 r = gen_rand32() % m;
142 #else
143 int j;
144
145 /* Acquire the next index */
146 j = Rand_place + 1;
147 if (j == RAND_DEG) j = 0;
148
149 /* Update the table, extract an entry */
150 r = (Rand_state[j] += Rand_state[Rand_place]);
151
152 /* Advance the index */
153 Rand_place = j;
154
155 /* Extract a "random" number */
156 r = ((r >> 4) % m);
157 #endif
158 }
159
160 /* Use the value */
161 return (r);
162 }
163
164
165 /*
166 * Extract a "random" number from 0 to m-1, via "division"
167 *
168 * This method selects "random" 28-bit numbers, and then uses
169 * division to drop those numbers into "m" different partitions,
170 * plus a small non-partition to reduce bias, taking as the final
171 * value the first "good" partition that a number falls into.
172 *
173 * This method has no bias, and is much less affected by patterns
174 * in the "low" bits of the underlying RNG's.
175 */
Rand_div(s32b m)176 s32b Rand_div(s32b m)
177 {
178 u32b r, n;
179
180 /* Hack -- simple case */
181 if (m <= 1) return (0);
182
183 /* Use a simple RNG */
184 if (Rand_quick)
185 {
186 /* Partition size */
187 n = (0x10000000 / m);
188
189 /* Wait for it */
190 while (1)
191 {
192 /* Cycle the generator */
193 r = (Rand_value = LCRNG(Rand_value));
194
195 /* Mutate a 28-bit "random" number */
196 r = (r >> 4) / n;
197
198 /* Done */
199 if (r < (u32b) m) break;
200 }
201 }
202
203 /* Use a complex RNG */
204 else
205 {
206 #ifdef USE_SFMT
207 /* Partition size */
208 n = (0xFFFFFFFF / m);
209
210 /* Wait for it */
211 while (1)
212 {
213 /* SFMT version */
214 r = gen_rand32() / n;
215
216 /* Done */
217 if (r < (u32b) m) break;
218 }
219 #else
220 /* Partition size */
221 n = (0x10000000 / m);
222
223 /* Wait for it */
224 while (1)
225 {
226 int j;
227
228 /* Acquire the next index */
229 j = Rand_place + 1;
230 if (j == RAND_DEG) j = 0;
231
232 /* Update the table, extract an entry */
233 r = (Rand_state[j] += Rand_state[Rand_place]);
234
235 /* Hack -- extract a 28-bit "random" number */
236 r = (r >> 4) / n;
237
238 /* Advance the index */
239 Rand_place = j;
240
241 /* Done */
242 if (r < (u32b) m) break;
243 }
244 #endif
245 }
246
247 /* Use the value */
248 return (r);
249 }
250
251
252
253
254 /*
255 * The number of entries in the "randnor_table"
256 */
257 #define RANDNOR_NUM 256
258
259 /*
260 * The standard deviation of the "randnor_table"
261 */
262 #define RANDNOR_STD 64
263
264 /*
265 * The normal distribution table for the "randnor()" function (below)
266 */
267 static s16b randnor_table[RANDNOR_NUM] =
268 {
269 206, 613, 1022, 1430, 1838, 2245, 2652, 3058,
270 3463, 3867, 4271, 4673, 5075, 5475, 5874, 6271,
271 6667, 7061, 7454, 7845, 8234, 8621, 9006, 9389,
272 9770, 10148, 10524, 10898, 11269, 11638, 12004, 12367,
273 12727, 13085, 13440, 13792, 14140, 14486, 14828, 15168,
274 15504, 15836, 16166, 16492, 16814, 17133, 17449, 17761,
275 18069, 18374, 18675, 18972, 19266, 19556, 19842, 20124,
276 20403, 20678, 20949, 21216, 21479, 21738, 21994, 22245,
277
278 22493, 22737, 22977, 23213, 23446, 23674, 23899, 24120,
279 24336, 24550, 24759, 24965, 25166, 25365, 25559, 25750,
280 25937, 26120, 26300, 26476, 26649, 26818, 26983, 27146,
281 27304, 27460, 27612, 27760, 27906, 28048, 28187, 28323,
282 28455, 28585, 28711, 28835, 28955, 29073, 29188, 29299,
283 29409, 29515, 29619, 29720, 29818, 29914, 30007, 30098,
284 30186, 30272, 30356, 30437, 30516, 30593, 30668, 30740,
285 30810, 30879, 30945, 31010, 31072, 31133, 31192, 31249,
286
287 31304, 31358, 31410, 31460, 31509, 31556, 31601, 31646,
288 31688, 31730, 31770, 31808, 31846, 31882, 31917, 31950,
289 31983, 32014, 32044, 32074, 32102, 32129, 32155, 32180,
290 32205, 32228, 32251, 32273, 32294, 32314, 32333, 32352,
291 32370, 32387, 32404, 32420, 32435, 32450, 32464, 32477,
292 32490, 32503, 32515, 32526, 32537, 32548, 32558, 32568,
293 32577, 32586, 32595, 32603, 32611, 32618, 32625, 32632,
294 32639, 32645, 32651, 32657, 32662, 32667, 32672, 32677,
295
296 32682, 32686, 32690, 32694, 32698, 32702, 32705, 32708,
297 32711, 32714, 32717, 32720, 32722, 32725, 32727, 32729,
298 32731, 32733, 32735, 32737, 32739, 32740, 32742, 32743,
299 32745, 32746, 32747, 32748, 32749, 32750, 32751, 32752,
300 32753, 32754, 32755, 32756, 32757, 32757, 32758, 32758,
301 32759, 32760, 32760, 32761, 32761, 32761, 32762, 32762,
302 32763, 32763, 32763, 32764, 32764, 32764, 32764, 32765,
303 32765, 32765, 32765, 32766, 32766, 32766, 32766, 32767,
304 };
305
306
307
308 /*
309 * Generate a random integer number of NORMAL distribution
310 *
311 * The table above is used to generate a psuedo-normal distribution,
312 * in a manner which is much faster than calling a transcendental
313 * function to calculate a true normal distribution.
314 *
315 * Basically, entry 64*N in the table above represents the number of
316 * times out of 32767 that a random variable with normal distribution
317 * will fall within N standard deviations of the mean. That is, about
318 * 68 percent of the time for N=1 and 95 percent of the time for N=2.
319 *
320 * The table above contains a "faked" final entry which allows us to
321 * pretend that all values in a normal distribution are strictly less
322 * than four standard deviations away from the mean. This results in
323 * "conservative" distribution of approximately 1/32768 values.
324 *
325 * Note that the binary search takes up to 16 quick iterations.
326 */
randnor(int mean,int stand)327 s16b randnor(int mean, int stand)
328 {
329 s16b tmp;
330 s16b offset;
331
332 s16b low = 0;
333 s16b high = RANDNOR_NUM;
334
335 /* Paranoia */
336 if (stand < 1) return (mean);
337
338 /* Roll for probability */
339 tmp = rand_int(32768);
340
341 /* Binary Search */
342 while (low < high)
343 {
344 int mid = (low + high) >> 1;
345
346 /* Move right if forced */
347 if (randnor_table[mid] < tmp)
348 {
349 low = mid + 1;
350 }
351
352 /* Move left otherwise */
353 else
354 {
355 high = mid;
356 }
357 }
358
359 /* Convert the index into an offset */
360 offset = (long)stand * (long)low / RANDNOR_STD;
361
362 /* One half should be negative */
363 if (rand_int(100) < 50) return (mean - offset);
364
365 /* One half should be positive */
366 return (mean + offset);
367 }
368
369
370
371 /*
372 * Generates damage for "2d6" style dice rolls
373 */
damroll(int num,int sides)374 s32b damroll(int num, int sides)
375 {
376 int i, sum = 0;
377 for (i = 0; i < num; i++) sum += randint(sides);
378 return (sum);
379 }
380
381
382 /*
383 * Same as above, but always maximal
384 */
maxroll(int num,int sides)385 s32b maxroll(int num, int sides)
386 {
387 return (num * sides);
388 }
389
390
391
392