0

Expand a random range from 1–5 to 1–7

int i;
do
{
  i = 5 * (rand5() - 1) + rand5();  // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;  // result is now uniformly random between 1 and 7

WHy can't I just put

i = 6*(rand5()-1);

there? why we need "*" and" +" operation

Community
  • 1
  • 1
Josh Morrison
  • 7,488
  • 25
  • 67
  • 86

3 Answers3

4

(rand5() - 1) returns a number from 0 to 4. If you multiply any of these numbers by 6 you will get one of only 5 numbers (0, 6, 12, 18 or 24).

Doing it the other way ensures every possible integer between 1 and 21 can appear in the output (with a uniform probability).

EDIT:

5 * (rand5() - 1) will give you one of either (0, 5, 10, 15, 20). To this we then add another random integer between 1 and 5, thus filling in the gaps. We now have a random integer between 1 and 25 with uniform probability. Since we want a range from 1 to 21, we reject anything over 21 and try again.

Alex Deem
  • 4,717
  • 1
  • 21
  • 24
1

The point being that rand5() is random, and each call in the original expression returns a different answer. That is why rand5() + rand5() is not the same as 2*rand5().

Similarly: 5 * (rand5() - 1) + rand5() is 5*rand5() + rand5() - 5, but not the same as 6*rand5() - 5, since again each call to rand5() yields a different result.

Keith
  • 6,756
  • 19
  • 23
  • Man, I thought both you guys were crazy, I couldn't see how that math could work that way. Then it dawned on me: I was reading the equation as 5 * (r5-1 + r5), not as (5 * (r5-1)) + r5. This is why readability is so important, not that this code is so hard to read. – Hack Saw Feb 25 '11 at 05:13
0

Here is a routine in python with an empirical test for uniformity.

First the random generator of ints in the range 1..5:

>>> def r5(): return randrange(5) + 1

>>> bins = dict((i, 0) for i in range(9))
>>> pp(bins)
{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0}
>>> for i in range(999999): bins[r5()] += 1

>>> pp(bins)
{0: 0, 1: 199752, 2: 200378, 3: 200452, 4: 199580, 5: 199837, 6: 0, 7: 0, 8: 0}

Notice the bin counts for the values 1..5.

THe algorithm used is that if you generate two r5() numbers, in order, then their are 5*5 = 25 possible permutations that all have equal possibility of occurrence. if we take any constant 21 of these permutations, we can see if the perm we generate is in that 21 and turn every three values into one of seven integers to return. If we generate a permutation not in the 21 then we need to get two more r5() values and repeat.

The code for r7 depends on some constants that I have made global for speed:

>>> list5 = [1,2,3,4,5]
>>> perm21 = [(x,y) for x in list5 for y in list5 ][:21]
>>> set21 = set(perm21)
>>> def r7():
    r = (6,6)
    while r not in set21:
        r = (r5(), r5())
    return (perm21.index(r) // 3) + 1

>>> bins = dict((i, 0) for i in range(9))
>>> for i in range(999999): bins[r7()] += 1

>>> pp(bins)
{0: 0,
 1: 142857,
 2: 143558,
 3: 143046,
 4: 142699,
 5: 142786,
 6: 142439,
 7: 142614,
 8: 0}
>>>

Lets try looking at the spread of 10 times the trials:

>>> bins = dict((i, 0) for i in range(9))
>>> for i in range(9999999): bins[r7()] += 1

>>> pp(bins)
{0: 0,
 1: 1429821,
 2: 1429851,
 3: 1427350,
 4: 1428478,
 5: 1425243,
 6: 1429618,
 7: 1429638,
 8: 0}

Looks OK to me :-)

Paddy3118
  • 4,704
  • 27
  • 38