OSDN Git Service

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