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

Question

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?

Answer 1

(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.

Answer 2

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.