Say I have a random number generator that generates a number within
[0, RAND_MAX], and
RAND_MAX < UINT_MAX.
How do I generate a random number within
[0, i] such that
i<UINT_MAX, while maintaining an even distribution, and without exceeding
UINT_MAX in any calculations?
The first attempt is to split the range into
n equal parts such that
i mod n == 0 by finding the least denominator of
i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if
i is prime:
0 1 2 3 4 5 6 |___| |_____|
The second attempt is to split the range into two parts
a = [0, floor(i/2)] and
b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:
g = gcd(length(a), length(b)) if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g random(0, floor(i/2)) else random(floor(i/2)+1, i)
Given the following range, the right sub-range is selected twice as often as the left sub-range:
0 1 2 3 4 5 |_| |_____|
Unfortunately the first call to
random() may recurse forever if
gcd() is ever one.
The final attempt is to correct the distribution skew introduced by splitting a range of odd length:
if random(1) if random(1) random(0, floor(i/2)) else random(floor(i/2) + 1, i) else if random(1) random(0, floor(i/2) - 1) else random(floor(i/2), i)
Which probably doesn't work.
For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:
# triangular distribution: random(a, floor(b/2)) + random(a, b - floor(b/2))
Edit (on accept):
The two answers I considered are both of high quality. This answer considers RNGs on a per-digit or per-bit basis. The accepted answers consider RNGs numerically, without considering digits or bits. In both cases, the comments are important to read.
I've also posted a follow-up question Maintain Uniform Distribution across Subranges.