Return to Revisions

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.