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 }