random generator not good enough?

Question

During an interview I was asked to implement a random generator in java without using any existing random number libraries that takes as an argument int n, and returns a random number between 0 and n. This was the implementation I provided:

public static int random(int n) {
    int r = 0;
    for (int i =0; i <n;i++) {
        r+=helper();
    }
    return r;
}

// helper that returns 0 or 1
private static int helper() {
    long t = System.nanoTime();
    if (t%2 == 0) {
        return 1;
    } else {
        return 0;
    }
}

He said it's not right but he wouldn't tell me what he was expecting. Why did he say it's wrong? How would you have done it differently?

Answer 1

Main issues with your approach:

• System.nanoTime() isn't (on its own) a useful source of random bits - it's highly likely to produce the same value multiple times in a row if you call it in quick succession because many systems don't actually have a sufficiently accurate timer. Even if it was nano-second-accurate, you are likely to get predictable patterns from the lowest bits if you sample it in a tight loop. Valid uses of System.nanoTime in random number generation might be: a) one-off initialisation of a seed value or b) occasionally adding some extra randomness into an entropy pool (not guaranteed to be beneficial, but it can't hurt)
• Even if the bits were truly random, by adding the 0/1 values n times you would be creating a binomial-style distribution with a mean of n/2, i.e. not a uniform distribution which is presumably what the interviewer was expecting.
• Your algorithm is O(n) - not good for generating random numbers with a large value of n!

You ideally want a PRNG that produces new pseudo-random bits from an internal state. Here's the one I use:

private static volatile long state = 0xCAFEBABE; // initial non-zero value

public static final long nextLong() {
  long a=state;
  state = xorShift64(a);
  return a;
}

public static final long xorShift64(long a) {
  a ^= (a << 21);
  a ^= (a >>> 35);
  a ^= (a << 4);
  return a;
}

public static final int random(int n) {
  if (n<0) throw new IllegalArgumentException();
  long result=((nextLong()>>>32)*n)>>32;
  return (int) result;
}

This is based on George Marsaglia's XORShift algorithm. It produces good pseudorandom numbers and is very fast (typically even faster than a Linear Congruential Generator since the xors and shifts are cheaper than multiplies and divides on most hardware).

Having said that, I wouldn't expect people to memorise this kind of algorithm for an interview unless you are specifically applying for a role as a crypto programmer!

Answer 2

first you have a binomial distribution (values towards n/2 are more likely to occur than 0 or n-1)

a better way would have been to generate ceil(log2(n)) bits and returning the value when the value is less than n and restarting otherwise

public static int random(int n) {
    while(true){
        int r = 0;
        for (int i =1; i<n;i<<=1) {
            r=(r<<1)|helper();
        }
        if(r<n)return r;
    }
}

also nanoTime() is only as accurate as the system can provide, which means that t%2 might be biased 1 or 0. Calling it in such a tight loop gives a very high likelihood of the returned values being the same on a machine with a low accuracy

a much better solution would be implementing a proper RNG like a Linear congruential generator and using that for the generation of the random bits

Answer 3

As others have said, the problem is that you're summing your bits. When choosing a number between 0 and 4 your algorithm would pick a two most of the time because there are many more ways to get a two by summation of the bits:

0: 0+0+0+0
1: 1+0+0+0, 0+1+0+0, 0+0+1+0, 0+0+0+1
2: 1+1+0+0, 1+0+1+0, 1+0+0+1, 0+1+1+0, 0+1+0+1, 0+0+1+1  
2: 0+1+1+1, 1+0+1+1, 1+1+0+1, 1+1+1+0
4: 1+1+1+1

Using bit shifts would have given you a lot better distribution, but you'd still be getting bad values from a timer in a tight loop.

I don't know for sure but I'd imagine there are well-tested normally distributed hash functions in Java's standard libraries. Starting with a seed of, say the timer, you could do something like this:

randomBits = hashFunction(seed)
seed = randomBits
return seed % n

I'm no mathematician and I'm a bit worried that the modulo at the end might skew the distribution, but it would be a lot more random than summing bits and could be written quickly in an interview.

Answer 4

A simple class of random number generators are the linear congruential generators, which generate numbers through state = (state * a + b) % c.

Java's Random class works exactly like that, using the system time as initial state. The state in java.util.Random has a size of 48 bits, while it only ever returns at most 32 bits of that, so it looks "quite random". LGCs aren't great random number generators, but they do their job if only few values are needed.

Answer 5

He probably expected you to use Java's Random class.

Your current implementation takes a sum of "coin toss" results to determine a random number. While your results will be somewhat random, they won't be evenly distributed. If you roll two dice, you'll end up with a total of 7 roughly half the time. This approach to random number generation is subject to the same math.

The people who implement Java's libraries have gone out of their way to solve a lot of the issues around random number generation, and it's usually best to use them when they offer a solution to your problem. No need to reinvent the wheel.

If you want to know how to produce a good Random number generator, you can always read up on how Java implements theirs!

Answer 6

To ratchet freak's answer I would add that the interviewer probably considered your use of System.nanoTime() as cheating since, in a way, it's an external random number generator, though not a very good one by itself.

He probably wanted you to implement a clearly deterministic generator from scratch, as the one from Wikipedia pointed out by ratchet freak.

Answer 7

You could use your current implementation to provide good (not great) random 0 or 1 by adding a timer for some entropy. We ran a small contest and this solution was among the best - you were very very close:

public static void random(int iterations) throws InterruptedException{
    for(int i = 1 ; i <= iterations ; i++){
        System.out.print(System.nanoTime() % 2);
        Thread.sleep(0, 200);
        if(i % 1000 == 0){
            System.out.println();
        }
    }
}

Answer 8

Here's the correct answer: Creating a good random number generator is difficult. If it's not something you have specifically learned, then it is impossible to come up with anything remotely useful. If you have learned about it, then it's still not something that you would likely be able to do from memory.

You might know about a linear congruential random number generator, but there are some constants involved that need some very very tricky analysis to get right. Something you'd look up on the internet. You might have heard of Marsaglia's KISS algorithm, or the Mersenne twister. Each one you wouldn't even try to implement without looking up the details on the internet.

There are very few programming jobs where I would hold it against you if you cannot write a good random number generator. That said, what you should say is: "I have never done this, I don't know if the result would be any good". Then write an algorithm - coming up with anything is positive. And then the important thing: Write some code that tests the random number generator. For example, use n = 20 and check that the result is never less than 0 or greater than 20, and print out how often each number from 0 to 20 comes up in 2100 calls (you'd hope that each comes up about 100 times).

In practice, outside an interview, you'd need someone who knows better how to write a random number generator than the guys responsible for the code in the Java library. That person would be quite rare.