Jump to content
  • Advertisement
Sign in to follow this  
jollyjeffers

relying on C/C++'s rand() function

This topic is 4565 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Thanks for the replies!

Quote:
The game programming gems series 1, 2 and 5 contain some article on rng,
maybe that will help...
Thanks for the tip, but I've left those books in storage at the moment [rolleyes]. Will have to settle for wikipedia for now!

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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Boost has a slew of PRNGs, including a pair of Mersenne Twisters.
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]

Quote:
Original post by Fruny
In either case, there is no need to actually roll your own. [smile]
I acquired this one (from here) in the end.

Initial results just by swapping like-for-like are substantially better: .

Cheers,
Jack

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Don't shy away from the simplicity of an LCG if it happens to suit your PRNG needs :)

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!