# the random number problem

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 07-10-2011
achitan
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.
• 07-10-2011
laserlight
Quote:

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).

Quote:

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.
• 07-10-2011
achitan
thank you
Thank you, laserlight!
I'll look into that. I'm new to C++ random number generation (also to C++, as a matter of fact).
• 07-10-2011
laserlight
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).
• 07-10-2011
achitan
all cards on the table, I'm using g++ compiler in an up-to-date Ubuntu 11.04 x_64 version
• 07-10-2011
quzah
Quote:

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.
• 07-10-2011
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...
• 07-10-2011
laserlight
Quote:

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.
• 07-10-2011
manasij7479
Quote:

Originally Posted by quzah
If a number is random, it should have numbers twice in a row 1/Nth of the time.
Quzah.

Can you explain the logic behind that? ..or point me towards a mathematical proof ?
• 07-10-2011
laserlight
Quote:

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.
• 07-10-2011
manasij7479
Quote:

Originally Posted by laserlight
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.

How stupid of me to have missed(asked before thinking ) that after I did a whole exercise full of Permutation problems this morning ....
• 07-10-2011
quzah
Quote:

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.
• 07-10-2011
King Mir
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.
• 07-10-2011
phantomotap
Quote:

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.
Periodicity is practicably determined by the size of entire state of the "PRNG" and not just the size of the state that the "PRNG" naturally samples.

It is very likely that the periodicity of a "PRNG" is greater by far.

Soma
• 07-11-2011
rogster001
Thought i would point you in direction of a good mersenne twister implementation, this one is useful as it is easy to incorporate into your own code and it comes with a variety of examples in source code files.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last