relying on C/C++'s rand() function
Afternoon all...
I'm working on some AI-related search techniques (not hugely relevant though) that rely quite heavily on random numbers. Simple stuff like seeding lists of float's, picking a random sample from a list etc...
Anyway, I can't (yet) find fault with my implementation - but the results when dumped to Excel seem to point the finger at the rand() function.
I keep getting odd patterns where rand() will generate the same numbers repeatedly or the general distribution of randomness is a bit, well, un-random [lol]
I don't know much about the stock rand() implementation (Visual C++ 2005), but I've always been working on the general assumption that its nothing special.
Would it be a reasonable step to "blame" the PRNG?
Either it's just crap and I need to roll my own (Mersenne Twister seems nice) or I possibly need to change my usage of it.
My usage:
At the start of each search with my algorithm I use srand( GetTickCount( ) ) to seed the generator. I then call rand() whenever I require a random number - probably 500x per iteration with 1000's of iterations.
I use a simple (rand() % Max) to pick a random integer (e.g. when picking an index for a random sample from an array), and (static_cast< float >( rand() ) / static_cast< float >( RAND_MAX )) when I want a random value between 0.0 and 1.0 (often scaled to be a float within a given min/max range).
I've tried various methods of srand() - never, once at application start, once at algorithm start, once every iteration, or every N iterations etc...
I wanted to check with the infinite wisdom and knowledge of GDNet before I try implementing a new PRNG algorithm. Would be a waste of valuable time if my usage of rand() is just wrong or a different PRNG won't actually make any difference (etc..)
Cheers,
Jack
Oh, one other thing...
Whilst running a forum search I came across a suggestion from Fruny about std::random_shuffle(). I'll see about trying that, but another comment in the same thread seemed to indicate that random_shuffle() would just use rand() internally - which strikes me as being no better than what I have. Or is it?
Cheers,
Jack
Whilst running a forum search I came across a suggestion from Fruny about std::random_shuffle(). I'll see about trying that, but another comment in the same thread seemed to indicate that random_shuffle() would just use rand() internally - which strikes me as being no better than what I have. Or is it?
Cheers,
Jack
The standard random function looks sth (correct me if I'm wrong):
I32 rand(void)
{
mSeed = (mSeed * 214013L + 2531011L) >> 16;
return mSeed & 0x7FFF;
}
Looks pretty simple - so I'm guessing it doesn't perform great in
terms of returning 'random' values...
The game programming gems series 1, 2 and 5 contain some article on rng,
maybe that will help...
Regards
I32 rand(void)
{
mSeed = (mSeed * 214013L + 2531011L) >> 16;
return mSeed & 0x7FFF;
}
Looks pretty simple - so I'm guessing it doesn't perform great in
terms of returning 'random' values...
The game programming gems series 1, 2 and 5 contain some article on rng,
maybe that will help...
Regards
I had issues with rand(). It's slow, and if you're using it to create noise, it looks pretty un-random. I usually use a version of the Mersenne Twister which I found on the Internet somewhere.
Also, using modulo with rand() is A Bad Thing. The higher bits have more randomness to them, so something like int foo = (rand()&0x8000) >> 12; would be better.
Also, using modulo with rand() is A Bad Thing. The higher bits have more randomness to them, so something like int foo = (rand()&0x8000) >> 12; would be better.
Thanks for the replies!
Most of my arrays are between 10-250 in length, so my modulo will always be fairly small.
I think I'll go check out the Mersenne Twister and the non-modulus thing.
Cheers,
Jack
Quote:The game programming gems series 1, 2 and 5 contain some article on rng,Thanks for the tip, but I've left those books in storage at the moment [rolleyes]. Will have to settle for wikipedia for now!
maybe that will help...
Quote:Also, using modulo with rand() is A Bad Thing. The higher bits have more randomness to them, so something like int foo = (rand()&0x8000) >> 12; would be better.VERY interesting - very interesting indeed [grin]
Most of my arrays are between 10-250 in length, so my modulo will always be fairly small.
I think I'll go check out the Mersenne Twister and the non-modulus thing.
Cheers,
Jack
random_shuffle() uses rand() by default, but you can pass it a custom function to use instead.
Boost has a slew of PRNGs, including a pair of Mersenne Twisters.
In either case, there is no need to actually roll your own. [smile]
Boost has a slew of PRNGs, including a pair of Mersenne Twisters.
In either case, there is no need to actually roll your own. [smile]
Quote:Original post by FrunyAs stupid as it sounds, I've gotta stick to "vanilla" C/C++ for this particular prototype. Useful to note that Boost can help, but sadly not useful here [sad]
Boost has a slew of PRNGs, including a pair of Mersenne Twisters.
Quote:Original post by FrunyI acquired this one (from here) in the end.
In either case, there is no need to actually roll your own. [smile]
Initial results just by swapping like-for-like are substantially better: .
Cheers,
Jack
Quote:Original post by jollyjeffers
As stupid as it sounds, I've gotta stick to "vanilla" C/C++ for this particular prototype. Useful to note that Boost can help, but sadly not useful here [sad]
Then you need to get some better vanilla. See section 5.1. [grin]
OK, that's not helping, I know. [totally]
Interesting... so I understand that linked document is a guideline/preview of what might be coming in a C++ compiler sometime in the future..?
I don't really keep up with the latest-n-greatest from the ISO commities [smile]
Cheers,
Jack
I don't really keep up with the latest-n-greatest from the ISO commities [smile]
Cheers,
Jack
Don't shy away from the simplicity of an LCG if it happens to suit your PRNG needs :)
Perhaps something simple like this:
A naive implementation off the top of my head, you might be able to use a regular 32-bit seed type if you know more about how the CPU handles overflow (the basic equation is Rn+1 = 16807*Rn mod (232 - 1)). If this doesn't work for you then you can stick with the Mersenne Twister, but this is simple enough to quickly substitute in and test.
Perhaps something simple like this:
long long iSeed;long rand(){ iSeed = (iSeed * 16807) & 0x0000FFFF; return (long)iSeed;}
A naive implementation off the top of my head, you might be able to use a regular 32-bit seed type if you know more about how the CPU handles overflow (the basic equation is Rn+1 = 16807*Rn mod (232 - 1)). If this doesn't work for you then you can stick with the Mersenne Twister, but this is simple enough to quickly substitute in and test.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement