Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
Did he specify that you needed to return deviates from the uniform distribution? –  James McLeod May 26 '12 at 2:32
3  
I assume he didn't say he wanted a good one. Most people don't know how to make a good one, and even if one did, there are many ways to do it. So there's no one "right" solution. I'd call yours good enough, given that simple ones that use bit shifting and XOR aren't very random. If you were on a Linux system, you could read from /dev/random, but that might be cheating. –  Barry Brown May 26 '12 at 3:06
3  
Next time, tell them that such tests are called reinventing a square wheel –  jfrankcarr May 26 '12 at 5:26
2  
@jfrankcarr: Absolutely, I'd have answered - "Why bother, there have been better mathematicians than I writing these for years. Use those" –  James May 26 '12 at 10:52
1  
@AndresF.: A decent enough kernel samples true sources of randomness - network background noise, disk access timing deviations, etc. - and massages the result into a uniform distribution. This is about as random as it gets, and it is very different from a pseudo-random number generator which, given its current state, is 100% deterministic. –  tdammers May 26 '12 at 22:38

6 Answers 6

up vote 11 down vote accepted

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 long volatile 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!

share|improve this answer

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!

share|improve this answer
    
I wish! He strictly told me any use of random library methods are forbidden –  paul smith May 26 '12 at 2:24
1  
@paulsmith: These are good details to provide in the question when you ask it to ensure that people give you good answers. For what it's worth, I doubt that 99% of Java developers could produce a decent pseudo-random generation algorithm. The best I could do would probably be to take the system time and mod it with n. –  StriplingWarrior May 26 '12 at 2:31
9  
@paulsmith apparently, he expected you to know a PRNG algorithm. If it's relevant to the job, it might be fit, although it still seems a bit far fetched as an interview question to me. –  kaoD May 26 '12 at 2:33

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

share|improve this answer
    
I see. So then how would you have done it? –  paul smith May 26 '12 at 2:31
    
@paulsmith I don't understand why they asked this from you tbh... at best you could have memorised any of the many algorithms out there as they are incredibly simple when someone has already chosen the right constants. And what would have that proven anyway? –  Esailija May 27 '12 at 14:46
    
@Esailija maybe implementing prngs is part of the job? maybe the job has a lot of probabilistic stuff involved and they were less interested in the implementation but more in what the candidate knew about probability distributions ? maybe the interviewer is an idiot - we may never know ;) –  jk. May 28 '12 at 8:30

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.

share|improve this answer
    
This sounds like a time to point to search.dilbert.com/comic/Random%20Number%20Generator –  Donal Fellows May 26 '12 at 14:44

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.

share|improve this answer
    
+1 for illustrating summation of bits –  Kenneth May 27 '12 at 11:12

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.