help me with weird random number thing!

[cliffski]

Ok, I'm no dork, I know to seed srand() with the system time on startup but.............

There is ONE random number that I generate in my game that is always the same. It's always 41.
In other words:

rand()

returns 41.

Its probably the 300th call to rand() or somesuch.
And yet if I make my game dump out all of its random numebrs to a log, they DO seem to be different and totally random...
Is this a debugger thing? Shurely no co-incidence!
I have only 1 call to srand() in the whole app. There is nothing magical about this specific call.
What could I be doign wrong, like a dork?

[Bad Sector]

Does the srand() get a different value each time though? Have you checked this possibility? How do you use the rand() and how the srand()?

[cliffski]

I do srand(timeGetTime()) and I check what timeGetTime() was. get this:

first attempt:
timeGeTime() 310713421
first rand() 11654
second rand() 41

secondattempt:
timeGeTime() 310766985
first rand() 1353
second rand() 41

etc..
I may reboot... and do a total rebuild.

[zoombapup]

Hmm, just 1 away from the answer to life the universe and everything. I'd say thats usually a good thing

Try using a proper random number generator? rand() isnt.

[cliffski]

rand() should not be predictable. if I call it twice, having seeded it with the system time, it should return different numbers.
And even if it doesnt, it shouldnt magically pick a single call to rand() to return the same number.

[cliffski]

OMG it's this:

http://bytes.com/topic/c/answers/516...osoft-compiler

Apparently becuase I'm in a different thread, I need to re seed rand for that thread.

you learn something new every day...

[Game Producer]

I betcha you are doing seeding srand() with something between those first and second rand() calls.

Have you done an a piece of software that does exactly that and only that - or are you taking this code from your software code.

Is there other ways to seed the random thing besides srand()?

[Game Producer]

And if it's not that, then perhaps it's the germany-england soccer result that keeps haunting you

[Game Producer]

Ah, we wrote simultaneously. Was just about to mention "other thread"...

Oh well, nice that it got sorted out.

[oNyx]

I highly recommend to use a different PRNG. That way you can get deterministic results with different compilers, different operating systems, and even entirely different languages. Additionally, it's entirely up to you how sophisticated the PRNG is.

Nowadays I recommend XorShift. It's a surprisingly simple looking algorithm with excellent characteristics. It passes the Diehard tests (i.e. it got good statistical properties) and it's also very fast - at least in all languages where binary operators work directly with proper integers (C/C++, Java, AS3, etc.).

JavaScript for example only got IEEE 754 floating point (aka double) and nothing else. If you use a binary operator, the value(s) get(s) converted to int first, then the operation is performed, and finally it's converted back again. This does, of course, affect performance a bit. I still do use XorShift over there though (I use it everywhere). I don't really need thousands of random numbers per second. I'm fine without that 3-4x speed boost.

[Vino]

Here's my handy and reliable mersenne twister c implementation for you:

#define MT_SIZE 624
static size_t g_aiMT[MT_SIZE];
static size_t g_iMTI = 0;

// Mersenne Twister implementation from Wikipedia.
void mtsrand(size_t iSeed)
{
	g_aiMT[0] = iSeed;
	for (size_t i = 1; i < MT_SIZE; i++)
	{
		size_t inner1 = g_aiMT[i-1];
		size_t inner2 = (g_aiMT[i-1]>>30);
		size_t inner = inner1 ^ inner2;
		g_aiMT[i] = (0x6c078965 * inner) + i;
	}

	g_iMTI = 0;
}

size_t mtrand()
{
	if (g_iMTI == 0)
	{
		for (size_t i = 0; i < MT_SIZE; i++)
		{
			size_t y = (0x80000000&(g_aiMT[i])) + (0x7fffffff&(g_aiMT[(i+1) % MT_SIZE]));
			g_aiMT[i] = g_aiMT[(i + 397)%MT_SIZE] ^ (y>>1);
			if ((y%2) == 1)
				g_aiMT[i] = g_aiMT[i] ^ 0x9908b0df;
		}
	}

	size_t y = g_aiMT[g_iMTI];
	y = y ^ (y >> 11);
	y = y ^ ((y << 7) & (0x9d2c5680));
	y = y ^ ((y << 15) & (0xefc60000));
	y = y ^ (y >> 18);

	g_iMTI = (g_iMTI + 1) % MT_SIZE;

	return y;
}

I don't know if you code in C or C++ but if you do, you're welcome. It's deterministic on every platform I've used it on so far. I keep it handy in a common library that I import into all my projects.

[oNyx]

Ye, the Mersenne Twister is also a good choice. Even if it fell a bit out of favor these days, since it's rather complicated to implement. Other PRNGs like Multiply-with-carry or WELL512 are simpler, are equally good or better at generating random numbers, and they are also faster.

XorShift on the other hand is somewhat low tech in comparison, having a period of "only" 2^128-1. Well, for games it's good enough in my opinion. rand() typically only has a period of 2^31 or 2^32 for example and it generally doesn't pass Diehard or similar tests.

[Pogacha]

Depending on what I was using MT or rand(), but that XorShift looks great
far simplier and faster than MT, less memory footprint too.
Thanks for sharing.

[Mattias Gustavsson]

Here's the implementation of WELL512 that I'm using in my Pixie game engine
Header file:

/**
 * \class	Random
 * 
 * \ingroup	core
 * \brief	
 * \author	Mattias Gustavsson	
 * 
 * Random number generation, using the WELL algorithm by F. Panneton, P. L'Ecuyer and M. Matsumoto.
 * The creators of the algorithm describes it like this:
 *
 *      Fast uniform random number generators with extremely long periods have been defined and implemented based on 
 *      linear recurrences modulo 2. The twisted GFSR and the Mersenne twister are famous recent examples. Besides the 
 *      period length, the statistical quality of these generators is usually assessed via their equidistribution 
 *      properties. The huge-period generators proposed so far are not quite optimal in that respect. In this paper, 
 *      we propose new generators, with better equidistribution and "bit-mixing" properties for equivalent period length 
 *      and speed. Approximately half of the coefficients of the characteristic polynomial of these generators are 
 *      nonzero. The state of our new generators evolves in a more chaotic way than for the Mersenne twister. We 
 *      illustrate how this can reduce the impact of persistent dependencies among successive output values, which can 
 *      be observed in certain parts of the period of gigantic generators such as the Mersenne twister.
 *
 * More information in the original paper: http://www.iro.umontreal.ca/~panneton/WELLRNG.html
 *
 * This code is originally based on WELL512 C/C++ code written by Chris Lomont (published in Game Programming Gems 7) 
 * and placed in the public domain. There's also an article about it on Lomont's site:
 *
 *      http://lomont.org/Math/Papers/2008/Lomont_PRNG_2008.pdf
 */

#ifndef __Random_H__
#define __Random_H__

class Random
    {
    public:
        Random();

        void Seed(unsigned int seed);
        void SetState(const unsigned int state[16], int index);
        void GetState(unsigned int state[16], int& index);

        /** 
         * Generates a random number on [0,0xffffffff] interval
         */
        unsigned int RandomInteger();

        /**
         * Generates a random number on [0,0.99999999999...] interval
         */
        float RandomFloat();

        /**
         * Generates a random number on [min,max] interval
         */
        int RandomRanged(int min, int max);

    private:
        unsigned int state_[16];
        unsigned int index_;

    };

#endif /* __Random_H__ */

Cpp file:

//*** Random.cpp ***


#include "Random.h"

//*** Constructor ***

Random::Random():
    index_(0)
    {
    Seed(0x5ee39c34);
    }


//*** Seed ***

void Random::Seed(unsigned int s)
    {	
    state_[0]=s^0xf68a9fc1;
    for (int i=1; i<16; i++) 
        {
        state_[i] = (0x6c078965U * (state_[i-1] ^ (state_[i-1] >> 30)) + i); 
        }
    }


//*** SetState ***

void Random::SetState(const unsigned int state[16], int index)
    {
    for (int i=0; i<16; i++)
        {
        state_[i]=state[i];
        }

    index_=index&15;
    }


//*** GetState ***

void Random::GetState(unsigned int state[16], int& index)
    {
    for (int i=0; i<16; i++)
        {
        state[i]=state_[i];
        }

    index=index_;
    }


//*** RandomInteger ***

unsigned int Random::RandomInteger()
    {
    unsigned int a = state_[index_];
    unsigned int c = state_[(index_+13)&15];
    unsigned int b = a^c^(a<<16)^(c<<15);
    c = state_[(index_+9)&15];
    c ^= (c>>11);
    a = state_[index_] = b^c;
    unsigned int d = a^((a<<5)&0xda442d20U);
    index_ = (index_ + 15)&15;
    a = state_[index_];
    state_[index_] = a^b^d^(a<<2)^(b<<18)^(c<<28);
    return state_[index_];
    }


//*** RandomRanged ***

int Random::RandomRanged(int min, int max)
    {
    int range=(max-min)+1;
    if (range<=0)
        {
        return min;
        }
    int value=(int)(RandomFloat()*range);
    return min+value; 
    }


//*** RandomFloat ***

float Random::RandomFloat()
    {
    // Get a random integer, and divide by 2^32
    return (RandomInteger()/4294967296.0f);     
    }

[oNyx]

Thanks for sharing, Matt.

I haven't seen the Whitesmiths indent style since ages. Pretty nostalgic, really. It's the style I started with. I then switched to Allman (the braces' content is indented - it worked better in most editors) and finally to 1TBS (hugging braces - industry standard with Java, mandatory with JavaScript).


By the way, that "[0,0xffffffff]-interval" comment... the hyphen shouldn't be there.

[Mattias Gustavsson]

I haven't seen the Whitesmiths indent style since ages.

Yeah, it's not the most common one - I used to use Allman for years, but switched over to Whitesmiths some 7 years ago, and have stuck with it for my personal projects ever since, while still using Allman at most of the places I've worked. I do think that once I got used to Whitesmiths, it is the one which suits me better - I just think it's easier to see the code structure

Well spotted on the hyphen *removed*