How do you generate a random number in between 1 and 7 by using a function which generates 1 to 5

Question

Possible Duplicate:
Expand a random range from 1-5 to 1-7

I understood the solution using rejection sampling i.e

public static int rand7() {
    while (true) {
       int num = 5 * (rand5() - 1) + (rand5() - 1);
       if (num < 21) return (num % 7 + 1);
    }
}

but I am thinking of another solution, i.e rand5() is called 7 times and result is divided by 5, but I am not sure whether this is correct. Please let me know if is or isn't.

public static int rand7() {    
    int num = rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5();
    return num/5;
}

EDIT: It looks like the probability of generating 1 is (1/5)^7 but to generate 2 it is 7*(1/5)^7. It is uneven so it is not going to work.

Seems to me like that should work, as should calling `rand5()` any number of times greater than or equal to 7 (accumulating the results in `sum`), and then taking `(sum % 7) + 1` as the result. — aroth, Aug 06 '11 at 14:01
@aroth, that won't work. Assume you do it twice. You get a random value in the range (1, 10). Then 1, 2 and 3 will have higher probabilities than 4, 5, 6, 7. — aioobe, Aug 06 '11 at 14:05
@aioobe - You mean it won't produce an equal statistical likelihood for each number in the range. Granted. But the question is not stipulating that `rand7()` has to produce a statistically uniform distribution. As I read it, any solution that *may* produce all values from 1-7 is valid, even if it produces `3` 99% of the time and one of `1,2,4,5,6,7` only 1% of the time. Obviously that wouldn't be a very good random number generator, but it seems like it would satisfy the constraints of the question. — aroth, Aug 06 '11 at 14:11
So [`return 4`](http://xkcd.com/221/) would be fine? That's a random number between 1 and 7, right? (If you're joking, please say so :-) — aioobe, Aug 06 '11 at 14:14
@Paul R: Not an exact duplicate. This question is about the veracity of a solution not provided in the question you have cited. — Jacob, Aug 06 '11 at 14:17
If you don't specify the distribution you want to get, then a function that always returns 3 is a legitimate answer. — n. m. could be an AI, Aug 06 '11 at 14:17
@aioobe - No, that wouldn't quite work, since it can only ever result in 4. And more like nitpicking over the semantics of the question than joking. If we assume that "random" should mean "possessing a statistically uniform distribution" then of course you are correct. Though from the information provided in the question, for all we know `rand5()` is implemented as `return 4`. — aroth, Aug 06 '11 at 14:22
@aroth When the distribution is not specified it is usually implied that it is uniform. `return 4` is just an extreme case of a nonuniform distribution. — starblue, Aug 06 '11 at 17:06
Every number between 1 and 5 is **already** a number between 1 and 7. *trollface.jpg* — Ignacio Vazquez-Abrams, Aug 07 '11 at 05:03

Jacob · Answer 1 · 2011-08-08T14:07:09.110

3

It will not be a uniform distribution (looks normal). And as Paul says, the proof follows from the Central Limit Theorem.

enter image description here

edited Aug 08 '11 at 14:07

answered Aug 06 '11 at 14:38

Jacob

34,255
14
110
165

For proof see Central Limit Theorem: http://en.wikipedia.org/wiki/Central_limit_theorem – Paul R Aug 06 '11 at 15:35
@Hareendra: No problem. Also, if you think an answer is good, please upvote it. I have also noticed that you haven't *accepted* any answers. If you a specific answer answers your question best, please click on the tick-mark next to it. For more information, read the [FAQ](http://stackoverflow.com/faq#howtoask) – Jacob Aug 06 '11 at 18:21

aioobe · Answer 2 · 2011-08-06T14:26:09.820

2

No, it's not correct (at least not if the requirement is a uniform distribution, which is provided through rejection sampling).

If you had added two more + rand5() terms, you would compute an approximation of the average a rand5 function. As it stands now, you're basically compute an approximation of 7/5 × the average of the rand5 function. (Which should be about 4.2.)

If you wanted a number between 1 and say 25, you could do

int[][] lut = { {  1,  2,  3,  4,  5},
                {  6,  7,  8,  9, 10},
                ...,
                { 21, 22, 23, 24, 25 } }

return lut[rand5()][rand()]

This can not be done for 7 though, since 5 and 7 are co-prime. Rejection sampling is the best way to solve this.

edited Aug 06 '11 at 14:26

answered Aug 06 '11 at 13:57

aioobe

413,195
112
811
826

1

No, it's not the average. To get the average he would have to call `rand5()` 7 times, and then divide by 7. He's calling 7 times and dividing by 5. And as far as I can tell, the question doesn't make any stipulations about how the results of `rand7()` need to be distributed. I think any solution that may possibly generate any value between 1 and 7 (inclusive) would be considered valid. – aroth Aug 06 '11 at 14:02
1

You get an approximately normal distribution this way rather than a rectangular distribution - see Central Limit Theorem. – Paul R Aug 06 '11 at 14:07
@aroth, updated the answer regarding the average. About the "distribution" I think we can safely assume that it's an even distribution the OP is after. – aioobe Aug 06 '11 at 14:17
@ aroth, sorry for not including the details , i wanted a uniform distribution. – hareendra reddy Aug 07 '11 at 04:56

score 2 · Answer 3 · answered Aug 07 '11 at 07:00

It is not possible to create an uniform rand7() function on base of uniform rand5() function. However it is possible to be as close as needed.

For example, if you are able to call rand5() 10 times in rand7(), you can get quite well quasi-uniform rand7(). If you are able to call it 100, then rand7() can be almost perfect, but never exactly uniform. This can be mathematically proven.

Lance Roberts · Answer 4 · 2011-08-08T18:04:16.650

2

A simple solution is to use rand5() on the bits of an octet, by assigning 0 to derived values 1 or 2, generating again on a 3, or assigning 1 for values 4 or 5. If the final result is zero, then redo. Here's some code:

public static int rand7() {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + rand5_output_2();
        }
    }
    return returnValue;
}

private static int rand5_output_2() {
    while (true) {
        int flip = rand5();

        if (flip < 3) {
            return 0;
        }
        else if (flip > 3) {
            return 1;
        }
    }
}

edited Aug 08 '11 at 18:04

answered Aug 07 '11 at 07:29

Lance Roberts

22,383
32
112
130

He is not overcomplicating it. Your solution will not work as the function rand5() is apparently returning integer numbers. This way you get only numbers 1 2 4 5 7. – Tomas Aug 08 '11 at 10:38
@Tomas, OK, wish he'd specified that. Here's the best solution I found for integers. – Lance Roberts Aug 08 '11 at 18:04

score 0 · Accepted Answer · answered Aug 06 '11 at 14:06

0

While that other solution will generate a random number in the range 1..7, it will do so with a non-uniform probability distribution, i.e. the number 3 will be a lot more likely than the number 1.

In contrast, the rejection sampling approach will return all numbers in the range 1..7 with equal probability.

answered Aug 06 '11 at 14:06

meriton

68,356
14
108
175

note that the second solution leads to normal distribution (gaussian curve). The first solution is OK. – Tomas Aug 08 '11 at 10:40

How do you generate a random number in between 1 and 7 by using a function which generates 1 to 5

5 Answers5