Change random number generation method to Xorshift (from hengband)
XAngband/trunk/src/z-rand.c (diff)
XAngband/trunk/src/z-rand.h (diff)| @@ -64,7 +64,12 @@ | ||
| 64 | 64 | /* |
| 65 | 65 | * Current "state" table for the "complex" RNG |
| 66 | 66 | */ |
| 67 | -u32b Rand_state[RAND_DEG]; | |
| 67 | +u32b Rand_state[RAND_DEG] = { | |
| 68 | + 123456789, | |
| 69 | + 362436069, | |
| 70 | + 521288629, | |
| 71 | + 88675123, | |
| 72 | +}; | |
| 68 | 73 | |
| 69 | 74 | /* |
| 70 | 75 | * Current "state" of the quick RNG - don't bother to put this in save files. |
| @@ -77,77 +82,16 @@ | ||
| 77 | 82 | */ |
| 78 | 83 | void Rand_state_init(u32b seed) |
| 79 | 84 | { |
| 80 | - int i, j; | |
| 85 | + int i; | |
| 81 | 86 | |
| 82 | - /* Seed the table */ | |
| 83 | - Rand_state[0] = seed; | |
| 84 | - | |
| 85 | - /* Propagate the seed */ | |
| 86 | - for (i = 1; i < RAND_DEG; i++) Rand_state[i] = LCRNG(Rand_state[i-1]); | |
| 87 | - | |
| 88 | - /* Cycle the table ten times per degree */ | |
| 89 | - for (i = 0; i < RAND_DEG * 10; i++) | |
| 90 | - { | |
| 91 | - /* Acquire the next index */ | |
| 92 | - j = Rand_place + 1; | |
| 93 | - if (j == RAND_DEG) j = 0; | |
| 94 | - | |
| 95 | - /* Update the table, extract an entry */ | |
| 96 | - Rand_state[j] += Rand_state[Rand_place]; | |
| 97 | - | |
| 98 | - /* Advance the index */ | |
| 99 | - Rand_place = j; | |
| 100 | - } | |
| 87 | + /* Initialize Xorshift Algorithm RNG */ | |
| 88 | + for (i = 1; i <= 4; ++ i) { | |
| 89 | + seed = 1812433253UL * (seed ^ (seed >> 30)) + i; | |
| 90 | + Rand_state[i-1] = seed; } | |
| 101 | 91 | } |
| 102 | 92 | |
| 103 | 93 | |
| 104 | 94 | /* |
| 105 | - * Extract a "random" number from 0 to m-1, via "modulus" | |
| 106 | - * | |
| 107 | - * Note that "m" should probably be less than 500000, or the | |
| 108 | - * results may be rather biased towards low values. | |
| 109 | - */ | |
| 110 | -s32b Rand_mod(s32b m) | |
| 111 | -{ | |
| 112 | - int j; | |
| 113 | - u32b r; | |
| 114 | - | |
| 115 | - /* Hack -- simple case */ | |
| 116 | - if (m <= 1) return (0); | |
| 117 | - | |
| 118 | - /* Use the "simple" RNG */ | |
| 119 | - if (Rand_quick) | |
| 120 | - { | |
| 121 | - /* Cycle the generator */ | |
| 122 | - r = (Rand_value = LCRNG(Rand_value)); | |
| 123 | - | |
| 124 | - /* Mutate a 28-bit "random" number */ | |
| 125 | - r = ((r >> 4) % m); | |
| 126 | - } | |
| 127 | - | |
| 128 | - /* Use the "complex" RNG */ | |
| 129 | - else | |
| 130 | - { | |
| 131 | - /* Acquire the next index */ | |
| 132 | - j = Rand_place + 1; | |
| 133 | - if (j == RAND_DEG) j = 0; | |
| 134 | - | |
| 135 | - /* Update the table, extract an entry */ | |
| 136 | - r = (Rand_state[j] += Rand_state[Rand_place]); | |
| 137 | - | |
| 138 | - /* Advance the index */ | |
| 139 | - Rand_place = j; | |
| 140 | - | |
| 141 | - /* Extract a "random" number */ | |
| 142 | - r = ((r >> 4) % m); | |
| 143 | - } | |
| 144 | - | |
| 145 | - /* Use the value */ | |
| 146 | - return (r); | |
| 147 | -} | |
| 148 | - | |
| 149 | - | |
| 150 | -/* | |
| 151 | 95 | * Extract a "random" number from 0 to m-1, via "division" |
| 152 | 96 | * |
| 153 | 97 | * This method selects "random" 28-bit numbers, and then uses |
| @@ -165,12 +109,12 @@ | ||
| 165 | 109 | /* Hack -- simple case */ |
| 166 | 110 | if (m <= 1) return (0); |
| 167 | 111 | |
| 168 | - /* Partition size */ | |
| 169 | - n = (0x10000000 / m); | |
| 170 | - | |
| 171 | 112 | /* Use a simple RNG */ |
| 172 | 113 | if (Rand_quick) |
| 173 | 114 | { |
| 115 | + /* Partition size */ | |
| 116 | + n = (0x10000000 / m); | |
| 117 | + | |
| 174 | 118 | /* Wait for it */ |
| 175 | 119 | while (1) |
| 176 | 120 | { |
| @@ -188,27 +132,16 @@ | ||
| 188 | 132 | /* Use a complex RNG */ |
| 189 | 133 | else |
| 190 | 134 | { |
| 191 | - /* Wait for it */ | |
| 192 | - while (1) | |
| 193 | - { | |
| 194 | - int j; | |
| 135 | + /* Xorshift Algorithm RNG */ | |
| 136 | + u32b t = Rand_state[0] ^ (Rand_state[0] << 11); | |
| 195 | 137 | |
| 196 | - /* Acquire the next index */ | |
| 197 | - j = Rand_place + 1; | |
| 198 | - if (j == RAND_DEG) j = 0; | |
| 138 | + Rand_state[0] = Rand_state[1]; | |
| 139 | + Rand_state[1] = Rand_state[2]; | |
| 140 | + Rand_state[2] = Rand_state[3]; | |
| 199 | 141 | |
| 200 | - /* Update the table, extract an entry */ | |
| 201 | - r = (Rand_state[j] += Rand_state[Rand_place]); | |
| 142 | + Rand_state[3] = (Rand_state[3] ^ (Rand_state[3] >> 19)) ^ (t ^ (t >> 8)); | |
| 202 | 143 | |
| 203 | - /* Hack -- extract a 28-bit "random" number */ | |
| 204 | - r = (r >> 4) / n; | |
| 205 | - | |
| 206 | - /* Advance the index */ | |
| 207 | - Rand_place = j; | |
| 208 | - | |
| 209 | - /* Done */ | |
| 210 | - if (r < m) break; | |
| 211 | - } | |
| 144 | + r = Rand_state[3] % m; | |
| 212 | 145 | } |
| 213 | 146 | |
| 214 | 147 | /* Use the value */ |
| @@ -90,7 +90,6 @@ | ||
| 90 | 90 | /**** Available Functions ****/ |
| 91 | 91 | |
| 92 | 92 | extern void Rand_state_init(u32b seed); |
| 93 | -extern s32b Rand_mod(s32b m); | |
| 94 | 93 | extern s32b Rand_div(u32b m); |
| 95 | 94 | extern s16b randnor(int mean, int stand); |
| 96 | 95 | extern s16b damroll(int num, int sides); |
