RANDOM Number Generation in C

Question

Recently i have begun development of a simple game. It is improved version of an earlier version that i had developed. Large part of the game's success depends on Random number generation in different modes:

MODE1 - Truly Random mode

myRand(min,max,mode=1);

• Should return me a random integer b/w min & max.

MODE2 - Pseudo Random : Token out of a bag mode

myRand(min,max,mode=2);

• Should return me a random integer b/w min & max. Also should internally keep track of the values returned and must not return the same value again until all the other values are returned atleast once.

MODE3 - Pseudo Random : Human mode

myRand(min,max,mode=3);

• Should return me a random integer b/w min & max. The randomisation ought to be not purely mathematically random, rather random as user perceive it. How Humans see RANDOM.

* Assume the code is time-critical (i.e. any performance optimisations are welcome)

* Pseudo-code will do but an implementation in C is what i'm looking for.

* Please keep it simple. A single function should be sufficient (thats what i'm looking for)

Thank You

Answer 1

As a first step, go and read Knuth

Answer 2

You can use a linear feedback shift register for the mode 2, if max-min = 2^N-1. This kind of random generator produces a repeating sequence of 2^N-1 numbers with N bit internal storage. See http://en.wikipedia.org/wiki/LFSR for a more detailed explanation and code.

Answer 3

First, research the Mersenne Twister. This should be an excellent foundation for your problem.

Mode 1: Directly use the values. Given that the values are 32 bit, depending on the ranges of min and max, modulo (max-min+1) may be good enough, though there is a small bias if this interval is not a power of two. Else you can treat the value as a float value between 0 and 1 and need some additional operations. There may be other solutions to get equal distribution with integers, but I haven't researched this specific problem yet. Wikipedia may be of help here.

Mode 2: Use an array that you fill with min..max and then shuffle it. Return the shuffled values in order. When you're through the array, refill and reshuffle.

Mode 3 is the most complicated. Small amounts of random values show clusters, i.e. if you count the occurrences of the different values, you have an average value and the counts are usually above or below this average. As I understand your link, humans expect randomness to have all counts exactly on the average. So count the occurrences and give the different values a higher probability, depending on their distance to the average count. It may be enough to simply reuse mode 2 with a multiple array, e.g. use an array 10 times the size of (max-min+1), fill it with 10x min, 10x min+1, and so on, and shuffle it. Each full 10 rounds you then have the counts exactly equal.

EDIT on mode 3:

Say you have min=1 and max=5. You count the occurrences. If they all have the same probability (which they should using a good random generator), then this probability for each value to occur is 0.2, because the probabilites add up to 1.0:

Value Occur Probability
1     7x    0.2
2     7x    0.2
3     7x    0.2
4     7x    0.2
5     7x    0.2
Average: 7x

But now let's say that 3 occured only 5x and 5 occured 9x. If you want to hold the equal distribution, then 3 has to become a higher probability to catch up with the average occurrence, and 5 has to become a lower probability to not grow so fast until all the other values catched up. Nonetheless all the individual probabilities must add up to 1.0:

Value Occur Probability
1     7x    0.2
2     7x    0.2
3     5x    0.3
4     7x    0.2
5     9x    0.1
Average: Still 7x

The different occurrences should have different probabilities, too, depending on their distance to the average:

Value Occur Probability
1     10x   0.05
2     4x    0.35
3     5x    0.3
4     7x    0.2
5     9x    0.1
Average: Still 7x

Not that trivial to implement and most likely very slow, because the random generator still provides equal probabilites, so a modified mode 2 may be a good-enough choice.