Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
- What is a simple solution?
- What is an effective solution to reduce memory usage or run on a slower CPU?
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
There are elegant algorithms cited above, but here's one way to approach it, although it might be roundabout. I am assuming values generated from 0.
R2 = random number generator giving values less than 2 (sample space = {0, 1})
R8 = random number generator giving values less than 8 (sample space = {0, 1, 2, 3, 4, 5, 6, 7})
In order to generate R8 from R2, you will run R2 thrice, and use the combined result of all 3 runs as a binary number with 3 digits. Here are the range of values when R2 is ran thrice:
0 0 0 --> 0
.
.
1 1 1 --> 7
Now to generate R7 from R8, we simply run R7 again if it returns 7:
The roundabout solution is to generate R2 from R5 (just like we generated R7 from R8), then R8 from R2 and then R7 from R8.
Edit: That doesn't quite work. It's off by about 2 parts in 1000 (assuming a perfect rand5). The buckets get:
By switching to a sum of
seems to gain an order of magnitude for every 2 added
BTW: the table of errors above was not generated via sampling but by the following recurrence relation:
Here's my answer:
It's a little more complicated than others, but I believe it minimises the calls to rand5. As with other solutions, there's a small probability that it could loop for a long time.
I don't like ranges starting from 1, so I'll start from 0 :-)
Here is a working Python implementation of Adam's answer.
I like to throw algorithms I'm looking at into Python so I can play around with them, thought I'd post it here in the hopes that it is useful to someone out there, not that it took long to throw together.