RANDOM number generation in C

Question

I recently started developing a simple game. This is an improved version of an earlier version that I developed. Most of the success of the game depends on the generation of random numbers in different modes:

MODE1 - real random mode

myRand (min, max, mode = 1);

• Must return me a random integer b / w min and max.

MODE2 - Pseudo Random: token from summation mode

myRand (min, max, mode = 2);

• Must return me a random integer b / w min and max. It is also necessary to internally monitor returned values ​​and not return the same value until all other values ​​are returned at least once.

MODE3 - Pseudo Random: Human mode

myRand (min, max, mode = 3);

• Must return me a random integer b / w min and max. Randomization should not be purely mathematically random, but random, as the user perceives it. How people see it RANDOMLY .

* Assume that the code is time critical (for example, any performance optimization is welcome)

* Pseudocode will do, but implementation in C is what I am looking for.

* Please keep it simple. One function should be enough (this is what I'm looking for)

thanks

Answer 1

First, explore the Mersenne Twister. This should be a great basis for your problem.

Mode 1: Use the values ​​directly. Given that the values ​​are 32 bits, depending on the ranges of min and max, modulo (max-min + 1) can be quite good, although there is a slight bias if this interval is not equal to two. In addition, you can treat the value as a floating point value between 0 and 1 and perform some additional operations. There may be other solutions for getting an equal distribution with integers, but I have not yet studied this specific problem. Wikipedia can 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 go through the array, replenish and drag.

Mode 3 is the most difficult. A small number of random values ​​show clusters, i.e. If you count occurrences of different values, you have an average value, and the number of values ​​is usually above or below this average. As far as I understand your connection, people expect that randomness will have all the meanings on average. Therefore, count the occurrences and give different values ​​a higher probability, depending on their distance to the average value. This may be enough to simply reuse mode 2 with multiple arrays, for example. use an array 10 times larger (max-min + 1), fill it with 10x min, 10x min + 1, etc. and shuffle it. Every complete 10 rounds you have exactly equal numbers.

EDIT in mode 3:

Say that you have min = 1 and max = 5. You count events. If they all have the same probability (that they should use a good random generator), then this probability for each value will be 0.2, since the probability values ​​are 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 happened only 5x and 5 happened 9x. If you want to maintain an equal distribution, then 3 should be more likely to catch up with the average, and 5 should be less likely to not grow so fast until all other values ​​are reached. However, all individual probabilities should be 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 

In different cases, there should also be different probabilities 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 probabilities, so modified mode 2 can be a pretty good choice.

Answer 2

As a first step, go read Knuth

Answer 3

You can use the linear shift feedback register for mode 2 if max-min = 2 ^ N-1. This random generator creates 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 4

human perception will be the same as in the first mode, except that the results, multiples of 2, 5, 10, can be arbitrarily rejected as a result.

If I asked for a random number and got 5 or 10, I would think that it is not random.