Pages

Friday, January 8, 2010

The weird random

PROBLEM: Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

SOLUTION: As always, it is the way that you approach it. In my personal opinion the first part doesn't interfere in the second part. In other words, you have two different functions, one that produces a random integer 1...5 and it is asking you to write a function that produces a random integer between 1...7, so the easiest way to solve this problem would disconsider the random five function and just return a random number 1 to 7.

But it will not be the case, let's consider that based on a random number between 1..5, we need to find a random number between 1...7.

However a second question that we need to ask is if it is or not a uniform distribution (equidistributed). If it was not, the solution would be much easier.

Once again, let's assume that it will be a uniform distribution.

My solution would be based on a solution that calculates the binary number for the random five method. My line of thinking start when we see the number 7 in binary, it is 111, so it tells and give us hint how to calculate and solve this problem.

First we define a new method that calculates the random bit based on the random five method and in our random seven method just consider three random bit and convert it to decimal.

So far this conversion is simple, based on the binary conversion to decimal formula:


As wee have only three digits we can reduce this formula to:


And simplifying it to:



Based on this formula, considering x as a random bit, we will have these cases:

r = 0 + 0 * 2 + 0 * 4 = 0 --> discard this one.
r = 1 + 0 * 2 + 0 * 4 = 1
r = 0 + 1 * 2 + 0 * 4 = 2
r = 1 + 1 * 2 + 0 * 4 = 3
r = 0 + 0 * 2 + 1 * 4 = 4
r = 1 + 0 * 2 + 1 * 4 = 5
r = 0 + 1 * 2 + 1 * 4 = 6
r = 1 + 1 * 2 + 1 * 4 = 7

Our code would be:
public class MyRandom {
int randFive() {
return ((int) (Math.random() * 5)) + 1;
}

int randSeven() {
int r = randBit() + randBit() * 2 + randBit() * 4;
return r != 0 ? r : randSeven();
}

private int randBit() {
int r = randFive();

// here is the catch, to have a even random bit
// from five we should discard one of the odd
//numbers. We can choose between 1, 3 or 5.
return r != 1 ? r % 2 : randBit();
}
}

TEST:

public class MyRandomTest {
public static void main(String[] args) {
int TEST_SIZE = new Double(Math.pow(2, 16)).intValue();
MyRandom rand = new MyRandom();
int numbers[] = new int[7];

// generate random numbers
for (int i = 0; i < TEST_SIZE; i++) {
numbers[rand.randSeven() - 1]++;
}

NumberFormat nf = NumberFormat.getPercentInstance();
nf.setMaximumFractionDigits(2);

// statistic
for (int i = 0; i < numbers.length; i++) {
double percent = (new Double(numbers[i]).doubleValue()) / TEST_SIZE;
System.out.println("Number: " + (1 + i) + " - " + numbers[i]
+ " times : " + nf.format(percent));
}
}
}
TEST RESULT:
Number: 1 - 9437 times : 14.4%
Number: 2 - 9357 times : 14.28%
Number: 3 - 9324 times : 14.23%
Number: 4 - 9294 times : 14.18%
Number: 5 - 9397 times : 14.34%
Number: 6 - 9378 times : 14.31%
Number: 7 - 9349 times : 14.27%

No comments :