3
$\begingroup$

I have a function(say RandOne() ) which return random number upto $2^{31}-1$ (32 bit) . How to use that function to generate random number upto $2^{63}-1$ (64 bit)?

I think we should use something like one to many mapping . Using RandOne function many times and use it to make new function RandTwo() (which generate upto 64 bit number) but how to make sure that probability of any number is uniformly distributed ?

PS: We can assume RandOne() is perfect random generator .Hence probability of each number generated by it is equal .

  • 0
    @labbhattacharjee - the link that you've given describes how to convert 64 bits to 32 bits; not the other way around.2012-08-05

1 Answers 1

2

To distill the advice from the comments, if you have two 32-bit random numbers, you can just concatenate them to get one 64-bit random number. Mathematically, you can write that as

$r = r_0 + 2^{32} \, r_1$

where $r_0$ and $r_1$ are the 32-bit random numbers and $r$ is the 64-bit result. Or, in a programming language like C or Java:

long r = (long)r0 + ( (long)r1 << 32 ); 

where long is assumed to be a 64-bit integer type.

Note that this assumes that $r_0$ and $r_1$ are uniformly distributed between $0$ and $2^{32}-1$ inclusive, and yields a result $r$ between $0$ and $2^{64}-1$ inclusive. If your original random numbers really have only 31 bits, as your question title suggests, then the result will only have 62 random bits.

As long as $r_0$ and $r_1$ are uniformly distributed and independent (i.e. "truly random"), $r$ will also be uniformly distributed. However, if the values of $r_0$ and $r_1$ are not truly independent, the distribution of $r$ might not be as uniform as it should be. In particular, if $r_0$ and $r_1$ are generated by a simple pseudorandom number generator with only 32 bits of internal state, such that $r_0$ uniquely determines $r_1$, then $r$ can take on only $2^{32}$ possible values.

Even then, of course, $r$ might look acceptably random for your purposes, especially if you don't need to generate too many such numbers. One might contrast this with, say, using a 32-bit pseudorandom number generator to shuffle a deck of cards: such a shuffle, if done with an otherwise correct algorithm, will likely look perfectly random in casual play, even though one can mathematically prove that it can only generate a tiny fraction of all the $52! \approx 2^{225.6}$ possible shuffles.

That said, for any serious purposes (e.g. statistical sampling or Monte Carlo algorithms), I would recommend using a better random number generator with a larger state space, and making sure that the generator is also seeded with sufficiently many bits of initial randomness.