11 replies to this topic

[Roger]

Given a function which produces a random integer in the range 1 to 5, how can we write a function which produces a random integer in the range 1 to 7.

I'm preparing for an interview with Google next week. Although the job will be more Product-related vs. Programming, I am still doing some research to see what type of programming questions they'll ask. I'll post a couple more to see if you can help me out.

Thanks!

[Groogy]

Not sure if this is what you want but you could call function(1-5) twice, multiply the result with each other and use modulus 7 plus one on the product and return it.
Example:

int Random1To5();

int Random1To7() {
  return (Random1To5() * Random1To5()) % 7 + 1;
}

Though I doubt this is the answer they would want. But I guess it would produce the same result.

[Roger]

Hmm.. will this be truly random? Almost sounds too easy..

[WingedPanther]

I wouldn't use that. Random1to5 * Random1to5 gives you the following probabilities (assuming 1to5 produces equally likely values of 1, 2, 3, 4, 5)
1,1 -> 2
1,2 -> 3
1,3 -> 4
1,4 -> 5
1,5 -> 6
2,1 -> 3
2,2 -> 5
2,3 -> 7
2,4 -> 2
2,5 -> 4
3,1 -> 4
3,2 -> 7
3,3 -> 3
3,4 -> 6
3,5 -> 2
4,1 -> 5
4,2 -> 2
4,3 -> 6
4,4 -> 3
4,5 -> 7
5,1 -> 6
5,2 -> 4
5,3 -> 2
5,4 -> 7
5,5 -> 5

1: 00%
2: 20%
3: 16%
4: 16%
5: 16%
6: 16%
7: 16%

[BlaineSch]

Nothing is truly "random" only appears random.

I'd get the smallest measurement of time and mod it by 7 and add one. Usually it's nanotime or something. You might do a bit more math to it to make it look more complex though :]

[Alexander]

One good classic method I would use would be rejection sampling to generate observations from a distribution, an example of generating a viewed statistically random number:

int onetoseven() {
  int r;
  do {
    r = 5 * ( onetofive() - 1) + onetofive(); //1->25
  } while(r > 21); 
  return r % 7 + 1; //1 -> 21
}

Just be noted the two methods I am conveying have a slight inherit chance of reaching an infinite loop.
Another take on a statistically random number is the "splash" method, as long as relying on onetofive() on being random, it is a random value between one and seven, since there are equal numbers of non-zero values to choose from.

int onetoseven() {
    int values[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0) {
        int i = onetofive();
        int j = onetofive();
        result = values[i-1][j-1];
    }
    return result;
}

[Roger]

I like the "splash" method you described - easy to remember and seems pretty random.. I wonder if the result is truly random (per @WP's analysis earlier).

[Alexander]

Roger said:

I wonder if the result is truly random (per @WP's analysis earlier).

Nothing is truly random, but one million iterations of onetoseven()with the second function returns the following results:

[the number] [times] [percent] 
1: 143539 (14.35%)
2: 143489 (14.35%)
3: 142580 (14.26%)
4: 142092 (14.21%)
5: 143321 (14.33%)
6: 142824 (14.28%)
7: 142156 (14.22%)

And thus we reached uniformity with 1 - 5 as a basis to the algorithm.

[Roger]

awesome! thanks, Nullw0rm!

[zoranh]

Groogy said:

Not sure if this is what you want but you could call function(1-5) twice, multiply the result with each other and use modulus 7 plus one on the product and return it.
Example:

int Random1To5();

int Random1To7() {
  return (Random1To5() * Random1To5()) % 7 + 1;
}

Though I doubt this is the answer they would want. But I guess it would produce the same result.

This does not produce uniform distribution!

[Roman Y]

Nice one. Like the splash method too! btw you're asking if the methods will truly be random... arn't all the random functions that have another random fuction as basis random?

btw Nullw0rm would the splash method work if you have to build a function on another function 1-n if needed function needs to be bigger than 1-n²? could one just build 3 dimensional array and use the same idea?

[zoranh]

Roman Y said:

Nice one. Like the splash method too! btw you're asking if the methods will truly be random... arn't all the random functions that have another random fuction as basis random?

btw Nullw0rm would the splash method work if you have to build a function on another function 1-n if needed function needs to be bigger than 1-n²? could one just build 3 dimensional array and use the same idea?

Both NullW0rm's solutions are correct and work in exactly the same way. But solution #1 is more general and can be used in other cases, not only 1-7.

Note that Random class in C# generates numbers in range 0 and 2^31-2 inclusive, while C++ still generates only in range 0 to 32767.

Here is general solution which generates numbers betwen 0 and 2^30-1 using random5 function. It first reduces random5 to range 0-3 and then uses that as two bits of final result. Then any small random number in range 0-m can be generated as random() % (m+1) with difference between uniform distribution so small that it can be neglected in any practical case (as you normally do when you use Random class in C#).

        int random4()
        {
            int value = -1;
            do
            {
                value = random5() - 1;
            }
            while (value == 4);
            return value;
        }

        int random()
        {
            int value = 0;
            for (int i = 0; i < 30; i += 2)
                value = (value << 2) | random4();
            return value;
        }