4 * Copyright (c) 1997 Ben Harrison, and others
6 * This software may be copied and distributed for educational, research,
7 * and not for profit purposes provided that this copyright and statement
8 * are included in all such copies. Other copyrights may also apply.
12 /* Purpose: a simple random number generator -BEN- */
20 * Angband 2.7.9 introduced a new (optimized) random number generator,
21 * based loosely on the old "random.c" from Berkeley but with some major
22 * optimizations and algorithm changes. See below for more details.
24 * Code by myself (benh@phial.com) and Randy (randy@stat.tamu.edu).
26 * This code provides (1) a "decent" RNG, based on the "BSD-degree-63-RNG"
27 * used in Angband 2.7.8, but rather optimized, and (2) a "simple" RNG,
28 * based on the simple "LCRNG" currently used in Angband, but "corrected"
29 * to give slightly better values. Both of these are available in two
30 * flavors, first, the simple "mod" flavor, which is fast, but slightly
31 * biased at high values, and second, the simple "div" flavor, which is
32 * less fast (and potentially non-terminating) but which is not biased
33 * and is much less subject to low-bit-non-randomness problems.
35 * You can select your favorite flavor by proper definition of the
36 * "randint0()" macro in the "defines.h" file.
38 * Note that, in Angband 2.8.0, the "state" table will be saved in the
39 * savefile, so a special "initialization" phase will be necessary.
41 * Note the use of the "simple" RNG, first you activate it via
42 * "Rand_quick = TRUE" and "Rand_value = seed" and then it is used
43 * automatically used instead of the "complex" RNG, and when you are
44 * done, you de-activate it via "Rand_quick = FALSE" or choose a new
45 * seed via "Rand_value = seed".
48 * RNG algorithm was fully rewritten. Upper comment is OLD.
58 * Current "state" table for the RNG
59 * Only index 0 to 3 are used
61 u32b Rand_state[RAND_DEG] = {
70 * Initialize Xorshift Algorithm state
72 static void Rand_Xorshift_init(u32b seed, u32b* state)
76 /* Initialize Xorshift Algorithm RNG */
77 for (i = 1; i <= 4; ++ i) {
78 seed = 1812433253UL * (seed ^ (seed >> 30)) + i;
86 static u32b Rand_Xorshift(u32b* state)
88 u32b t = state[0] ^ (state[0] << 11);
94 state[3] = (state[3] ^ (state[3] >> 19)) ^ (t ^ (t >> 8));
100 * Initialize the RNG using a new seed
102 void Rand_state_init(u32b seed)
104 Rand_Xorshift_init(seed, Rand_state);
108 * Backup the RNG state
110 void Rand_state_backup(u32b* backup_state)
114 for (i = 0; i < 4; ++ i) {
115 backup_state[i] = Rand_state[i];
120 * Restore the RNG state
122 void Rand_state_restore(u32b* backup_state)
126 for (i = 0; i < 4; ++ i) {
127 Rand_state[i] = backup_state[i];
133 * Extract a "random" number from 0 to m-1, via "division"
135 s32b Rand_div(u32b m)
137 /* Hack -- simple case */
138 if (m <= 1) return (0);
141 return Rand_Xorshift(Rand_state) % m;
148 * The number of entries in the "randnor_table"
150 #define RANDNOR_NUM 256
153 * The standard deviation of the "randnor_table"
155 #define RANDNOR_STD 64
158 * The normal distribution table for the "randnor()" function (below)
160 static s16b randnor_table[RANDNOR_NUM] =
162 206, 613, 1022, 1430, 1838, 2245, 2652, 3058,
163 3463, 3867, 4271, 4673, 5075, 5475, 5874, 6271,
164 6667, 7061, 7454, 7845, 8234, 8621, 9006, 9389,
165 9770, 10148, 10524, 10898, 11269, 11638, 12004, 12367,
166 12727, 13085, 13440, 13792, 14140, 14486, 14828, 15168,
167 15504, 15836, 16166, 16492, 16814, 17133, 17449, 17761,
168 18069, 18374, 18675, 18972, 19266, 19556, 19842, 20124,
169 20403, 20678, 20949, 21216, 21479, 21738, 21994, 22245,
171 22493, 22737, 22977, 23213, 23446, 23674, 23899, 24120,
172 24336, 24550, 24759, 24965, 25166, 25365, 25559, 25750,
173 25937, 26120, 26300, 26476, 26649, 26818, 26983, 27146,
174 27304, 27460, 27612, 27760, 27906, 28048, 28187, 28323,
175 28455, 28585, 28711, 28835, 28955, 29073, 29188, 29299,
176 29409, 29515, 29619, 29720, 29818, 29914, 30007, 30098,
177 30186, 30272, 30356, 30437, 30516, 30593, 30668, 30740,
178 30810, 30879, 30945, 31010, 31072, 31133, 31192, 31249,
180 31304, 31358, 31410, 31460, 31509, 31556, 31601, 31646,
181 31688, 31730, 31770, 31808, 31846, 31882, 31917, 31950,
182 31983, 32014, 32044, 32074, 32102, 32129, 32155, 32180,
183 32205, 32228, 32251, 32273, 32294, 32314, 32333, 32352,
184 32370, 32387, 32404, 32420, 32435, 32450, 32464, 32477,
185 32490, 32503, 32515, 32526, 32537, 32548, 32558, 32568,
186 32577, 32586, 32595, 32603, 32611, 32618, 32625, 32632,
187 32639, 32645, 32651, 32657, 32662, 32667, 32672, 32677,
189 32682, 32686, 32690, 32694, 32698, 32702, 32705, 32708,
190 32711, 32714, 32717, 32720, 32722, 32725, 32727, 32729,
191 32731, 32733, 32735, 32737, 32739, 32740, 32742, 32743,
192 32745, 32746, 32747, 32748, 32749, 32750, 32751, 32752,
193 32753, 32754, 32755, 32756, 32757, 32757, 32758, 32758,
194 32759, 32760, 32760, 32761, 32761, 32761, 32762, 32762,
195 32763, 32763, 32763, 32764, 32764, 32764, 32764, 32765,
196 32765, 32765, 32765, 32766, 32766, 32766, 32766, 32767,
202 * Generate a random integer number of NORMAL distribution
204 * The table above is used to generate a pseudo-normal distribution,
205 * in a manner which is much faster than calling a transcendental
206 * function to calculate a true normal distribution.
208 * Basically, entry 64*N in the table above represents the number of
209 * times out of 32767 that a random variable with normal distribution
210 * will fall within N standard deviations of the mean. That is, about
211 * 68 percent of the time for N=1 and 95 percent of the time for N=2.
213 * The table above contains a "faked" final entry which allows us to
214 * pretend that all values in a normal distribution are strictly less
215 * than four standard deviations away from the mean. This results in
216 * "conservative" distribution of approximately 1/32768 values.
218 * Note that the binary search takes up to 16 quick iterations.
220 s16b randnor(int mean, int stand)
226 s16b high = RANDNOR_NUM;
229 if (stand < 1) return (mean);
231 /* Roll for probability */
232 tmp = (s16b)randint0(32768);
237 int mid = (low + high) >> 1;
239 /* Move right if forced */
240 if (randnor_table[mid] < tmp)
245 /* Move left otherwise */
252 /* Convert the index into an offset */
253 offset = (long)stand * (long)low / RANDNOR_STD;
255 /* One half should be negative */
256 if (randint0(100) < 50) return (mean - offset);
258 /* One half should be positive */
259 return (mean + offset);
265 * Generates damage for "2d6" style dice rolls
267 s16b damroll(int num, int sides)
270 for (i = 0; i < num; i++) sum += randint1(sides);
276 * Same as above, but always maximal
278 s16b maxroll(int num, int sides)
280 return (num * sides);
285 * Given a numerator and a denominator, supply a properly rounded result,
286 * using the RNG to smooth out remainders. -LM-
288 s32b div_round(s32b n, s32b d)
292 /* Refuse to divide by zero */
299 if ((ABS(n) % ABS(d)) > randint0(ABS(d)))
301 /* Increase the absolute value */
302 if (n * d > 0L) tmp += 1L;
314 * Extract a "random" number from 0 to m-1, using the RNG.
316 * This function should be used when generating random numbers in
317 * "external" program parts like the main-*.c files. It preserves
318 * the current RNG state to prevent influences on game-play.
320 * Could also use rand() from <stdlib.h> directly. XXX XXX XXX
322 u32b Rand_external(u32b m)
324 static bool initialized = FALSE;
325 static u32b Rand_state_external[4];
329 /* Initialize with new seed */
330 u32b seed = time(NULL);
331 Rand_Xorshift_init(seed, Rand_state_external);
335 return Rand_Xorshift(Rand_state_external) % m;