Given a random int generator [0-5], generate [0-7]

Question

So this was an interview question.

You are provided with a function rand5() which generates a random integer in the range [0-5] i.e. {0,1,2,3,4,5}

a) Can you use that function to generate a random integer in the range [0-7]?

b) Can you use that function to generate a random integer in the range [0-7] with each number having equal probability?

You may use the function multiple times.

One of the solution for part a, ((rand5() +rand5())*7)//10 where // represents integer division would give you the range [0-7] however the probabilities are not equal.

Would love to see your answers and thought process on this.

Possible duplicate of [Expand a random range from 1–5 to 1–7](https://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7) — pjs, May 16 '19 at 19:57
I believe SO questions are marked as duplicates provided the duplicate has an *accepted* answer. — גלעד ברקן, May 17 '19 at 15:33
@erickson I researched a little and could not find policies or meta posts that support my claim. It's possible I saw a comment to that effect somewhere. Also, I always assumed the duplicate-question wording after it's closed to the effect of "this question already has an answer..." equated "having an answer" with having an accepted answer. I guess it's more nuanced, though. — גלעד ברקן, May 17 '19 at 18:21

score 5 · Answer 1 · edited May 17 '19 at 15:30

5

    $one  = rand5();
    $two  = rand5();
    $four = rand5();

    return (($four < 3)? 4 : 0)  +  (($two < 3)? 2 : 0)  +  ($one < 3)? 1 : 0);

edited May 17 '19 at 15:30

erickson

265,237
58
395
493

answered May 16 '19 at 13:08

David Zimmerman

335
4
7

can you modify this approach to work with, say 9 instead of 7? – hsnsd May 16 '19 at 13:16
4

Nice one, although shouldn't it be `>= 3`? (so 0, 1, 2 are 0 and 3, 4, 5 are 1). Maybe worth noting this approach works whenever the source random function produces an even number of values and the desired range is from zero to a power of two minus one. – jdehesa May 16 '19 at 13:18
Once agian, the probability of having lower numbers is higher than lower numbers in this example. EDIT: I guess only with 2,5 you got even chances. – Wimanicesir May 16 '19 at 13:19
Probability of getting 7 is 1/27, not 1/8 – MBo May 16 '19 at 16:52
@MBo Can you explain? Probability of getting three heads in a row is 2^(-3) = 1/8. – erickson May 16 '19 at 17:49
1

@erickson Yes, but we have here not 0/1 coin, but rand5() giving result 0..5, and probality of (4 or 5) is 1/3. P.S. I should write "Probability of getting 7 using this approach" – MBo May 16 '19 at 17:51
1

@MBo Ah, right. My comment was based on the assumption that he'd fix that bug as mentioned above. – erickson May 16 '19 at 17:54
2

People are upvoting this, but as written it does not give a uniform distribution. Also, this approach will not work if the targeted number of outcomes isn't a power of 2 - in that case you need a rejection scheme. – pjs May 16 '19 at 21:17
@pjs yeah, but it's a trivial fix and it does answer the posted question. – גלעד ברקן May 16 '19 at 23:27

score 1 · Answer 2 · answered May 17 '19 at 02:55

This can be done using Rejection Sampling.
Consider the rolls arranged in a 2D grid like below

[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5]

Now if you roll the die twice you can generate any position in the 2D grid (first row for row position, second for column position). There are 36 positions in total. Since we want to generate numbers in [0, 7] range we need output space to be a multiple of 8. If we consider first 32 positions (in a row major order) we can split them into group of 4 indices. For example

[0, 1, 2, 3] in first row => 0
[4, 5, 0, 1] in first and second row => 1
[2, 3, 4, 5] in second row => 2
...
[4, 5, 0, 1] in fifth and sixth row => 7

If we roll last 4 positions, we will just roll again.

int rand7() {
    while(true) {
        int row = rand(5);
        int col = rand(5);
        int pos = row * 6 + col;
        if(pos < 32) {
            return pos/4;
        }
    }
}

There's a similar answer [here](https://stackoverflow.com/a/842183/2034787) with over 550 votes for it. — גלעד ברקן, May 17 '19 at 04:19

score 1 · Answer 3 · answered May 17 '19 at 10:40

Try this approach:

rand5() yields random number between 0-5 with equal probability. Also three numbers (0, 2, 4) returned by rand5() are even and other three(1, 3, 5) are odd. Thus it yields even and odd numbers with equal probability.
if rand7() returns all numbers with equal probability, then the probability of 6 in rand7() should be 1/8. Also probability of rand5() returning even number thrice is 1/8.

Thus rand7() can be:

// returns random number between 0-5 with equal probability
function rand5() {
  return Math.floor(Math.random() * 6);
}

// returns random number between 0-7 with equal probability
function rand7() {
  if(rand5() % 2 == 0 && rand5() % 2 == 0) { 
    return 6 + rand5() % 2;
  } else {
    return rand5();
  }
}

console.log(rand7());

score 0 · Answer 4 · answered May 16 '19 at 18:55

A die has an equal chance to roll any side. If the desired range is smaller than the range of the die, simply re-roll when it's out of bounds.

The problem comes when the desired range is larger than the range of one die. The sum of multiple dice rolls is not-quite-normally distributed, so that adding the value of multiple rolls won't work.

Instead, think about using successive rolls to progressively "zoom in" on a value within a subrange. If we roll a 6-sided die twice, the first roll would select a 6-unit subrange—for example, 12–17, inclusive. The second roll would select a single value from that subrange, like 14.

Again, as with a single die, if the range is larger than desired, simply reject values that are out of bounds, and roll again.

Given a random int generator [0-5], generate [0-7]

4 Answers4