Using C++ rand() isn't as bad as previously thought?

Discussion in 'Game Development (Technical)' started by GBGames, Dec 24, 2006.

  1. GBGames

    GBGames
    Expand Collapse
    Indie Author

    Joined:
    Jul 27, 2004
    Messages:
    1,254
    Likes Received:
    0
    I was recently looking for the "right" way to use rand() since I had read about problems with using it incorrectly. The problem has to do with the lower order bits causing more repetition than expected, which ruins the randomness you could have. Uhfgood pointed me to the following article which seems to explain away the myths and gives a good solution to use: http://eternallyconfuzzled.com/articles/rand.html

    Well, I decided to test it for myself, and it turns out that the article seems to make claims that didn't pan out in my tests. Then again, maybe my tests weren't very accurate or didn't prove what I thought they did. The source code to my test is available, and I would appreciate it if someone else could verify the results for themselves.

    http://gbgames.com/blog/?p=538
     
  2. Tertsi

    Tertsi
    Expand Collapse
    Indie Author

    Joined:
    Nov 4, 2004
    Messages:
    502
    Likes Received:
    0
    Just use Mersenne Twister and be done with it.
     
  3. Garthy

    Garthy
    Expand Collapse
    Indie Author

    Joined:
    Dec 5, 2006
    Messages:
    81
    Likes Received:
    0
    rand() is a perfectly usable low-quality random number generator. You do need to be aware the issues with the low-order bits, but these are easily prevented by taking high-order bits when you have the choice anyway. For example:

    int foo = (rand() >> 8) & 65535;

    Will give you a decent random number from 0 to 65535.

    Saying the problems with rand() are myths is a bit like saying that the warning to hold a knife by the handle rather than the blade is a myth. It's no myth, but like many tools, there are caveats to their use. You hold a knife by the handle, and you hold rand() by the high bits. ;) Also be aware that these problems are only present on some systems. Modern Linux distributions, for example, just call random() rather than rand(), which doesn't share the same problems.

    As Tertsi says, consider using a Mersenne Twister. They produce high-quality results at a fairly decent speed. It's actually hard to find a drawback. There's plenty of prewritten source out there. If you need ultra-fast psuedorandom number generation- and you'll know for sure if you do- chances are you're going to have to roll your own custom solution anyway.

    ... and Merry Christmas everyone. ;)
     
  4. soniCron

    soniCron
    Expand Collapse
    Indie Author

    Joined:
    May 4, 2005
    Messages:
    3,664
    Likes Received:
    0
  5. Michael Flad

    Michael Flad
    Expand Collapse
    Indie Author

    Joined:
    Aug 4, 2004
    Messages:
    190
    Likes Received:
    0
    Just a sidenote - rand() returns a value within the range of 0-RAND_MAX which is usually/often 0x7FFF (don't know if it's defined by the standard or just an implementation detail). So just be prepared for a limited range of numbers.
     
  6. Spaceman Spiff

    Spaceman Spiff
    Expand Collapse
    Original Member

    Joined:
    Apr 3, 2005
    Messages:
    137
    Likes Received:
    0
    Another reason to roll your own rand() function is predictability across platforms. If you use the standard C library function, it could change with platform or compiler version (though not likely).

    Also, there are some reasons to wrap up your own random number generator in a class. By making separate random number objects for the game simulation vs. other parts of the game, you can support a synchronous multiplayer game model where the same simulation runs in sync on all machines. Not to mention it makes record/replay functionality much easier.
     
  7. Garthy

    Garthy
    Expand Collapse
    Indie Author

    Joined:
    Dec 5, 2006
    Messages:
    81
    Likes Received:
    0
    Yikes! I wasn't aware some implementations had limits so low. On the two Linux boxes I have on hand the limit is much higher (0x7FFFFFFF), but the thought of systems potentially being limited to 0x7FFF (32767 ie. only 15 bits!) is terrifying. Anyone know what various Windows systems are limited to? And idea which systems are limited to 0x7FFF?

    Personally, I just put together a class using a Mersenne Twister early on since I needed the predictability and the ability to have multiple separate streams of reproducible random numbers. If I use rand()- and I'm pretty sure I don't- it's only when I honestly don't care about the randomness at all.
     
    #7 Garthy, Dec 25, 2006
    Last edited: Dec 25, 2006
  8. Garthy

    Garthy
    Expand Collapse
    Indie Author

    Joined:
    Dec 5, 2006
    Messages:
    81
    Likes Received:
    0
    Maybe something like this would help for those who really don't want to use anything but rand(). It should cope with limits as low as 0x7FFF.

    Code:
    int rand2()
    {
      return ((rand() >> 7)&255)
           | (((rand() >> 7)&255) << 8)
           | (((rand() >> 7)&255) << 16)
           | (((rand() >> 7)&255) << 24);
    }
    This way you can pull out high-order bits even with a low RAND_MAX. Warning: Completely untested.

    Again, I'd rather just use a Mersenne Twister. Far less pain. ;)
     
  9. voxel

    voxel
    Expand Collapse
    New Member

    Joined:
    Oct 29, 2006
    Messages:
    176
    Likes Received:
    0
    I support this fully. You almost NEED to write your own rand() because you want deterministic code for the exact reasons you've mention -different platforms, different number generators, synchronization, etc.

    BTW using a random seed is a bad, bad, bad practice in games except for coverage testing.
     
  10. PsySal

    PsySal
    Expand Collapse
    Original Member

    Joined:
    Apr 4, 2006
    Messages:
    63
    Likes Received:
    0
    I have had problems with rand(), too. I think my problems stemmed from not ever in a million years imagining that RAND_MAX could be so small on some implementations.

    Use MT. It's easy to imagine that rand() is implemented very differently in different situations, which itself makes it kind of useless, e.g. say you are randomly generating levels based on some input seed. With rand() you can probably expect different levels on different platforms, which might not be what you want.
     
  11. Sectarian

    Sectarian
    Expand Collapse
    New Member

    Joined:
    Dec 1, 2006
    Messages:
    67
    Likes Received:
    0

    Hi everyone. I am designing a broswer based game rightnow and am using C++ for the platform.

    I've been reading Archives yesterday here and this one as well. My question is should I use something different than C++ for the platform or continue to
    use C++ ?

    Because so far I have'nt experienced any problems yet?

    I appreciate your help/inputs. :)
     
  12. Donavon Keithley

    Donavon Keithley
    Expand Collapse
    Original Member

    Joined:
    Aug 5, 2004
    Messages:
    110
    Likes Received:
    0
    Take a look at Boost's random library. It offers a variety of RNG algorithms and utilities for shaping the distribution.
     
  13. CJPinder

    CJPinder
    Expand Collapse
    New Member

    Joined:
    Jan 18, 2007
    Messages:
    7
    Likes Received:
    0
    Random Number Generation

    I completely agree with Spaceman Spiff. From my own experience it is always best to use you own random number generator rather than rely on the one that comes with the compiler. It can be tricky to write your own one though and you have to be very careful so as to not create a broken generator. I've recently written an article about random number generation for games programmers that describes one of the most well tested generators and includes source in C and BASIC. I hope it will be useful to you:
    http://www.newkind.co.uk/articles/game-programming/random-numbers.php

    TTFN
    Christian.
     

Share This Page