*Given a function which produces a random integer in the range 1 to 5, write another function which uses it and produces a random integer in the range 1 to 7.*

I'm going to modify this a little and make it generic:

*Given a function which produces a random integer in the range 1 to 5(M), write another function which uses it and produces a random integer in the range 0 to 7(N)*.

Of course it's easy to do it without generating a uniform distribution so I'm not going to spend time on that.

What needs to be done is generate a uniform distribution. But consider this example:

If we add random(5) + random(5), assuming random(5) generates numbers from 0 to 4, we have:

` 1: 0+0`

` 2: 0+1, 1+0`

` 3: 0+2, 2+0, 1+1`

` 4: 0+3, 3+0, 1+2, 2+1`

` 5: 0+4, 4+0, 1+3, 3+1, 2+2`

` 6: 1+4, 4+1, 2+3, 3+2`

` 7: 2+3, 3+2, 3+3`

` 8: 3+4, 4+3`

` 9: 4+4`

This obviously is not a uniform distribution because we have more chances of generating the number 4 than the number 8. So whatever algorithm is needed, it cannot simply use operations involving random(5). Or, actually it can, with some complicated math behind. Read about Box–Muller transformations and Rejection sampling.

What I think is a simpler algorithm is the following: since every number can be represented in X bits, generate X numbers from 1 to 5, and depending on the generated number, set bit X to 1 or 0. Number from 0 to 7 can be represented with 3 bits. Let me know what you think.

1: int genRandom1to5() {

2: return (rand() % 5) + 1;

` 3: }`

` 4: `

5: int genRandom1to7() {

6: int rand17 = 0;

7: for (int i = 0; i < 3; i++) {

8: int rand15 = 3;

9: while (rand15 == 3) {

` 10: rand15 = genRandom1to5();`

` 11: }`

12: if (rand15 < 3)

` 13: rand17 |= (1 << i);`

` 14: }`

15: return rand17;

` 16: }`

## No comments:

## Post a Comment