Sign in to follow this  

random number question

This topic is 3461 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

Is there some way I can have two instances of rand? The reason is that for the actaul gameplay I want one, (which I will set and record the seed of at the start of the level), then a seprate one for user stuff (eg which of 3 diffrent things does a unit say when given a move order). This way I can "replay" a level just by tracking the commands given to the units etc each update, and the level will play out exactly the same. (without having to also track everything the player does that might result in a call to rand()) Also for multiplayer this means that things won't get out of sync because rand() was called for UI purposes or something on only one client.

Share this post


Link to post
Share on other sites
Yes: Don't use a random number generator like rand() which stores its state in a hidden, implementation-defined way. Instead, use something like boost::random, which is very flexible and allows you to save and reload the state of the RNG. There's also a C interface for reentrant rand() named rand_r(), but it isn't nearly as flexible.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
Is there some way I can have two instances of rand?

Sure, the last resort is to write your own Pseudo Random Number Generator class. The easiest principle is to initialize a number x with a seed and then get the next random number by doing

x := x * a + c

See Wikipedia article for further reading. There you also find nice values for a and c.

Here is my improvised stab at the problem. You can provide your own seed or let the implementation choose one based on time and a smear value. This ensures that multiple instances created within the same second still start with different seeds - time(0) only changes once per second.

class MyRand
{
static unsigned smear;
unsigned random;
public:
const unsigned seed;

MyRand(unsigned seed = time(0) ^ smear): random(seed), seed(seed)
{
smear = smear * 1103515245 + 12345;
}

void rewind()
{
random = seed;
}

unsigned operator()()
{
return random = random * 69069 + 5;
}

unsigned operator()(unsigned bound)
{
return operator()() % bound;
}

int operator()(int min, int max)
{
return operator()(max - min + 1) + min;
}
};

unsigned MyRand::smear(0);

int main()
{
MyRand r;
MyRand s;

std::cout << r() << std::endl;
std::cout << r() << std::endl;
std::cout << r() << std::endl << std::endl;

std::cout << s() << std::endl << std::endl;

r.rewind();
std::cout << r() << std::endl;
std::cout << r() << std::endl;
std::cout << r() << std::endl << std::endl;

MyRand t(r.seed);
std::cout << t() << std::endl;
std::cout << t() << std::endl;
std::cout << t() << std::endl << std::endl;
}


Note how you get the exact same sequence of numbers by either
a) rewinding r, or
b) initializing t with r's seed

The operator()(unsigned bound) implementation isn't very good, because with even bounds, the least significant bit always flips, so for example successive calls to r(10) will yield ...odd-even-odd-even-odd-even... numbers. I tried to improve it, but I'm not 100% sure my approach is correct:

unsigned operator()(unsigned bound)
{
/* 1 */ unsigned div = std::numeric_limits<signed>::min();
/* 2 */ div /= bound;
/* 3 */ return operator()() / div >> 1;
}

I would actually love to write

div = (std::numberic_limits<unsigned>::max() + 1) / bound;
return operator()() / div;

but of course a number one greater than the maximum is very unlikely to exist ;-)



Aha, my gut feeling was right, I found a corner case where operator(int bounds) yielded an illegal value.

In line 2, we do an integer division. If div is not an integral multiple of bound (this is true for every number made up of prime factors other than 2), we throw away the fractional part, thus effectively rounding down. That means div is actually a little too small, and for some (very few) large values of random, the division in line 3 yields a value that is too high (exactly bound, but the result should be lower than bound).

The workaround is to perform the first division with rounding up. In integer arithmetic, we can emulate a/b with rounding up by doing (a+b-1)/b.

unsigned operator()(unsigned bound)
{
unsigned div = std::numeric_limits<signed>::min();
div += bound - 1; // the next division should round up...
div /= bound;
return operator()() / div >> 1; // ...so that this division nexer exceeds bounds
}

This would have been a very hard to trace bug. What do we learn from this?
a) Always test corner cases. Just see what happens if random has the highest possible value.
b) Don't reinvent the wheel, use boost::random ;-)

There are still issues to fix, for example very high values of bound will yield nonsense values because of overflow, plus min and max should be checked for consistency.

We can even prove that this fix indeed does produce correct values by checking all legal values for bound:

for (unsigned i = 1, k = std::numeric_limits<signed>::max(); i <= k; ++i)
{
unsigned div = std::numeric_limits<signed>::min();
div += i - 1; // fix
div /= i;
unsigned x = std::numeric_limits<unsigned>::max() / div >> 1;
if (x >= i) std::cout << i << std::endl;
}

This takes about a minute to prove on my computer. If you take away the "// fix" line, you get all numbers that are not powers of two, as I predicted.

[Edited by - DevFred on June 23, 2008 5:09:25 PM]

Share this post


Link to post
Share on other sites
I took a look at the boost\random but that really confuses me on how to do what I want...


class DLL Random
{
public:
virtual double Uniform()=0;//0 <= x < 1. Uniform distribution
virtual double Uniform(double Min, double Max)=0;//Min <= x < 1. Uniform distribution
virtual double Gaussian()=0;//0 <= x < 1. More dense in the centre
virtual double InverseGaussian()=0;//0 <= x < 1. Inverse

virtual unsigned GetSeed()=0;
virtual void SetSeed(unsigned s)=0;
};




Basicly I want to have at least that functionality, so that I can just pass a pointer to my functions.

I'll take a look at DevFred's implemntation, at least I can follow whats going on there :)

[Edited by - Sync Views on June 23, 2008 5:19:04 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
I'll take a look at DevFred's implemntation, at least I can follow whats going on there :)

You're welcome. Before you get into any trouble because of static member initializations and header files, I split the latest version up for you:

myrand.h
#ifndef MYRAND_H
#define MYRAND_H

#include <ctime>
#include <limits>

class MyRand
{
static unsigned smear;
unsigned random;
public:
const unsigned seed;

MyRand(unsigned seed = time(0) ^ smear): random(seed), seed(seed)
{
smear = smear * 1103515245 + 12345;
}

void rewind()
{
random = seed;
}

unsigned operator()()
{
return random = random * 69069 + 5;
}

unsigned operator()(unsigned bound)
{
unsigned div = std::numeric_limits<signed>::min();
div += bound - 1;
div /= bound;
return operator()() / div >> 1;
}

int operator()(int min, int max)
{
return operator()(max - min + 1) + min;
}
};

#endif


myrand.cpp
#include "myrand.h"

unsigned MyRand::smear(0);


your own code
#include "myrand.h"
#include <iostream>

int main()
{
MyRand test;
std::cout << test(10) << std::endl;
}


Have fun with it and report any problems you have.

Share this post


Link to post
Share on other sites
I implemented you generator into my class, although I changed how the number is returned to this for the 0 <= x < 1 range:
return (double)r / (std::numeric_limits<unsigned>::max)();


class rng : public Random
{
unsigned r,s;
public:
rng();
rng(unsigned s);
virtual unsigned GetSeed();
virtual void SetSeed(unsigned s);

virtual double Uniform();
virtual double Uniform(double Min, double Max);
};




rng::rng()
{
r = s = (unsigned)(time(NULL) % 0xFFFFFFFF);//so it works with a 64bit time stamp
}
rng::rng(unsigned int _s)
: r(_s), s(_s)
{}
unsigned rng::GetSeed()
{
return s;
}
void rng::SetSeed(unsigned _s)
{
r = s = _s;
}
double rng::Uniform()
{
r = r * 69069 + 5;
return (double)r / (std::numeric_limits<unsigned>::max)();
}
double rng::Uniform(double Min, double Max)
{
return Uniform()*(Max - Min) + Min;
}



So I made a quick test to see if this worked, and got some intresting results

rng::uniform()
Tests: 100000000
Distribution over 0.1 blocks:
0.0999577
0.0999817
0.1000150
0.0999711
0.1000210
0.1000200
0.0999882
0.1000030
0.1000170
0.1000260
000000000
Time taken: 4.25 seconds
Numbers per second: 23529000

rand()/(double)RAND_MAX
Tests: 100000000
Distribution over 0.1 blocks:
0.0999927
0.0999800
0.1000170
0.0999700
0.0999731
0.0999819
0.0999994
0.1000150
0.1000210
0.1000190
3.044e-005 <--ok...so why are there results over 1?
Time taken: 8.032 seconds
Numbers per second: 12450000


[Edited by - Sync Views on June 24, 2008 8:40:15 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
3.044e-005 <--ok...so why are there results over 1?

Your fault is in this line of code:

return (double)r / (std::numeric_limits<unsigned>::max)();

What happens if r IS std::numeric_limits<unsigned>::max()? You get exactly 1. You need to divide by one more, but since that number isn't representable as an unsigned, you have to cast that to double first.
Rewrite the line to this and tell me if that fixes the problem:

return r / (1.0 + std::numeric_limits<unsigned>::max());

Furthermore, why do you inherit from Random?

Plus this line of code looks silly:

r = s = (unsigned)(time(NULL) % 0xFFFFFFFF);//so it works with a 64bit time stamp

If you want the lowest 32 bit, don't divide by 0xFFFFFFFF, but instead BITWISE AND by 0xFFFFFFFF. Plus you don't really need that, just assign to s and r. It will get truncated automatically:

r = s = (time(NULL);

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
THe thing is, the test that failed was with the standard rand()...

Oh :) Well, you also have to divide by one more than the maximum with rand() if you want to get values < 1.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
3.044e-005 <--ok...so why are there results over 1?


3.044e-005 is scientific notation for 0.00003044 ;) so it's not generating over 1 at all, just closer to 0.

Share this post


Link to post
Share on other sites
Quote:
Original post by nightech
Quote:
Original post by Sync Views
3.044e-005 <--ok...so why are there results over 1?

3.044e-005 is scientific notation for 0.00003044 ;) so it's not generating over 1 at all, just closer to 0.

Look at what the numbers represent. About 10% of the generated numbers are between 0 and 0.1, another 10% between 0.1 and 0.2 and so forth. What the OP didn't understand why there was "more than no" number betwenen 1.0 and 1.1 (it's because 1 is between 1.0 and 1.1).

Share this post


Link to post
Share on other sites
How much faster than two additions, one multiplication and one division can you get? I presume rand() is tied by some ancient specification regarding its output values, but I really dunno.

Share this post


Link to post
Share on other sites
Quote:

Now what i'm wondering is how come it's faster than the standard rand() that I assumed was optimised?


The pseudo random number generator in MSVC is awful. Never really heard of anyone who actually uses it. I don't think it's even truly uniform and it has a really bad period length. The recommendation of using boost::random is really the best recommendation. In there they have several versions of the Mersenne Twister which is very fast, uniform and has a really good period length. It's really good for Monte Carlo simulations but doesn't work at all for cryptography though, not that the MSVC one is any better. There are faster implementations than the boost Mersenne Twister version but I doubt that's where your bottleneck will be.

Share this post


Link to post
Share on other sites
Quote:
Original post by DevFred
I would actually love to write

div = (std::numberic_limits<unsigned>::max() + 1) / bound;
return operator()() / div;
but of course a number one greater than the maximum is very unlikely to exist

Then perhaps you need to investigate Schrage's algorithm.

You also need to make sure you choose your constants correctly and that the seed value of your sequence is adjusted to avoid pathalogical conditions. Writing a simple PRNG is not as easy as it appears.

The Boost PRNGs are similar to the TR1 PRNGs and will do exactly what you need. They're entirely in header files so no extra linkifications. They're very well tested and verified by experts in the field.

The tr1 PRNGs (at least) also provide streamable states so you can save and restore the state of the PRNG, or even exchange it over the wire to synch between, say, client and server. For multiplayer thyat could be a bonus.

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
Writing a simple PRNG is not as easy as it appears.

That's why I started my first reply with the following words:
Quote:
Original post by Bregma
the last resort is to write your own Pseudo Random Number Generator class

Share this post


Link to post
Share on other sites
I still don';t really get the boost thing though...


class mt : public Random
{
boost::mt19937 mt((unsigned)time(NULL));
public:
virtual double Uniform()
{
static boost::variate_generator
<boost::mt19937& ,boost::uniform_real<>>
rng(mt,boost::uniform_real<>(0,1));//Is this 0 <= x < 1? The docs don't seem to say...
return rng();
}
virtual double Uniform(double Min, double Max(
{
//Isn't there a way to avoide creating all this for EVERY number?
//but then wouldn't multipliying the above be pretty bad having already mapped it to 0...1?
boost::variate_generator
<boost::mt19937& ,boost::uniform_real<>>
rng(mt,boost::uniform_real<>(Min, Max);
return rng();
}
};

Share this post


Link to post
Share on other sites
Quote:
Original post by Sync Views
Isn't there a way to avoide creating all this for EVERY number?

Sure, just construct the necessary objects ONCE and then create random numbers. After reading the docs for 5 minutes, this is a small example I copy-and-pasted together with minor mods, works great:

#include <iostream>
#include <boost/random.hpp>

int main()
{
boost::mt19937 generator(42u);
boost::uniform_real<> uni_dist(0, 1);
boost::variate_generator<boost::mt19937&, boost::uniform_real<> > uni(generator, uni_dist);

for (int i = 0; i < 100; ++i)
std::cout << uni() << std::endl;
}

It looks like you're still creating or own class... why do you do this? Just use the existing boost classes.

Share this post


Link to post
Share on other sites
If you use boost, you'd use a uniform_real distribution that you supply the arguments 50 and 100. See DevFred's post for other details.

Share this post


Link to post
Share on other sites
I think you guys are misunderstanding: he's concerned about performance. ;) He doesn't want to reconstruct an object for each range in which he wants a random number; and he figures that if he reuses an object with a specific range and re-maps the range manually, that he's lost the benefit of that functionality (and possibly lost performance by redundantly mapping a range that the object will map internally).

But honestly, you don't really have to worry about these kinds of things. My guess is that the variate_generator class is designed to be quite light-weight, so reconstructing it for the range is appropriate. Keep in mind that you don't need a named temporary here, either:


// should be fine
return boost::variate_generator<boost::mt19937& ,boost::uniform_real<>>(mt,boost::uniform_real<>(Min, Max)();


The reason variate_generator is an object rather than a free function, presumably, is so that you can use it as a functor - say, for example, to pass to std::generate() to draw several numbers in the same range.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
I think you guys are misunderstanding: he's concerned about performance. ;)

Erm, ok, so he needs like a million random numbers per second or what?

Share this post


Link to post
Share on other sites

This topic is 3461 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this