1
$\begingroup$

If I have a uniformly distributed random number generator of up to 32 bits in length, can I generate a uniformly distributed 128 bit number by rolling my 32-bit random number generator multiple times and combining the results in some way?

My thoughts are as follows:

If I throw multiple 6-sided die and add them up, it's not uniformly distributed - the distribution is gaussian. So I can't add up four of my 32 bits to get a 128 bit number that's uniform.

If I do a whole bunch of coin tosses, one for each bit, then I can generate a 128 bit binary number. Since I'm essentially picking one of two and then replacing it each time, then each possible sequence of 128 picks has the same probability.

If I generate four 32-bit random numbers and concatenate them, then would that be uniformly distributed? Is that not what I'm doing for the coin toss example above?

I did this in reality in my code (concatenated four 32-bit numbers) and found that all of the results were > 2^96 purely because the most significant 32-bit roll was very rarely zero (naturally). This makes sense, but it makes me wonder if it truly is a uniform distribution or or if there is a skewing of the distribution to the numbers bigger than 2^96.

If it is a skewed distribution, how do I create a uniform distribution?

$\endgroup$
2
  • 3
    $\begingroup$ Most integers less than $2^{128}$ are greater than $2^{96}$ (only about $1$ in every $2^{32}$ of them are not). $\endgroup$
    – Henry
    Commented Oct 9, 2014 at 8:42
  • 2
    $\begingroup$ Like @Henry alluded to, concatenation of $32$-bit uniformly random bitstrings will also make uniformly distributed bitstrings of longer length. The probability of having numbers less than $2^{96}$ in $2^{128}$-bit strings should equal the probability of having a random $32$-bit string equal zero, which is $1/2^{32}$ so very very low. $\endgroup$
    – String
    Commented Oct 9, 2014 at 8:46

1 Answer 1

Reset to default
2
$\begingroup$

You have to generate 4 32-bit random numbers and then merge them together. Adding will definitely a bad idea, you won't get a uniform distribution but merging in sense of "1th .. 32th bit - 1st generated number, 33th .. 64th bit - 2nd generated number and so on" will give you uniformly distributed binary number of length 128, as probability of event that any bit equals zero $=$ probability that bit equals one $= 1/2$. Numerically you have to multiply the first number at $2^{96}$, the second at $2^{64}$, the third at $2^{32}$, take the fourth as is and then sum them up.

$\endgroup$

You must log in to answer this question.