# Given a random number generator rand5() generate gen7()

Given a pseudo random number generator rand5() that generates a random integer in the set [0,1,2,3,4], how would someone use this to generate a function rand7() that outputs [0,1,2,3,4,5,6] with equal probability.

I was thinking of approaching it this way: reduce the problem to generate number from 0 to 6 using a coin.

We can represent [0,1,2,3,4,5,6] using bit-wise from 000 to 111.
Selecting each bit from LSB to MSB can be done using tossing a coin.
However, if we continue in this fashion from LSB to MSB then we
can get all bits as 111 which is decimal 7. So, in the case of MSB
if we get 1 then discarding it and starting again should give
the result? Right?


Reducing the problem from rand5() to coin can be done in this way: if the number is 0,2 then we can consider it as head and getting 1,3 can be considered as tail.

Is my solution right?

• What do you think? If you feel your idea works, make an argument that proves it. – quicksort Feb 1 '17 at 4:40
• @quicksort: each bit has probability of 1/2 being set or unset. So, each number in the range [0,1,2,3,4,5,6] has probability of 1/8 being selected. – noman pouigt Feb 1 '17 at 5:34
• So you are using 3 x rand5 calls and with probability 1/5 reject and get new 3 x rand5 calls? – Evil Feb 1 '17 at 6:56
• @Evil In order to convert from rand5 to a coin the probability works like this: 1/5 is the probability of getting each number and if the undesired number comes we start again. I think it is called rejection sampling where the probability is not even considered when a undesired result comes as if that event has not even happened. – noman pouigt Feb 1 '17 at 7:23
• Ok. I know about the rejection sampling, the odd thing is giving probability 1/8 if by rejection you do not count it (so for 7 numbers it is 1/7). I have asked about discarding - do you discard all three samples or only last one? are you happy with that much samples used or this is not a concern? – Evil Feb 1 '17 at 8:57

## 2 Answers

(For some reason, this old question came up first)
rand5()+rand5()*5 would give numbers 0-24, each with a probability of 1/25. You could use the first 21 of these to return 0-6 with equal probabililty.
Likewise, rand2()+rand2()*2+rand2*4) gives numbers 0-7, each with a probability of 1/8. You could use the first 7 of these to return 0-6 with equal probability.
In pseudocode:

function rand7a() {
do { rand7 = rand5() + rand5()*5 } while (rand7 >= 21);
return rand7 mod 7;
}
function rand7b() {
do { rand7 = rand2() + rand2()*2 + rand2()*4 } while ( rand7 == 7);
return rand7;
}


EDIT: Elaboration:
1st approach:
rand2() in binary is 000 or 001 with 50-50 probability.
rand2()*2 is 000 or 010 with 50-50 probability.
rand2()*4 is 000 or 100 with 50-50 probability.
So the sum is binary xxx where each x has a 50-50 probability of 0 or 1; so each 000 to 111 has a probablilty of 1/8.

2nd approach: going through each of the 8 possibilities of the 3 rand2()s:
0+0+0 or 1+0+0 or 0+2+0 or 1+2+0 or 0+0+4 or 1+0+4 or 0+2+4 or 1+2+4
all of these with equal probablilty 1/8.

• Rand2 + rand2*2 +rand2*4 how does this give a number in the range 0 to 7 with equal probability? Can you elaborate? – noman pouigt Jun 10 '18 at 20:00
• @nomanpouigt Think of the number written in binary. A number in the range 0-7 has three bits and the answer chooses each bit independently, uniformly at random. – David Richerby Jun 10 '18 at 20:28
• @noman pouigt I EDIT'ed in an elaboration. Thanks. – dcromley Jun 10 '18 at 20:35

It can work, but there is no need for an intermediate step: just convert from base 5 to base 7, picking the least significant base-7 digit. The algorithm is as follows:

1. Use rand(5) to generate a and b; let n = 5 * a + b.
2. If n >= 21, discard n and go back to step 1, else go to step 3.
3. Return n mod 7.
• Slightly more efficient: If n ≥ 21, subtract 21 to get another 0 ≤ a < 4, get 0 ≤ b < 5, transform into a number n from 0 to 19. If less than 14 then return n modulo 7, otherwise subtract 14 to get another 0 ≤ a < 6 and so on and so on. – gnasher729 Jun 11 '18 at 22:10
• @gnasher729: Indeed. It's the equivalent of long division, base 5. Although I think that the added complexity, and added operations, can take more time than getting, once in a while, a new rand(). – jose_castro_arnaud Jun 13 '18 at 18:27
• i guess what you mean is base 5 to base 10 – dksahuji Mar 26 '20 at 6:55