diff options
| -rw-r--r-- | doc/lua_api.txt | 4 | ||||
| -rw-r--r-- | src/noise.cpp | 31 |
2 files changed, 23 insertions, 12 deletions
diff --git a/doc/lua_api.txt b/doc/lua_api.txt index aa0d7e45d..f348f5103 100644 --- a/doc/lua_api.txt +++ b/doc/lua_api.txt @@ -2865,7 +2865,9 @@ It can be created via `PcgRandom(seed)` or `PcgRandom(seed, sequence)`. * `next()`: return next integer random number [`-2147483648`...`2147483647`] * `next(min, max)`: return next integer random number [`min`...`max`] * `rand_normal_dist(min, max, num_trials=6)`: return normally distributed random number [`min`...`max`] - * This is only a rough approximation of a normal distribution with mean=(max-min)/2 and variance=1 + * This is only a rough approximation of a normal distribution with: + * mean = (max - min) / 2, and + * variance = (((max - min + 1) ^ 2) - 1) / (12 * num_trials) * Increasing num_trials improves accuracy of the approximation ### `SecureRandom` diff --git a/src/noise.cpp b/src/noise.cpp index c57c98ccb..b918c9936 100644 --- a/src/noise.cpp +++ b/src/noise.cpp @@ -93,22 +93,31 @@ u32 PcgRandom::range(u32 bound) // If the bound is 0, we cover the whole RNG's range if (bound == 0) return next(); + /* - If the bound is not a multiple of the RNG's range, it may cause bias, - e.g. a RNG has a range from 0 to 3 and we take want a number 0 to 2. - Using rand() % 3, the number 0 would be twice as likely to appear. - With a very large RNG range, the effect becomes less prevalent but - still present. This can be solved by modifying the range of the RNG - to become a multiple of bound by dropping values above the a threshold. - In our example, threshold == 4 - 3 = 1 % 3 == 1, so reject 0, thus - making the range 3 with no bias. - - This loop looks dangerous, but will always terminate due to the - RNG's property of uniformity. + This is an optimization of the expression: + 0x100000000ull % bound + since 64-bit modulo operations typically much slower than 32. */ u32 threshold = -bound % bound; u32 r; + /* + If the bound is not a multiple of the RNG's range, it may cause bias, + e.g. a RNG has a range from 0 to 3 and we take want a number 0 to 2. + Using rand() % 3, the number 0 would be twice as likely to appear. + With a very large RNG range, the effect becomes less prevalent but + still present. + + This can be solved by modifying the range of the RNG to become a + multiple of bound by dropping values above the a threshold. + + In our example, threshold == 4 % 3 == 1, so reject values < 1 + (that is, 0), thus making the range == 3 with no bias. + + This loop may look dangerous, but will always terminate due to the + RNG's property of uniformity. + */ while ((r = next()) < threshold) ; |