Generating a random number between 1-7 by rand(5)

Question

I want to write an algo to generate a random number between 1-7 given a method that generates a random number between 1-5.

I thought of one solution as rand(5)/5*7 ??

I think this should work.

Can anybody tell me an optimal solution ?

I read this solution somewhere, but I do not know how they thought of keeping " int num = 5 * (rand5() - 1) + (rand5() - 1);" . I understand that it generates a random number between 1-7 but how they thought of this logic or what they trying to convey is not getting into my head. Can anybody please throw a light on this.

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

Look for the solution @http://stackoverflow.com/questions/9423523/generate-unique-random-numbers-in-java — Nisarg Shah, Aug 23 '13 at 04:32
@VighaneshGursale not duplicate bro.. not even 1%,, if i would have got solution i wont have posted only — user2387900, Aug 23 '13 at 04:50

Ted Hopp · Accepted Answer · 2019-01-31T02:51:45.610

The code you posted is an example of an accept-reject algorithm. The expression

5 * (rand5() - 1) + (rand5() - 1);

generates a random number uniformly distributed between 0 and 24. The first term is 5 times a random number between 0 and 4, yielding one of the set {0, 5, 10, 15, 20} with equal probability. the second is a random number between 0 and 4. Since the two random numbers are presumably independent, adding them gives a random number uniformly distributed between 0 and 24. The second number "fills in" the gaps between the numbers generated by the first term.

The test then rejects any number that is 21 or above and the process repeats. When a number passes the test, it will be a random number uniformly distributed between 0 and 20 (inclusive). This range is then divided into 7 numbers (between 0 and 6) using % 7 and one is added before returning. Since there are 21 numbers in the interval [0, 20] and 21 is divisible by 7, the numbers between 0 and 6 will occur with equal probability.

In a table :

A           B              num
rand5()-1   rand5()-1      5 * A + B        num % 7 + 1
---------   ---------      ---------        -----------
0           0              0                1
1           0              5                6
2           0              10               4
3           0              15               2
4           0              20               7
0           1              1                2
1           1              6                7
2           1              11               5
3           1              16               3
4           1              21               reject
0           2              2                3
1           2              7                1
2           2              12               6
3           2              17               4
4           2              22               reject
0           3              3                4
1           3              8                2
2           3              13               7
3           3              18               5
4           3              23               reject
0           4              4                5
1           4              9                3
2           4              14               1
3           4              19               6
4           4              24               reject

Note that the last column has exactly three of each number in the range [1, 6].

Another way of understanding the logic is to think in terms of base-5 arithmetic. Since rand5() generates a random integer between 1 and 5 (inclusive), we can use rand5() - 1 to generate random digits for a base-5 number. We're trying to generate the numbers 1 through 7 (or, equivalently, 0 through 6), so we need at least two base-5 digits just to have seven numbers. So let's just generate a random, two-digit, base-5 number, digit by digit. That's what 5*(rand5() - 1) + (rand5() - 1) does. We could then do this over and over until we got a number between 0 and 6 (0 and 11₅). However, it would be more efficient to reject fewer of the two-digit numbers we are generating. We can do this by using everything up to (but not including) the largest two-digit, base-5 number that is a multiple of 7. That happens to be 41₅, which is 21₁₀. (We exclude 41₅ itself because we're starting at 0, not 1.) Since we want a number between 0 and 6, we reduce the range using % 7. (We could also have divided by 3, since there are exactly three, 7-integer ranges in [0, 40₅]. However, using the remainder operator makes it clear that we're aiming for the range [0, 6].)

P.S. Your proposed solution would not work. While it appears to have the correct range, the expression can only generate five distinct numbers, so it cannot possibly be correct. It can also produce 0 (when rand5() returns 1). If you were dealing with floating point random number generation, then simple scaling like that would be a good approach. (However, you'd want to shift to 0 before scaling and then shift back to 1 to get the correct lower bound on the range. The expression would be, I think, 1 + 7 * (rand5() - 1) / 5. But rand5() returns an integer, not a float.)

thanks..but why it is needed to generate 2 separate random numbers and then add, and again checking a condition ? I dont understand, why it would be uniform by generationg two random numbers and then adding it — user2387900, Aug 23 '13 at 04:47
@user2387900 - The idea is to generate a uniformly distributed range for which the reject region is small. With most accept-reject approaches, there's a trade-off between how much work you do to get a range that isn't too wasteful and how much work you have to do because you reject too often. You need to call `rand5()` more than once to get more than five distinct values (you need at least 7). By adding the second term, you ensure that the expression can generate every number between 1 and 24 with equal probability. — Ted Hopp, Aug 23 '13 at 04:52
@user2387900 - I reworded my answer a bit to address some of the points in my last comment. — Ted Hopp, Aug 23 '13 at 04:57
@user2387900 - Remember that this is all integer arithmetic. You can only generate five values with that expression. See the P.S. in my answer. — Ted Hopp, Aug 23 '13 at 05:01

Vicky Thakor · Answer 2 · 2013-08-23T04:38:47.013

1

Change 5 to your desired number. You have to import import java.util.Random;

int range = 7; // Now you can change your limit here.
Random r = new Random();
int number = r.nextInt(range);

Its another solution without using rand5()

edited Aug 23 '13 at 04:38

answered Aug 23 '13 at 04:33

Vicky Thakor

3,847
7
42
67

Can u pls explain the second line ? – user2387900 Aug 23 '13 at 04:35
Its inbuilt java class. – Vicky Thakor Aug 23 '13 at 04:36
2

The problem OP is trying to solve is: given a "black box" generator that yields a random integer uniformly distributed between 0 and 5, write a generator that yields a random integer uniformly distributed between 0 and 7. Using the `Random` class breaks the rules of the assignment, I think. – Ted Hopp Aug 23 '13 at 04:41
I tried in c#, but it has nextDouble, and it does not include any arguments. here by range if i write nextInt(50), then it generates a random number from 0-50 ? – user2387900 Aug 23 '13 at 04:42
Yeah using nextInt(50) will generate random number b/w 0-50 – Vicky Thakor Aug 23 '13 at 04:45
In c#, it does not have that feature..i suppose – user2387900 Aug 23 '13 at 04:51
oh.. I don't know about c#. But for java its useful – Vicky Thakor Aug 23 '13 at 04:52
1

C# Random.Next http://msdn.microsoft.com/en-us/library/2dx6wyd4.aspx – Axis Aug 23 '13 at 04:55

Generating a random number between 1-7 by rand(5)

2 Answers2