Generate Random Number outside Bounds:

Question

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>RAND_MAX and 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.

Edit:

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.

Answer 1

For the sake of your example, let's say RAND_MAX=12 and i=17. Then do the following procedure: Choose two random numbers $r_1,r_2$ and combine them to a single random number uniformly distributed in $[0,144)$ by computing $r=r_1*12+r_2$. This is of course the wrong interval. You get a uniformly distributed random number in $[0,17)$ by repeating this process until you end up with a number $r$ in this interval; in other words, every time you get a random number $r\ge i$, you discard it and just try again. This guarantees that you end up with a uniform random number.

Answer 2

Instead of fixing the provided generator use a reasonable modern choice. It will be faster and have better statistical quality. Possible examples include the various variants of xorshift+, xorshift* and PCG.

To directly respond to the question asked. You can generate a sample, mask out the maximal power of two bits available, generate another and shift that and bit or in the previous. For a non power of two 'n' perform a rejection method.

EDIT 2: So using a 64-bit xorshift+ to generate a 64-bit uniform sequence might look like this:

// multiple 'state' blocks to allow for friendly multi-threading
typedef struct {
  uint64_t s0;
  uint64_t s1;
} rng_state;

// get 64-bits
inline uint64_t rng_next(rng_state_t* s)
{
  uint64_t s1 = s->s0;
  uint64_t s0 = s->s1;

  s->s0 = s0;
  s1   ^= s1 << 23;
  s->s1 = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5);

  return s->s1 + s0; 
}

Trying to "patch-up" random, given simplifying assumptions that it returns a uniform an N-bit number and extending it to 2N-bits:

inline uint64_t rng_next() {
   uint64_t r0 = random();
   return (r0 << RANDOM_BITS) | random();
 }

Taking a quick peek at source it looks like the current version of (say) glibc will return 31-bits and by default it uses a power-of-two LCG (very low quality). The end result of patching up is significantly lower quality and significantly higher runtime cost.

NOTE: All code is typed in post and probably doesn't even compile.