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 .

  • $\begingroup$ If you can obtain 32 random bits at a time, and what you need is 64 random bits, what do you think you should do? $\endgroup$ – user856 Aug 5 '12 at 6:29
  • $\begingroup$ concatenation will not make sure that probability of each number is equal . will it ? $\endgroup$ – user35921 Aug 5 '12 at 6:32
  • 1
    $\begingroup$ tesla, that would depend on the details of RandOne. $\endgroup$ – Gerry Myerson Aug 5 '12 at 6:37
  • $\begingroup$ It depends. If RandOne just has a 32-bit state, the second value will be determined by the first. $\endgroup$ – Robert Israel Aug 5 '12 at 6:45
  • $\begingroup$ If it is "perfect", all possible pairs $(x_1, x_2)$ will also have equal probabilities of being produced by consecutive calls to RandOne. $\endgroup$ – Robert Israel Aug 5 '12 at 6:47

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy