I am given a function rand5() that generates, with a uniform distribution, a random integer in the closed interval [1,5]. How can I use rand5(), and nothing else, to create a function rand7(), which generates integers in [1,7] (again, uniformly distributed) ?
By default, rand returns normalized values (between 0 and 1) that are drawn from a uniform distribution. To change the range of the distribution to a new range, (a, b), multiply each value by the width of the new range, (b – a) and then shift every value by a.
Then out of 3 possible rand() outputs: 0, 1 and 2, we get 0, 1 and 0 respectively when we use them modulo n. Therefore the output will not be uniform at all.
Note that a prefect uniform distribution cannot be achieved with a bounded number of draw5()
invocations, because for every k
: 5^k % 7 != 0
- so you will always have some "spare" elements.
Here is a solution with unbounded number of draw5()
uses:
Draw two numbers, x1,x2. There are 5*5=25 possible outcomes for this.
Note that 25/7 ~= 3.57. Chose 3*7=21 combinations, such that each combination will be mapped to one number in [1,7], for all other 4 numbers - redraw.
For example:
(1,1),(1,2),(2,1) : 1
(3,1),(1,3),(3,2): 2
(3,3),(1,4),(4,1): 3
(2,4),(4,2)(3,4): 4
(4,3), (4,4), (1,5): 5
(5,1), (2,5), (5,2) : 6
(5,3), (3,5), (4,5) : 7
(5,4),(5,5),(2,3), (2,2) : redraw
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With