Thread: the random number problem

Hi, all!
I really need a good random number generator for a baseball simulator (nothing fancy, just playing with probabilities). Currently I'm using the rand() function, and I've made a little test program to see after how many generations will the "random numbers" repeat themselves, and the results look promising. After 100 tests I get a mean value of 1'803'626'901 un-repeated numbers, which is great. Below is the program I used to get this statistic:

Code:

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
	long unsigned int rand_nr = 0, rand_nr_new;
	long unsigned int i = 0, sum = 0;
	
	for(int j = 1; j <= 100; j++)
	{
		srand(time(NULL));
		i = 0;
		rand_nr_new = rand();
		while(rand_nr != rand_nr_new)
		{
			rand_nr = rand_nr_new;
			rand_nr_new = rand();
			i += 1;
		}
		sum += i;
	}
	cout << sum/100 << " iteratii." << endl;
}

(don't worry, the while loop takes more than a second so there won't be two identical seeds - on my dual core T2390)

Now, I should probably tell you how the simulator works. There is a class Team that generates the teams (it uses rand() to generate last season's AVG, SLG, SB% and ERA for the pitcher). Then there is a class Game, that simulates one game (its constructor is Game(Team *home, Team *away)). The game uses a function at_bat to see if the AB was successful for every player (it is a function that depends on the last year AVG and uses rand()). If the at_bat was successful, the hit function gets called to see what the player achieved (single, double, triple or homerun). For this, it uses a function dependent the last year SLG statistic of the player, and of course the rand() function. Add to this that a player may also try to steal a base (based on last year SB% - will try only if SB% is over .750) - another two rand()s, and you'll get a picture of why I need a more real random number generator (there will be over half a million rand()s in every season).
There are 30 teams, each playing 162 games. My solution was to seed the random generator every time before a rand() call, with a function that made the program wait a second before srand. The results are encouraging, but for 162 games between 2 teams, I had to wait about 11'000 seconds (about 3h). The generation of two teams alone takes about 40 seconds.
The next idea, that I'm implementing right now, is to seed not just with srand(time(NULL)), but with srand(time(NULL)+clock()) after I make the program wait for 1/100 seconds. That will get my time down in the "reasonable domain".
But isn't there any way to create a more real random number generator? I heard about generating numbers using the raw inputs from your mouse, or some other hardware input that seems random. How would I go about that?

P.S. If I srand only once at the beginning of the program (in the main function before I start creating the teams, the results don't seem random at all: number of ABs is always a multiple of 10 as is the number of hits per team; one team also wins almost everything all the time (every time the away team). All this brought me to the idea that I need to srand (a different number of course) before every rand().
P.S. If you need to see the code I will gladly post it on request.

Originally Posted by achitan

My solution was to seed the random generator every time before a rand() call, with a function that made the program wait a second before srand.

That is dumb: you might as well take the time once, then before each call to rand(), increment the time value and then re-seed. Of course, this would still be dumb, though less dumb, as you would be better off exhausting the period of the PRNG before re-seeding.

I suggest that you look into PRNGs such as the Mersenne Twister instead of just using srand and rand. With a known algorithm, you could even consider saving the seeds so your experiments can be repeated exactly should you need to verify your results. Otherwise, you can still repeat your experiments, but if the algorithm changes say, when you switch compiler, you would be dealing with a different set of test data (which is not necessarily wrong, but might not allow you to check interesting aspects of your results).

Originally Posted by achitan

But isn't there any way to create a more real random number generator? I heard about generating numbers using the raw inputs from your mouse, or some other hardware input that seems random. How would I go about that?

You're not doing cryptography, so that would probably be overkill. That said, on a *nix system /dev/random may be available as a source of random numbers. I would consider it more of an alternative source for your seed values for a good PRNG rather than as the main RNG though.

Oh, and you may be able to get a Mersenne Twister implementation from a standard library implementation near you as it is included in the TR1 extensions to the standard library. This article on Random number generation using C++ TR1 explains more. If you are using a sufficiently updated compiler, it may even be included directly in the standard library (i.e., not in the std::tr1 namespace, but in the std namespace).

Originally Posted by achitan

I've made a little test program to see after how many generations will the "random numbers" repeat themselves

If a number is random, it should have numbers twice in a row 1/Nth of the time. Why would you even care if a number came up twice in a row?


Quzah.

Originally Posted by achitan

Because I heard that calling rand() multiple times will give you a sequence of random numbers that will repeat itself after a while (keeping the same seed). So it was just an exercise in statistics.
But if a number in a rand() sequence never repeats, then that's a condition which makes rand() not a very good random number generator. Anyway, back to Mersenne Twister...

Then you completely misunderstand. Seeding the prng once and then making many many calls to rand will give you the longest sequence possible until it repeats. Calling srand again at any point will not give you a completely new sequence. What that actually does is jump to a different point within the same sequence. Thus you immediately jump yourself closer to part of the sequence that you've come across more recently. So by ever calling srand more than once you will always get something that is actually less random!

Whatever test you're done that you think suggest otherwise are wrong. If your jumping around appears to make it take longer to get around to a certain value, then in reality what you're actually doing is causing many other values to come up more often instead, and in fact often causing the same sequence of values to come up again. It's worse, not better, trust me.

Originally Posted by manasij7479

Can you explain the logic behind that? ..or point me towards a mathematical proof ?

*hands out a pen and paper RPG, and a bag of dice*

Now go find some friends, and come back next weekend, and tell me how it went!


Quzah.

Originally Posted by achitan

Because I heard that calling rand() multiple times will give you a sequence of random numbers that will repeat itself after a while (keeping the same seed).

Yes, hence my reference to the period of the PRNG. However, this is a repetition of the sequence generated, not of any particular number that was already generated. Looking at "the program (you) used to get this statistic", you were actually merely searching for a pair of consecutively generated numbers with the same value.

Originally Posted by manasij7479

Can you explain the logic behind that? ..or point me towards a mathematical proof ?

I think that quzah just means that given a uniform random distribution, having selected one number out of N possible numbers, with replacement, the probability of selecting the same number next is 1/N. It is related to a common perception that once you have rolled a fair die to get a number, it is somehow less likely that that number will be rolled again next.

Using a known algorithm instead of rand is a good idea, but either way, the periodicity of the random number generator is likely to be MAX_INT-1. So the OP's concern is a non issue.