src/z-rand.c

   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@phial.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  * "randint0()" 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
  40 /*
  41  * Random Number Generator -- Linear Congruent RNG
  42  */
  43 #define LCRNG(X)        ((X) * 1103515245 + 12345)
  44
  45
  46
  47 /*
  48  * Use the "simple" LCRNG
  49  */
  50 bool Rand_quick = TRUE;
  51
  52
  53 /*
  54  * Current "value" of the "simple" RNG
  55  */
  56 u32b Rand_value;
  57
  58
  59 /*
  60  * Current "index" for the "complex" RNG
  61  */
  62 u16b Rand_place;
  63
  64 /*
  65  * Current "state" table for the "complex" RNG
  66  */
  67 u32b Rand_state[RAND_DEG];
  68
  69
  70 /*
  71  * Initialize the "complex" RNG using a new seed
  72  */
  73 void Rand_state_init(u32b seed)
  74 {
  75         int i, j;
  76
  77         /* Seed the table */
  78         Rand_state[0] = seed;
  79
  80         /* Propagate the seed */
  81         for (i = 1; i < RAND_DEG; i++) Rand_state[i] = LCRNG(Rand_state[i-1]);
  82
  83         /* Cycle the table ten times per degree */
  84         for (i = 0; i < RAND_DEG * 10; i++)
  85         {
  86                 /* Acquire the next index */
  87                 j = Rand_place + 1;
  88                 if (j == RAND_DEG) j = 0;
  89
  90                 /* Update the table, extract an entry */
  91                 Rand_state[j] += Rand_state[Rand_place];
  92
  93                 /* Advance the index */
  94                 Rand_place = j;
  95         }
  96 }
  97
  98
  99 /*
 100  * Extract a "random" number from 0 to m-1, via "division"
 101  *
 102  * This method selects "random" 28-bit numbers, and then uses
 103  * division to drop those numbers into "m" different partitions,
 104  * plus a small non-partition to reduce bias, taking as the final
 105  * value the first "good" partition that a number falls into.
 106  *
 107  * This method has no bias, and is much less affected by patterns
 108  * in the "low" bits of the underlying RNG's.
 109  */
 110 s32b Rand_div(u32b m)
 111 {
 112         u32b r, n;
 113
 114         /* Hack -- simple case */
 115         if (m <= 1) return (0);
 116
 117         /* Partition size */
 118         n = (0x10000000 / m);
 119
 120         /* Use a simple RNG */
 121         if (Rand_quick)
 122         {
 123                 /* Wait for it */
 124                 while (1)
 125                 {
 126                         /* Cycle the generator */
 127                         r = (Rand_value = LCRNG(Rand_value));
 128
 129                         /* Mutate a 28-bit "random" number */
 130                         r = (r >> 4) / n;
 131
 132                         /* Done */
 133                         if (r < m) break;
 134                 }
 135         }
 136
 137         /* Use a complex RNG */
 138         else
 139         {
 140                 /* Wait for it */
 141                 while (1)
 142                 {
 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                         /* Hack -- extract a 28-bit "random" number */
 153                         r = (r >> 4) / n;
 154
 155                         /* Advance the index */
 156                         Rand_place = j;
 157
 158                         /* Done */
 159                         if (r < m) break;
 160                 }
 161         }
 162
 163         /* Use the value */
 164         return (r);
 165 }
 166
 167
 168
 169
 170 /*
 171  * The number of entries in the "randnor_table"
 172  */
 173 #define RANDNOR_NUM     256
 174
 175 /*
 176  * The standard deviation of the "randnor_table"
 177  */
 178 #define RANDNOR_STD     64
 179
 180 /*
 181  * The normal distribution table for the "randnor()" function (below)
 182  */
 183 static s16b randnor_table[RANDNOR_NUM] =
 184 {
 185         206,     613,    1022,    1430,         1838,    2245,    2652,    3058,
 186         3463,    3867,    4271,    4673,        5075,    5475,    5874,    6271,
 187         6667,    7061,    7454,    7845,        8234,    8621,    9006,    9389,
 188         9770,   10148,   10524,   10898,   11269,       11638,   12004,   12367,
 189         12727,   13085,   13440,   13792,   14140,      14486,   14828,   15168,
 190         15504,   15836,   16166,   16492,   16814,      17133,   17449,   17761,
 191         18069,   18374,   18675,   18972,   19266,      19556,   19842,   20124,
 192         20403,   20678,   20949,   21216,   21479,      21738,   21994,   22245,
 193
 194         22493,   22737,   22977,   23213,   23446,      23674,   23899,   24120,
 195         24336,   24550,   24759,   24965,   25166,      25365,   25559,   25750,
 196         25937,   26120,   26300,   26476,   26649,      26818,   26983,   27146,
 197         27304,   27460,   27612,   27760,   27906,      28048,   28187,   28323,
 198         28455,   28585,   28711,   28835,   28955,      29073,   29188,   29299,
 199         29409,   29515,   29619,   29720,   29818,      29914,   30007,   30098,
 200         30186,   30272,   30356,   30437,   30516,      30593,   30668,   30740,
 201         30810,   30879,   30945,   31010,   31072,      31133,   31192,   31249,
 202
 203         31304,   31358,   31410,   31460,   31509,      31556,   31601,   31646,
 204         31688,   31730,   31770,   31808,   31846,      31882,   31917,   31950,
 205         31983,   32014,   32044,   32074,   32102,      32129,   32155,   32180,
 206         32205,   32228,   32251,   32273,   32294,      32314,   32333,   32352,
 207         32370,   32387,   32404,   32420,   32435,      32450,   32464,   32477,
 208         32490,   32503,   32515,   32526,   32537,      32548,   32558,   32568,
 209         32577,   32586,   32595,   32603,   32611,      32618,   32625,   32632,
 210         32639,   32645,   32651,   32657,   32662,      32667,   32672,   32677,
 211
 212         32682,   32686,   32690,   32694,   32698,      32702,   32705,   32708,
 213         32711,   32714,   32717,   32720,   32722,      32725,   32727,   32729,
 214         32731,   32733,   32735,   32737,   32739,      32740,   32742,   32743,
 215         32745,   32746,   32747,   32748,   32749,      32750,   32751,   32752,
 216         32753,   32754,   32755,   32756,   32757,      32757,   32758,   32758,
 217         32759,   32760,   32760,   32761,   32761,      32761,   32762,   32762,
 218         32763,   32763,   32763,   32764,   32764,      32764,   32764,   32765,
 219         32765,   32765,   32765,   32766,   32766,      32766,   32766,   32767,
 220 };
 221
 222
 223
 224 /*
 225  * Generate a random integer number of NORMAL distribution
 226  *
 227  * The table above is used to generate a pseudo-normal distribution,
 228  * in a manner which is much faster than calling a transcendental
 229  * function to calculate a true normal distribution.
 230  *
 231  * Basically, entry 64*N in the table above represents the number of
 232  * times out of 32767 that a random variable with normal distribution
 233  * will fall within N standard deviations of the mean.  That is, about
 234  * 68 percent of the time for N=1 and 95 percent of the time for N=2.
 235  *
 236  * The table above contains a "faked" final entry which allows us to
 237  * pretend that all values in a normal distribution are strictly less
 238  * than four standard deviations away from the mean.  This results in
 239  * "conservative" distribution of approximately 1/32768 values.
 240  *
 241  * Note that the binary search takes up to 16 quick iterations.
 242  */
 243 s16b randnor(int mean, int stand)
 244 {
 245         s16b tmp;
 246         s16b offset;
 247
 248         s16b low = 0;
 249         s16b high = RANDNOR_NUM;
 250
 251         /* Paranoia */
 252         if (stand < 1) return (mean);
 253
 254         /* Roll for probability */
 255         tmp = (s16b)randint0(32768);
 256
 257         /* Binary Search */
 258         while (low < high)
 259         {
 260                 int mid = (low + high) >> 1;
 261
 262                 /* Move right if forced */
 263                 if (randnor_table[mid] < tmp)
 264                 {
 265                         low = mid + 1;
 266                 }
 267
 268                 /* Move left otherwise */
 269                 else
 270                 {
 271                         high = mid;
 272                 }
 273         }
 274
 275         /* Convert the index into an offset */
 276         offset = (long)stand * (long)low / RANDNOR_STD;
 277
 278         /* One half should be negative */
 279         if (randint0(100) < 50) return (mean - offset);
 280
 281         /* One half should be positive */
 282         return (mean + offset);
 283 }
 284
 285
 286
 287 /*
 288  * Generates damage for "2d6" style dice rolls
 289  */
 290 s16b damroll(int num, int sides)
 291 {
 292         int i, sum = 0;
 293         for (i = 0; i < num; i++) sum += randint1(sides);
 294         return (sum);
 295 }
 296
 297
 298 /*
 299  * Same as above, but always maximal
 300  */
 301 s16b maxroll(int num, int sides)
 302 {
 303         return (num * sides);
 304 }
 305
 306
 307