Results 1 to 16 of 16

Thread: help me with weird random number thing!

  1. #1
    Moderator
    Join Date
    Jul 2004
    Posts
    3,898

    Question help me with weird random number thing!

    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?

  2. #2
    Senior Member
    Join Date
    May 2005
    Location
    Warsaw, Poland
    Posts
    2,733

    Default

    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()?

  3. #3
    Moderator
    Join Date
    Jul 2004
    Posts
    3,898

    Default

    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.

  4. #4
    Moderator
    Join Date
    Nov 2004
    Posts
    2,896

    Default

    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.
    www.mindflock.com - social AI-based games

  5. #5
    Moderator
    Join Date
    Jul 2004
    Posts
    3,898

    Default

    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.

  6. #6
    Moderator
    Join Date
    Jul 2004
    Posts
    3,898

    Default

    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...

  7. #7
    Moderator
    Join Date
    Jan 2006
    Location
    Finland
    Posts
    1,422

    Default

    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()?

  8. #8
    Moderator
    Join Date
    Jan 2006
    Location
    Finland
    Posts
    1,422

    Default

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

  9. #9
    Moderator
    Join Date
    Jan 2006
    Location
    Finland
    Posts
    1,422

    Default

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

    Oh well, nice that it got sorted out.

  10. #10
    Senior Member
    Join Date
    Jul 2004
    Posts
    1,214

    Default

    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.

  11. #11
    Senior Member
    Join Date
    May 2010
    Posts
    345

    Default

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

    Code:
    #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.
    Jorge "Vino" Rodriguez
    Digitanks | SMAK

  12. #12
    Senior Member
    Join Date
    Jul 2004
    Posts
    1,214

    Default

    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.

  13. #13
    Senior Member
    Join Date
    Jan 2005
    Location
    Argentina
    Posts
    605

    Default

    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.

  14. #14
    Senior Member
    Join Date
    Aug 2005
    Location
    Royal Leamington Spa, UK
    Posts
    660

    Default

    Here's the implementation of WELL512 that I'm using in my Pixie game engine
    Header file:
    Code:
    /**
     * \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:
    Code:
    //*** 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);     
        }
    Last edited by Mattias Gustavsson; 06-30-2010 at 03:50 AM.
    "The Strangler" - My recent point-and-click adventure
    www.mattiasgustavsson.com - My blog on games and game development
    www.pixieuniversity.com - My Software 2D Game Engine

  15. #15
    Senior Member
    Join Date
    Jul 2004
    Posts
    1,214

    Default

    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.

  16. #16
    Senior Member
    Join Date
    Aug 2005
    Location
    Royal Leamington Spa, UK
    Posts
    660

    Default

    Quote Originally Posted by oNyx View Post
    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*
    "The Strangler" - My recent point-and-click adventure
    www.mattiasgustavsson.com - My blog on games and game development
    www.pixieuniversity.com - My Software 2D Game Engine

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •