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; }