3 /* Purpose: a simple random number generator -BEN- */
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.
15 * Code by myself (benh@phial.com) and Randy (randy@stat.tamu.edu).
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.
26 * You can select your favorite flavor by proper definition of the
27 * "rand_int()" macro in the "defines.h" file.
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.
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".
41 * Random Number Generator -- Linear Congruent RNG
43 #define LCRNG(X) ((X) * 1103515245 + 12345)
48 * Use the "simple" LCRNG
50 bool Rand_quick = TRUE;
54 * Current "value" of the "simple" RNG
60 * Current "index" for the "complex" RNG
65 * Current "state" table for the "complex" RNG
67 u32b Rand_state[RAND_DEG];
71 * Initialize the "complex" RNG using a new seed
73 void Rand_state_init(u32b seed)
80 /* Propagate the seed */
81 for (i = 1; i < RAND_DEG; i++) Rand_state[i] = LCRNG(Rand_state[i-1]);
83 /* Cycle the table ten times per degree */
84 for (i = 0; i < RAND_DEG * 10; i++)
86 /* Acquire the next index */
88 if (j == RAND_DEG) j = 0;
90 /* Update the table, extract an entry */
91 Rand_state[j] += Rand_state[Rand_place];
93 /* Advance the index */
100 * Extract a "random" number from 0 to m-1, via "modulus"
102 * Note that "m" should probably be less than 500000, or the
103 * results may be rather biased towards low values.
105 s32b Rand_mod(s32b m)
110 /* Hack -- simple case */
111 if (m <= 1) return (0);
113 /* Use the "simple" RNG */
116 /* Cycle the generator */
117 r = (Rand_value = LCRNG(Rand_value));
119 /* Mutate a 28-bit "random" number */
123 /* Use the "complex" RNG */
126 /* Acquire the next index */
128 if (j == RAND_DEG) j = 0;
130 /* Update the table, extract an entry */
131 r = (Rand_state[j] += Rand_state[Rand_place]);
133 /* Advance the index */
136 /* Extract a "random" number */
146 * Extract a "random" number from 0 to m-1, via "division"
148 * This method selects "random" 28-bit numbers, and then uses
149 * division to drop those numbers into "m" different partitions,
150 * plus a small non-partition to reduce bias, taking as the final
151 * value the first "good" partition that a number falls into.
153 * This method has no bias, and is much less affected by patterns
154 * in the "low" bits of the underlying RNG's.
156 s32b Rand_div(u32b m)
160 /* Hack -- simple case */
161 if (m <= 1) return (0);
164 n = (0x10000000 / m);
166 /* Use a simple RNG */
172 /* Cycle the generator */
173 r = (Rand_value = LCRNG(Rand_value));
175 /* Mutate a 28-bit "random" number */
183 /* Use a complex RNG */
191 /* Acquire the next index */
193 if (j == RAND_DEG) j = 0;
195 /* Update the table, extract an entry */
196 r = (Rand_state[j] += Rand_state[Rand_place]);
198 /* Hack -- extract a 28-bit "random" number */
201 /* Advance the index */
217 * The number of entries in the "randnor_table"
219 #define RANDNOR_NUM 256
222 * The standard deviation of the "randnor_table"
224 #define RANDNOR_STD 64
227 * The normal distribution table for the "randnor()" function (below)
229 static s16b randnor_table[RANDNOR_NUM] =
231 206, 613, 1022, 1430, 1838, 2245, 2652, 3058,
232 3463, 3867, 4271, 4673, 5075, 5475, 5874, 6271,
233 6667, 7061, 7454, 7845, 8234, 8621, 9006, 9389,
234 9770, 10148, 10524, 10898, 11269, 11638, 12004, 12367,
235 12727, 13085, 13440, 13792, 14140, 14486, 14828, 15168,
236 15504, 15836, 16166, 16492, 16814, 17133, 17449, 17761,
237 18069, 18374, 18675, 18972, 19266, 19556, 19842, 20124,
238 20403, 20678, 20949, 21216, 21479, 21738, 21994, 22245,
240 22493, 22737, 22977, 23213, 23446, 23674, 23899, 24120,
241 24336, 24550, 24759, 24965, 25166, 25365, 25559, 25750,
242 25937, 26120, 26300, 26476, 26649, 26818, 26983, 27146,
243 27304, 27460, 27612, 27760, 27906, 28048, 28187, 28323,
244 28455, 28585, 28711, 28835, 28955, 29073, 29188, 29299,
245 29409, 29515, 29619, 29720, 29818, 29914, 30007, 30098,
246 30186, 30272, 30356, 30437, 30516, 30593, 30668, 30740,
247 30810, 30879, 30945, 31010, 31072, 31133, 31192, 31249,
249 31304, 31358, 31410, 31460, 31509, 31556, 31601, 31646,
250 31688, 31730, 31770, 31808, 31846, 31882, 31917, 31950,
251 31983, 32014, 32044, 32074, 32102, 32129, 32155, 32180,
252 32205, 32228, 32251, 32273, 32294, 32314, 32333, 32352,
253 32370, 32387, 32404, 32420, 32435, 32450, 32464, 32477,
254 32490, 32503, 32515, 32526, 32537, 32548, 32558, 32568,
255 32577, 32586, 32595, 32603, 32611, 32618, 32625, 32632,
256 32639, 32645, 32651, 32657, 32662, 32667, 32672, 32677,
258 32682, 32686, 32690, 32694, 32698, 32702, 32705, 32708,
259 32711, 32714, 32717, 32720, 32722, 32725, 32727, 32729,
260 32731, 32733, 32735, 32737, 32739, 32740, 32742, 32743,
261 32745, 32746, 32747, 32748, 32749, 32750, 32751, 32752,
262 32753, 32754, 32755, 32756, 32757, 32757, 32758, 32758,
263 32759, 32760, 32760, 32761, 32761, 32761, 32762, 32762,
264 32763, 32763, 32763, 32764, 32764, 32764, 32764, 32765,
265 32765, 32765, 32765, 32766, 32766, 32766, 32766, 32767,
271 * Generate a random integer number of NORMAL distribution
273 * The table above is used to generate a pseudo-normal distribution,
274 * in a manner which is much faster than calling a transcendental
275 * function to calculate a true normal distribution.
277 * Basically, entry 64*N in the table above represents the number of
278 * times out of 32767 that a random variable with normal distribution
279 * will fall within N standard deviations of the mean. That is, about
280 * 68 percent of the time for N=1 and 95 percent of the time for N=2.
282 * The table above contains a "faked" final entry which allows us to
283 * pretend that all values in a normal distribution are strictly less
284 * than four standard deviations away from the mean. This results in
285 * "conservative" distribution of approximately 1/32768 values.
287 * Note that the binary search takes up to 16 quick iterations.
289 s16b randnor(int mean, int stand)
295 s16b high = RANDNOR_NUM;
298 if (stand < 1) return (mean);
300 /* Roll for probability */
301 tmp = (s16b)rand_int(32768);
306 int mid = (low + high) >> 1;
308 /* Move right if forced */
309 if (randnor_table[mid] < tmp)
314 /* Move left otherwise */
321 /* Convert the index into an offset */
322 offset = (long)stand * (long)low / RANDNOR_STD;
324 /* One half should be negative */
325 if (rand_int(100) < 50) return (mean - offset);
327 /* One half should be positive */
328 return (mean + offset);
334 * Generates damage for "2d6" style dice rolls
336 s16b damroll(int num, int sides)
339 for (i = 0; i < num; i++) sum += randint(sides);
345 * Same as above, but always maximal
347 s16b maxroll(int num, int sides)
349 return (num * sides);