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