Thread: the random number problem

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    9

    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.
    Last edited by achitan; 07-10-2011 at 01:32 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Last edited by laserlight; 07-10-2011 at 01:50 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jan 2011
    Posts
    9

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

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Jan 2011
    Posts
    9
    all cards on the table, I'm using g++ compiler in an up-to-date Ubuntu 11.04 x_64 version

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by achitan View Post
    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.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User
    Join Date
    Jan 2011
    Posts
    9
    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...

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by quzah View Post
    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 ?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Last edited by laserlight; 07-10-2011 at 07:54 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    Quote Originally Posted by laserlight View Post
    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 ....

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by manasij7479 View Post
    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.
    Hope is the first step on the road to disappointment.

  13. #13
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  14. #14
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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

  15. #15
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    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.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with random number
    By ~C_Student~ in forum C Programming
    Replies: 9
    Last Post: 11-22-2009, 11:51 AM
  2. problem with random number generator
    By Niss in forum C Programming
    Replies: 6
    Last Post: 10-01-2008, 06:03 PM
  3. Problem with random number generation
    By HAssan in forum C Programming
    Replies: 1
    Last Post: 03-27-2007, 05:49 PM
  4. Random Number Range Problem.
    By xamlit in forum C Programming
    Replies: 11
    Last Post: 01-26-2006, 12:55 PM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM