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  * "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
  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 "modulus"
 101  *
 102  * Note that "m" should probably be less than 500000, or the
 103  * results may be rather biased towards low values.
 104  */
 105 s32b Rand_mod(s32b m)
 106 {
 107         int j;
 108         u32b r;
 109
 110         /* Hack -- simple case */
 111         if (m <= 1) return (0);
 112
 113         /* Use the "simple" RNG */
 114         if (Rand_quick)
 115         {
 116                 /* Cycle the generator */
 117                 r = (Rand_value = LCRNG(Rand_value));
 118
 119                 /* Mutate a 28-bit "random" number */
 120                 r = ((r >> 4) % m);
 121         }
 122
 123         /* Use the "complex" RNG */
 124         else
 125         {
 126                 /* Acquire the next index */
 127                 j = Rand_place + 1;
 128                 if (j == RAND_DEG) j = 0;
 129
 130                 /* Update the table, extract an entry */
 131                 r = (Rand_state[j] += Rand_state[Rand_place]);
 132
 133                 /* Advance the index */
 134                 Rand_place = j;
 135
 136                 /* Extract a "random" number */
 137                 r = ((r >> 4) % m);
 138         }
 139
 140         /* Use the value */
 141         return (r);
 142 }
 143
 144
 145 /*
 146  * Extract a "random" number from 0 to m-1, via "division"
 147  *
 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.
 152  *
 153  * This method has no bias, and is much less affected by patterns
 154  * in the "low" bits of the underlying RNG's.
 155  */
 156 s32b Rand_div(u32b m)
 157 {
 158         u32b r, n;
 159
 160         /* Hack -- simple case */
 161         if (m <= 1) return (0);
 162
 163         /* Partition size */
 164         n = (0x10000000 / m);
 165
 166         /* Use a simple RNG */
 167         if (Rand_quick)
 168         {
 169                 /* Wait for it */
 170                 while (1)
 171                 {
 172                         /* Cycle the generator */
 173                         r = (Rand_value = LCRNG(Rand_value));
 174
 175                         /* Mutate a 28-bit "random" number */
 176                         r = (r >> 4) / n;
 177
 178                         /* Done */
 179                         if (r < m) break;
 180                 }
 181         }
 182
 183         /* Use a complex RNG */
 184         else
 185         {
 186                 /* Wait for it */
 187                 while (1)
 188                 {
 189                         int j;
 190
 191                         /* Acquire the next index */
 192                         j = Rand_place + 1;
 193                         if (j == RAND_DEG) j = 0;
 194
 195                         /* Update the table, extract an entry */
 196                         r = (Rand_state[j] += Rand_state[Rand_place]);
 197
 198                         /* Hack -- extract a 28-bit "random" number */
 199                         r = (r >> 4) / n;
 200
 201                         /* Advance the index */
 202                         Rand_place = j;
 203
 204                         /* Done */
 205                         if (r < m) break;
 206                 }
 207         }
 208
 209         /* Use the value */
 210         return (r);
 211 }
 212
 213
 214
 215
 216 /*
 217  * The number of entries in the "randnor_table"
 218  */
 219 #define RANDNOR_NUM     256
 220
 221 /*
 222  * The standard deviation of the "randnor_table"
 223  */
 224 #define RANDNOR_STD     64
 225
 226 /*
 227  * The normal distribution table for the "randnor()" function (below)
 228  */
 229 static s16b randnor_table[RANDNOR_NUM] =
 230 {
 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,
 239
 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,
 248
 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,
 257
 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,
 266 };
 267
 268
 269
 270 /*
 271  * Generate a random integer number of NORMAL distribution
 272  *
 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.
 276  *
 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.
 281  *
 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.
 286  *
 287  * Note that the binary search takes up to 16 quick iterations.
 288  */
 289 s16b randnor(int mean, int stand)
 290 {
 291         s16b tmp;
 292         s16b offset;
 293
 294         s16b low = 0;
 295         s16b high = RANDNOR_NUM;
 296
 297         /* Paranoia */
 298         if (stand < 1) return (mean);
 299
 300         /* Roll for probability */
 301         tmp = (s16b)rand_int(32768);
 302
 303         /* Binary Search */
 304         while (low < high)
 305         {
 306                 int mid = (low + high) >> 1;
 307
 308                 /* Move right if forced */
 309                 if (randnor_table[mid] < tmp)
 310                 {
 311                         low = mid + 1;
 312                 }
 313
 314                 /* Move left otherwise */
 315                 else
 316                 {
 317                         high = mid;
 318                 }
 319         }
 320
 321         /* Convert the index into an offset */
 322         offset = (long)stand * (long)low / RANDNOR_STD;
 323
 324         /* One half should be negative */
 325         if (rand_int(100) < 50) return (mean - offset);
 326
 327         /* One half should be positive */
 328         return (mean + offset);
 329 }
 330
 331
 332
 333 /*
 334  * Generates damage for "2d6" style dice rolls
 335  */
 336 s16b damroll(int num, int sides)
 337 {
 338         int i, sum = 0;
 339         for (i = 0; i < num; i++) sum += randint(sides);
 340         return (sum);
 341 }
 342
 343
 344 /*
 345  * Same as above, but always maximal
 346  */
 347 s16b maxroll(int num, int sides)
 348 {
 349         return (num * sides);
 350 }
 351
 352
 353