Generating 64-bit Random Numbers in a Given Range

There are good standard ways of generating 32-bit random numbers. If you need something really simple, it is possible for example to generate decent random numbers with a Linear Congruential Random Number Generator:

class KxuLCRand
{
public:
   KxuLCRand( u32 seed = 555 ) { setSeed( seed ); }
   void setSeed( u32 seed ) { if ( !seed ) seed = 0x333; mState = seed | 0x1; }
   u32 getRandom() { mState *= 69069; return mState; }

private:
   u32 mState;
};

For generators for better statistical properties – such as for encryption or compression – you could use something like a Mersenne Twister. While in principle these generators could be written to generate 64-bit results natively, for efficiency they are implemented using 32-bit registers. Using 64-bit values for random number generation generally requires multiplying two 64 bit values and storing 128-bit quantities with all the complications that entails.

Generating 64-bit random numbers uniformly, across the entire 64-bit range is simple. Generate two 32 bit numbers, shift one up by 32 bits, and ‘or’ them together:

u64 getRandom64()
{
   u64 low    = lcng.getRandom();
   u64 high   = lcng.getRandom();
   u64 random = low | (high << 32);
   return random;
}

Generating 32-bit numbers in a range, that is given a ‘high’ and a ‘low’ number is straightforward in 32 bits, if you have access to a 64-bit register. The key is multiplying the result by the difference between high and low, and keeping just the bits above 32:

u32 getRandomInRange( u32 low, u32 high )
{
   u32 diff = low - high;
   u64 v = lcng.getRandom(); 
   v *= diff; 
   return (u32)(( v >> 32 ) + low );
}

Doing this for a range above 64 bits gets tricky because you’re back to needing to multiply by 2 64-bit registers.

The solution is simple. Implement a 64-bit multiply that keeps only the top 64 bits of the resulting 128-bit quantity:

u64 getRandomInRange( u64 low, u64 high )
{
   u64 diff = high - low;
   if ( diff < U32_MAX )
      return getRandomInRange( (u32)low, (u32)high );

   u64 rlow  = lcng.getRandom();
   u64 rhigh = lcng.getRandom();
   u64 vlow  = diff & 0xFFFFFFFF;
   u64 vhigh = diff >> 32;

   u64 r  = (( rhigh * vlow ) >> 32 );
       r += (( rlow * vhigh ) >> 32 ); 
       r += ( rhigh * vhigh );
       r += low;
   return r;
}