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         123456789,
  78         362436069,
  79         521288629,
  80         88675123,
  81 };
  82
  83
  84 /*
  85  * Initialize the "complex" RNG using a new seed
  86  */
  87 void Rand_state_init(u32b seed)
  88 {
  89         int i;
  90
  91         /* Initialize Xorshift Algorithm RNG */
  92         for (i = 1; i <= 4; ++ i) {
  93                 seed = 1812433253UL * (seed ^ (seed >> 30)) + i;
  94                 Rand_state[i-1] = seed;
  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         /* Use a simple RNG */
 118         if (Rand_quick)
 119         {
 120                 /* Partition size */
 121                 n = (0x10000000 / m);
 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                 /* Xorshift Algorithm RNG */
 141                 u32b t = Rand_state[0] ^ (Rand_state[0] << 11);
 142
 143                 Rand_state[0] = Rand_state[1];
 144                 Rand_state[1] = Rand_state[2];
 145                 Rand_state[2] = Rand_state[3];
 146
 147                 Rand_state[3] = (Rand_state[3] ^ (Rand_state[3] >> 19)) ^ (t ^ (t >> 8));
 148
 149                 r = Rand_state[3] % m;
 150         }
 151
 152         /* Use the value */
 153         return (r);
 154 }
 155
 156
 157
 158
 159 /*
 160  * The number of entries in the "randnor_table"
 161  */
 162 #define RANDNOR_NUM     256
 163
 164 /*
 165  * The standard deviation of the "randnor_table"
 166  */
 167 #define RANDNOR_STD     64
 168
 169 /*
 170  * The normal distribution table for the "randnor()" function (below)
 171  */
 172 static s16b randnor_table[RANDNOR_NUM] =
 173 {
 174         206,     613,    1022,    1430,         1838,    2245,    2652,    3058,
 175         3463,    3867,    4271,    4673,        5075,    5475,    5874,    6271,
 176         6667,    7061,    7454,    7845,        8234,    8621,    9006,    9389,
 177         9770,   10148,   10524,   10898,   11269,       11638,   12004,   12367,
 178         12727,   13085,   13440,   13792,   14140,      14486,   14828,   15168,
 179         15504,   15836,   16166,   16492,   16814,      17133,   17449,   17761,
 180         18069,   18374,   18675,   18972,   19266,      19556,   19842,   20124,
 181         20403,   20678,   20949,   21216,   21479,      21738,   21994,   22245,
 182
 183         22493,   22737,   22977,   23213,   23446,      23674,   23899,   24120,
 184         24336,   24550,   24759,   24965,   25166,      25365,   25559,   25750,
 185         25937,   26120,   26300,   26476,   26649,      26818,   26983,   27146,
 186         27304,   27460,   27612,   27760,   27906,      28048,   28187,   28323,
 187         28455,   28585,   28711,   28835,   28955,      29073,   29188,   29299,
 188         29409,   29515,   29619,   29720,   29818,      29914,   30007,   30098,
 189         30186,   30272,   30356,   30437,   30516,      30593,   30668,   30740,
 190         30810,   30879,   30945,   31010,   31072,      31133,   31192,   31249,
 191
 192         31304,   31358,   31410,   31460,   31509,      31556,   31601,   31646,
 193         31688,   31730,   31770,   31808,   31846,      31882,   31917,   31950,
 194         31983,   32014,   32044,   32074,   32102,      32129,   32155,   32180,
 195         32205,   32228,   32251,   32273,   32294,      32314,   32333,   32352,
 196         32370,   32387,   32404,   32420,   32435,      32450,   32464,   32477,
 197         32490,   32503,   32515,   32526,   32537,      32548,   32558,   32568,
 198         32577,   32586,   32595,   32603,   32611,      32618,   32625,   32632,
 199         32639,   32645,   32651,   32657,   32662,      32667,   32672,   32677,
 200
 201         32682,   32686,   32690,   32694,   32698,      32702,   32705,   32708,
 202         32711,   32714,   32717,   32720,   32722,      32725,   32727,   32729,
 203         32731,   32733,   32735,   32737,   32739,      32740,   32742,   32743,
 204         32745,   32746,   32747,   32748,   32749,      32750,   32751,   32752,
 205         32753,   32754,   32755,   32756,   32757,      32757,   32758,   32758,
 206         32759,   32760,   32760,   32761,   32761,      32761,   32762,   32762,
 207         32763,   32763,   32763,   32764,   32764,      32764,   32764,   32765,
 208         32765,   32765,   32765,   32766,   32766,      32766,   32766,   32767,
 209 };
 210
 211
 212
 213 /*
 214  * Generate a random integer number of NORMAL distribution
 215  *
 216  * The table above is used to generate a pseudo-normal distribution,
 217  * in a manner which is much faster than calling a transcendental
 218  * function to calculate a true normal distribution.
 219  *
 220  * Basically, entry 64*N in the table above represents the number of
 221  * times out of 32767 that a random variable with normal distribution
 222  * will fall within N standard deviations of the mean.  That is, about
 223  * 68 percent of the time for N=1 and 95 percent of the time for N=2.
 224  *
 225  * The table above contains a "faked" final entry which allows us to
 226  * pretend that all values in a normal distribution are strictly less
 227  * than four standard deviations away from the mean.  This results in
 228  * "conservative" distribution of approximately 1/32768 values.
 229  *
 230  * Note that the binary search takes up to 16 quick iterations.
 231  */
 232 s16b randnor(int mean, int stand)
 233 {
 234         s16b tmp;
 235         s16b offset;
 236
 237         s16b low = 0;
 238         s16b high = RANDNOR_NUM;
 239
 240         /* Paranoia */
 241         if (stand < 1) return (mean);
 242
 243         /* Roll for probability */
 244         tmp = (s16b)randint0(32768);
 245
 246         /* Binary Search */
 247         while (low < high)
 248         {
 249                 int mid = (low + high) >> 1;
 250
 251                 /* Move right if forced */
 252                 if (randnor_table[mid] < tmp)
 253                 {
 254                         low = mid + 1;
 255                 }
 256
 257                 /* Move left otherwise */
 258                 else
 259                 {
 260                         high = mid;
 261                 }
 262         }
 263
 264         /* Convert the index into an offset */
 265         offset = (long)stand * (long)low / RANDNOR_STD;
 266
 267         /* One half should be negative */
 268         if (randint0(100) < 50) return (mean - offset);
 269
 270         /* One half should be positive */
 271         return (mean + offset);
 272 }
 273
 274
 275
 276 /*
 277  * Generates damage for "2d6" style dice rolls
 278  */
 279 s16b damroll(int num, int sides)
 280 {
 281         int i, sum = 0;
 282         for (i = 0; i < num; i++) sum += randint1(sides);
 283         return (sum);
 284 }
 285
 286
 287 /*
 288  * Same as above, but always maximal
 289  */
 290 s16b maxroll(int num, int sides)
 291 {
 292         return (num * sides);
 293 }
 294
 295
 296 /*
 297  * Given a numerator and a denominator, supply a properly rounded result,
 298  * using the RNG to smooth out remainders.  -LM-
 299  */
 300 s32b div_round(s32b n, s32b d)
 301 {
 302         s32b tmp;
 303
 304         /* Refuse to divide by zero */
 305         if (!d) return (n);
 306
 307         /* Division */
 308         tmp = n / d;
 309
 310         /* Rounding */
 311         if ((ABS(n) % ABS(d)) > randint0(ABS(d)))
 312         {
 313                 /* Increase the absolute value */
 314                 if (n * d > 0L) tmp += 1L;
 315                 else            tmp -= 1L;
 316         }
 317
 318         /* Return */
 319         return (tmp);
 320 }
 321
 322
 323
 324
 325 /*
 326  * Extract a "random" number from 0 to m-1, using the "simple" RNG.
 327  *
 328  * This function should be used when generating random numbers in
 329  * "external" program parts like the main-*.c files.  It preserves
 330  * the current RNG state to prevent influences on game-play.
 331  *
 332  * Could also use rand() from <stdlib.h> directly. XXX XXX XXX
 333  */
 334 u32b Rand_simple(u32b m)
 335 {
 336         static bool initialized = FALSE;
 337         static u32b simple_rand_value;
 338         bool old_rand_quick;
 339         u32b old_rand_value;
 340         u32b result;
 341
 342
 343         /* Save RNG state */
 344         old_rand_quick = Rand_quick;
 345         old_rand_value = Rand_value;
 346
 347         /* Use "simple" RNG */
 348         Rand_quick = TRUE;
 349
 350         if (initialized)
 351         {
 352                 /* Use stored seed */
 353                 Rand_value = simple_rand_value;
 354         }
 355         else
 356         {
 357                 /* Initialize with new seed */
 358                 Rand_value = time(NULL);
 359                 initialized = TRUE;
 360         }
 361
 362         /* Get a random number */
 363         result = randint0(m);
 364
 365         /* Store the new seed */
 366         simple_rand_value = Rand_value;
 367
 368         /* Restore RNG state */
 369         Rand_quick = old_rand_quick;
 370         Rand_value = old_rand_value;
 371
 372         /* Use the value */
 373         return (result);
 374 }