Sign in to follow this  
all_names_taken

Cross-platform deterministic randomization?

Recommended Posts

I'd like to do some procedural generation based on a seed that can be sent across network and produces identical results on both sides. My question is: does rand() in C++ standard libraries really behave exactly the same cross-platform given the same seed at the start? I heard somewhere that the number sequence generated is platform specific... In particular with RAND_MAX and all that stuff it seems a reasonable thing to believe... If that's the case, what library could you recommend to cheaply generate random numbers identically for all platforms? Basically I need this type of functionality:
bool getRandomYesOrNo(float chance);
float getRandomFloat(float low, float high); //random number within range
float getRandomInt(int low, int high); //random number within range
The quality of the distribution etc isn't overly important unless the range is very narrow e.g. 5-20 integer elements or such. Performance is more important for my purposes.

Share this post


Link to post
Share on other sites
momotte    171
perlin noise is not a uniform pseudo-random number generator, it's an algorithm that relies on a pseudorandom number generator to generate coherent noise.

OP> linear congruential generators, that's what rand() uses, implement your own rand() with one of these sets of constants, and you'll get the same results on different platforms.
you could also google "mersenne twister" if you want a better prng. although it's trickier to implement...

Share this post


Link to post
Share on other sites
rubicondev    296
+1 for Mersenne Twister.

Here's some code I wrote based on someone elses who I seem to have naughtily removed the credit from in my cpp file.



tU32 RZMerTwist::RandU32 (tVOID)
{
// Pull a 32-bit integer from the generator state
// Every other access function simply transforms the numbers extracted here

if (!left)
Reload();

left--;

tU32 s1;
s1 = *pNext++;
s1 ^= (s1 >> 11);
s1 ^= (s1 << 7) & 0x9d2c5680UL;
s1 ^= (s1 << 15) & 0xefc60000UL;

return (s1 ^ (s1 >> 18) )&RZ_RAND_MAX;
}


tVOID RZMerTwist::Seed (cU32 Seed)
{
// Seed the generator with a simple tU32
Initialize(Seed);
Reload();
}

tVOID RZMerTwist::Initialize (cU32 Seed)
{
// Initialize generator state with seed
tU32 *s = state;
tU32 *r = state;
int i = 1;
*s++ = Seed & 0xffffffffUL;
for( ; i < ParamN; ++i )
{
*s++ = ( 1812433253UL * ( *r ^ (*r >> 30) ) + i ) & 0xffffffffUL;
r++;
}
}


tVOID RZMerTwist::Reload (tVOID)
{
// Generate N new values in state
tU32* p=state;
tINT i;

for( i = ParamN - ParamM; i--; ++p )
*p = twist( p[ParamM], p[0], p[1] );

for( i = ParamM; --i; ++p )
*p = twist( p[ParamM-ParamN], p[0], p[1] );

*p = twist( p[ParamM-ParamN], p[0], state[0] );

left = ParamN, pNext = state;
}






EDIT: Found it when I realised I need to include the class desc:


// This file is based on the work of Makoto Matsumoto

class RZMerTwist
{
friend class RZRandom;

private:
static cINT ParamM = 397;
static cINT ParamN = 624;

tU32 state[ParamN];
tU32* pNext;
tINT left;

tU32 RandU32 (tVOID);
tVOID Seed (cU32 oneSeed);

tVOID Initialize(cU32 oneSeed);
tVOID Reload (tVOID);
tU32 hiBit( cU32& u ) const { return u & 0x80000000UL; }
tU32 loBit( cU32& u ) const { return u & 0x00000001UL; }
tU32 loBits( cU32& u ) const { return u & 0x7fffffffUL; }
tU32 mixBits( cU32& u, cU32& v ) const{ return hiBit(u) | loBits(v); }
tU32 twist( cU32& m, cU32& s0, cU32& s1 ) const { return m ^ (mixBits(s0,s1)>>1) ^ (0-loBit(s1) & 0x9908b0dfUL); }
};





RandU32() is the only function you need to call to get numbers out, after once calling Seed() of course. Both of these are private in the above as I have another static class the access this one with a wide range of useful stuff like getting random numbers in given ranges etc. Just make those two public or wrap your own stuff around them.

Also note that with this system there isn't a meaningful RAND_MAX. You get all 32 bits of random goodness, so it's basically 4 billion.

Share this post


Link to post
Share on other sites
Antheus    2409
Floats are not portable across *every* platform. They might behave exactly the same under some.

Then there's issues like DX resetting FP flags.

To have deterministic behavior, the simplest way is to get a PRNG implementation that does not use floats, then include that in your project. Preferably, it uses only integers and doesn't rely on overflow.

When dealing with floating points, just upscale to integers. 1% chance means 42==rand(100), or similar.


If cross-platform only means Windows and Linux, then boost is likely enough. If it involves Macs, then as long as you limit yourself to x86, there shouldn't be any big issues.

But in general, cross-platform has a very broad meaning.

Share this post


Link to post
Share on other sites
Jan Wassenberg    999
Mersenne Twister (MT) has a large state (as it must to reach the insanely long period of 2**19337) and isn't actually that fast unless an SIMD variant is used, which is no longer cross-platform.
It's surprising to see MT recommended because the 13 years since its publication have seen the development of at least one algorithm (WELL512) that outperforms it in all aspects (for this particular application).

Share this post


Link to post
Share on other sites
rubicondev    296
Quote:
Original post by Antheus
Floats are not portable across *every* platform. They might behave exactly the same under some.

Then there's issues like DX resetting FP flags.

To have deterministic behavior, the simplest way is to get a PRNG implementation that does not use floats, then include that in your project. Preferably, it uses only integers and doesn't rely on overflow.

When dealing with floating points, just upscale to integers. 1% chance means 42==rand(100), or similar.


If cross-platform only means Windows and Linux, then boost is likely enough. If it involves Macs, then as long as you limit yourself to x86, there shouldn't be any big issues.

But in general, cross-platform has a very broad meaning.
Tell me about it! Floats caused massive problems between the Mac and PC version of Defcon, which introversion solved by working in 32.32 fixed point. Which was great until we had to do this on the DS which couldn't do either.. :(

Good point about the random floats though. I only just noticed that he intends to use them in his wrapper function. +1 for this being a gotcha waiting to happen, but its fine if you know the platforms beforehand

Share this post


Link to post
Share on other sites
rubicondev    296
Quote:
Original post by Jan Wassenberg
Mersenne Twister (MT) has a large state (as it must to reach the insanely long period of 2**19337) and isn't actually that fast unless an SIMD variant is used, which is no longer cross-platform.
It's surprising to see MT recommended because the 13 years since its publication have seen the development of at least one algorithm (WELL512) that outperforms it in all aspects (for this particular application).


I recommend it because I had source to post him that just works, and I know from personal experience how hard that is to get sometimes. I don't have the newer algorithm implemented as the old one runs just fine for a particle system on a DS, and its not like it's crap in the first place. One quiet moment I might look at the WELL512 thing though, thanks for the tip.

Share this post


Link to post
Share on other sites
Promit    13246
Quote:
Original post by Jan Wassenberg
Mersenne Twister (MT) has a large state (as it must to reach the insanely long period of 2**19337) and isn't actually that fast unless an SIMD variant is used, which is no longer cross-platform.
It's surprising to see MT recommended because the 13 years since its publication have seen the development of at least one algorithm (WELL512) that outperforms it in all aspects (for this particular application).
But MT is quite good, and implementations are readily available in nearly any language under highly favorable license terms.

Share this post


Link to post
Share on other sites

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