* automatically used instead of the "complex" RNG, and when you are
* done, you de-activate it via "Rand_quick = FALSE" or choose a new
* seed via "Rand_value = seed".
+ *
+ *
+ * RNG algorithm was fully rewritten. Upper comment is OLD.
*/
/*
- * Random Number Generator -- Linear Congruent RNG
+ * Currently unused
*/
-#define LCRNG(X) ((X) * 1103515245 + 12345)
-
-
+u16b Rand_place;
/*
- * Use the "simple" LCRNG
+ * Current "state" table for the RNG
+ * Only index 0 to 3 are used
*/
-bool Rand_quick = TRUE;
+u32b Rand_state[RAND_DEG] = {
+ 123456789,
+ 362436069,
+ 521288629,
+ 88675123,
+};
/*
- * Current "value" of the "simple" RNG
+ * Initialize Xorshift Algorithm state
*/
-u32b Rand_value;
+static void Rand_Xorshift_init(u32b seed, u32b* state)
+{
+ int i;
+ /* Initialize Xorshift Algorithm RNG */
+ for (i = 1; i <= 4; ++ i) {
+ seed = 1812433253UL * (seed ^ (seed >> 30)) + i;
+ state[i-1] = seed;
+ }
+}
/*
- * Current "index" for the "complex" RNG
+ * Xorshift Algorithm
*/
-u16b Rand_place;
+static u32b Rand_Xorshift(u32b* state)
+{
+ u32b t = state[0] ^ (state[0] << 11);
-/*
- * Current "state" table for the "complex" RNG
- */
-u32b Rand_state[RAND_DEG];
+ state[0] = state[1];
+ state[1] = state[2];
+ state[2] = state[3];
+
+ state[3] = (state[3] ^ (state[3] >> 19)) ^ (t ^ (t >> 8));
+ return state[3];
+}
/*
- * Initialize the "complex" RNG using a new seed
+ * Initialize the RNG using a new seed
*/
void Rand_state_init(u32b seed)
{
- int i, j;
-
- /* Seed the table */
- Rand_state[0] = seed;
+ Rand_Xorshift_init(seed, Rand_state);
+}
- /* Propagate the seed */
- for (i = 1; i < RAND_DEG; i++) Rand_state[i] = LCRNG(Rand_state[i-1]);
+/*
+ * Backup the RNG state
+ */
+void Rand_state_backup(u32b* backup_state)
+{
+ int i;
- /* Cycle the table ten times per degree */
- for (i = 0; i < RAND_DEG * 10; i++)
- {
- /* Acquire the next index */
- j = Rand_place + 1;
- if (j == RAND_DEG) j = 0;
+ for (i = 0; i < 4; ++ i) {
+ backup_state[i] = Rand_state[i];
+ }
+}
- /* Update the table, extract an entry */
- Rand_state[j] += Rand_state[Rand_place];
+/*
+ * Restore the RNG state
+ */
+void Rand_state_restore(u32b* backup_state)
+{
+ int i;
- /* Advance the index */
- Rand_place = j;
+ for (i = 0; i < 4; ++ i) {
+ Rand_state[i] = backup_state[i];
}
}
/*
* Extract a "random" number from 0 to m-1, via "division"
- *
- * This method selects "random" 28-bit numbers, and then uses
- * division to drop those numbers into "m" different partitions,
- * plus a small non-partition to reduce bias, taking as the final
- * value the first "good" partition that a number falls into.
- *
- * This method has no bias, and is much less affected by patterns
- * in the "low" bits of the underlying RNG's.
*/
s32b Rand_div(u32b m)
{
- u32b r, n;
-
/* Hack -- simple case */
if (m <= 1) return (0);
- /* Partition size */
- n = (0x10000000 / m);
-
- /* Use a simple RNG */
- if (Rand_quick)
- {
- /* Wait for it */
- while (1)
- {
- /* Cycle the generator */
- r = (Rand_value = LCRNG(Rand_value));
-
- /* Mutate a 28-bit "random" number */
- r = (r >> 4) / n;
-
- /* Done */
- if (r < m) break;
- }
- }
-
- /* Use a complex RNG */
- else
- {
- /* Wait for it */
- while (1)
- {
- int j;
-
- /* Acquire the next index */
- j = Rand_place + 1;
- if (j == RAND_DEG) j = 0;
-
- /* Update the table, extract an entry */
- r = (Rand_state[j] += Rand_state[Rand_place]);
-
- /* Hack -- extract a 28-bit "random" number */
- r = (r >> 4) / n;
-
- /* Advance the index */
- Rand_place = j;
-
- /* Done */
- if (r < m) break;
- }
- }
-
/* Use the value */
- return (r);
+ return Rand_Xorshift(Rand_state) % m;
}
/*
- * Extract a "random" number from 0 to m-1, using the "simple" RNG.
+ * Extract a "random" number from 0 to m-1, using the RNG.
*
* This function should be used when generating random numbers in
* "external" program parts like the main-*.c files. It preserves
*
* Could also use rand() from <stdlib.h> directly. XXX XXX XXX
*/
-u32b Rand_simple(u32b m)
+u32b Rand_external(u32b m)
{
static bool initialized = FALSE;
- static u32b simple_rand_value;
- bool old_rand_quick;
- u32b old_rand_value;
- u32b result;
-
-
- /* Save RNG state */
- old_rand_quick = Rand_quick;
- old_rand_value = Rand_value;
+ static u32b Rand_state_external[4];
- /* Use "simple" RNG */
- Rand_quick = TRUE;
-
- if (initialized)
- {
- /* Use stored seed */
- Rand_value = simple_rand_value;
- }
- else
+ if (!initialized)
{
/* Initialize with new seed */
- Rand_value = time(NULL);
+ u32b seed = time(NULL);
+ Rand_Xorshift_init(seed, Rand_state_external);
initialized = TRUE;
}
- /* Get a random number */
- result = randint0(m);
-
- /* Store the new seed */
- simple_rand_value = Rand_value;
-
- /* Restore RNG state */
- Rand_quick = old_rand_quick;
- Rand_value = old_rand_value;
-
- /* Use the value */
- return (result);
+ return Rand_Xorshift(Rand_state_external) % m;
}
OSDN Git Service
