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

This question already has answers here: Closed 11 years ago.

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.

---

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

---

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.

---

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.

---

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;
        }
    }
}

---

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.