c - Normalize random value of _int64 -

let's suppose have noramlly distributed random int values function:

unsigned int myrand(); 

the commonest way shrink range [0, a] (int a) follows:

(double)rand() / uint_max * 

now need same values in range of __int64:

unsigned __int64 max64; unsigned __int64 r64 = myrand(); r64 <<= 32; r64 |= myrand(); r64 = normalize(r64, max64); 

the problem normalize return range __int64 because not placed in double. wouldn't use various libraries big numbers due performance reasons. there way shrink return range , while saving normal distribution of values?

the method give

(double)myrand() / uint_max * 

is broken. example, if = 1 , want integers in range [0, 1] ever value of 1 if myrand () returned uint_max. if meant range [0, a), value 0, still broken because in case return value outside range. no matter what, introducing bias.

if want a+1 different values 0 inclusive, , 2^32 ≤ < 2^64, proceed follows:

step 1: calculate 64 bit random number r did. if 1 less power of two, return r shifted right amount.

step 2: find how many different random values mapped same output value. mathematically, number floor (2^64 / (a + 1)). 2^64 large, no problem because equal 1 + floor ((2^64 - (a + 1)) / (a + 1)), calculated in c or c++ d = 1 + (- (a + 1)) / (a + 1) if has type uint64_t.

step 3: find how many different random values should mapped calculating n = d * (a + 1). if r >= n go step 1.

step 4: return r / d.

no floating point arithmetic needed. result totally unbiased. if < 2^32 fall 32 bit version (or use 64 bit version well, calls myrandom () twice needed).

of course calculate d , n once unless changes.