Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
PcgRandom: Fix/improve documentation
  • Loading branch information
kwolekr committed Jun 4, 2016
1 parent dfbdb5b commit 8ed467d
Show file tree
Hide file tree
Showing 2 changed files with 23 additions and 12 deletions.
4 changes: 3 additions & 1 deletion doc/lua_api.txt
Expand Up @@ -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`
Expand Down
31 changes: 20 additions & 11 deletions src/noise.cpp
Expand Up @@ -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)
;

Expand Down

0 comments on commit 8ed467d

Please sign in to comment.