Another Mersenne Twister question

Discussion in 'C Programming' started by Simon, Oct 25, 2006.

  1. Simon

    Simon Guest

    I have a quick question on the Mersenne Twister (hereinafter MT)

    I'm using the standard C code downloaded from the MT website
    (http://tinyurl.com/6d8t3). It's being used for a game to generate
    random levels, monsters, items and so on, and I want the game to be
    different each time I play it.

    The standard MT code gives me the same string of random numbers each
    time I run it. This is not surprising - computers are deterministic
    and it always starts with the same seed. The obvious way to get around
    this is to seed the MT with the current time each time the game is run.
    Although I appear to have achieved this I'm concerned that I've done
    it in a stupid / wrong way.

    I've made only one change to the code. In the init_by_array function
    I've changed line 79 from:

    init_genrand(19650218UL);

    to:

    init_genrand(time());

    As I say, this seems to work fine - whenever I start up the program and
    initialise the MT I get a different string of random numbers. However,
    it would be great if someone who is familiar with MT could let me know
    whether this is a horrific hatchet job or not.

    Simon
    Simon, Oct 25, 2006
    #1
    1. Advertising

  2. Simon

    Guest

    Simon wrote:

    > I have a quick question on the Mersenne Twister (hereinafter MT)

    [Snip]

    Have you looked at the FAQ - for example
    http://c-faq.com/lib/srand.html ?
    , Oct 25, 2006
    #2
    1. Advertising

  3. On Wed, 25 Oct 2006, Simon wrote:
    >
    > I have a quick question on the Mersenne Twister (hereinafter MT)
    >
    > I'm using the standard C code downloaded from the MT website
    > (http://tinyurl.com/6d8t3). It's being used for a game to generate
    > random levels, monsters, items and so on, and I want the game to be
    > different each time I play it.
    >
    > The standard MT code gives me the same string of random numbers each
    > time I run it. This is not surprising - computers are deterministic
    > and it always starts with the same seed. The obvious way to get around
    > this is to seed the MT with the current time each time the game is run.
    > Although I appear to have achieved this I'm concerned that I've done
    > it in a stupid / wrong way.
    >
    > I've made only one change to the code. In the init_by_array function
    > I've changed line 79 from:
    >
    > init_genrand(19650218UL);
    >
    > to:
    >
    > init_genrand(time());
    >
    > As I say, this seems to work fine - whenever I start up the program and
    > initialise the MT I get a different string of random numbers. However,
    > it would be great if someone who is familiar with MT could let me know
    > whether this is a horrific hatchet job or not.


    To be correct in your C, you should have written at least

    #include <time.h>

    init_genrand((unsigned long)time(NULL));

    and probably

    #include <time.h>

    time_t tval = time(NULL);
    if (tval == (time_t)-1) {
    /* This system doesn't support time(), or there was an error */
    tval = some_other_seed;
    }
    init_genrand((unsigned long)tval);

    As for whether this is "random enough" --- yes, certainly it's
    random enough for a PC game. Certainly it's not random enough for
    crypto or an online poker game. But you won't be able to tell the
    difference between this and pure randomness anyway.

    For that matter, you won't be able to tell the difference between
    this and just using plain old rand(), provided by your standard library.
    But if you want to use MT, I see no reason to stop you. :)

    If you have questions about randomness that aren't C-specific,
    please see comp.programming, or for extra flamage, sci.crypt. ;)

    HTH,
    -Arthur
    Arthur J. O'Dwyer, Oct 25, 2006
    #3
  4. Simon

    Simon Guest

    Arthur J. O'Dwyer wrote:
    > To be correct in your C, you should have written at least
    >
    > #include <time.h>
    >
    > init_genrand((unsigned long)time(NULL));


    Yes, there are of course included. It was the methodology I was
    worried about - It took me a week or so to figure out what MT was doing
    and I wanted to make sure I hadn't missed anything!

    >
    > HTH,
    > -Arthur


    Thanks a lot

    Simon
    Simon, Oct 25, 2006
    #4
  5. Simon

    Guest

    Simon wrote:
    > I have a quick question on the Mersenne Twister (hereinafter MT)
    >
    > I'm using the standard C code downloaded from the MT website
    > (http://tinyurl.com/6d8t3). It's being used for a game to generate
    > random levels, monsters, items and so on, and I want the game to be
    > different each time I play it.
    >
    > The standard MT code gives me the same string of random numbers each
    > time I run it. This is not surprising - computers are deterministic
    > and it always starts with the same seed. The obvious way to get around
    > this is to seed the MT with the current time each time the game is run.
    > Although I appear to have achieved this I'm concerned that I've done
    > it in a stupid / wrong way.
    >
    > I've made only one change to the code. In the init_by_array function
    > I've changed line 79 from:
    >
    > init_genrand(19650218UL);
    >
    > to:
    >
    > init_genrand(time());


    Well you shouldn't modify the MT code itself. Instead you should
    simply call init_genrand(time(NULL)) at the start of your program and
    avoid calling init_by_array() unless you have a source of real entropy
    in an array somewhere.

    > As I say, this seems to work fine - whenever I start up the program and
    > initialise the MT I get a different string of random numbers. However,
    > it would be great if someone who is familiar with MT could let me know
    > whether this is a horrific hatchet job or not.


    It is. :) Just restrict yourself to calling init_genrand(time(NULL))
    at the start of your program as I described above. That way you will
    be able to use the MT source in its pristene form for other projects
    and still have it synchronize with what other people expect from it.

    There are more issues with using time(NULL) as a source of entropy.
    The most obvious being that you can only start your program once per
    second any guarantee that the sequence is different from the last time.
    This usually doesn't matter, but you could see how in a distributed
    system, this might be an issue (lots of machines running in parallel,
    hoping to run a different instance of a simulation -- they would not be
    different at all if they all started at the same time). You can find
    other sources of entropy in your system (such as the value of clock()
    after performing some IO, the PID, or in fact just an incrementing
    counter that you read and update in a file) and add that to an array of
    entropy sources (and you can include time(NULL)). Then you can use
    init_by_array() to initialize MT using all those entropy sources to
    reduce the probability that the sequence is the same.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
    , Oct 25, 2006
    #5
  6. Simon

    CBFalconer Guest

    Simon wrote:
    >
    > I have a quick question on the Mersenne Twister (hereinafter MT)
    >

    .... snip ...
    >
    > I've made only one change to the code. In the init_by_array
    > function I've changed line 79 from:
    >
    > init_genrand(19650218UL);
    >
    > to:
    >
    > init_genrand(time());
    >
    > As I say, this seems to work fine - whenever I start up the
    > program and initialise the MT I get a different string of random
    > numbers. However, it would be great if someone who is familiar
    > with MT could let me know whether this is a horrific hatchet job
    > or not.


    In the Mersenne Twister I use the seed call is to seedMT(unsigned
    long) and I use it as "seedMT(time(NULL));". However see the N869
    quote for the time function below. By failing to supply the proper
    argument you are letting time write its result into unknown memory
    areas, with totally undefined results.

    7.23.2.4 The time function

    Synopsis

    [#1]
    #include <time.h>
    time_t time(time_t *timer);

    Description

    [#2] The time function determines the current calendar time.
    The encoding of the value is unspecified.

    Returns

    [#3] The time function returns the implementation's best
    approximation to the current calendar time. The value
    (time_t)-1 is returned if the calendar time is not
    available. If timer is not a null pointer, the return value
    is also assigned to the object it points to. *

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>
    CBFalconer, Oct 25, 2006
    #6
  7. "Arthur J. O'Dwyer" <> writes:
    > On Wed, 25 Oct 2006, Simon wrote:

    [...]
    >> I've made only one change to the code. In the init_by_array function
    >> I've changed line 79 from:
    >>
    >> init_genrand(19650218UL);
    >>
    >> to:
    >>
    >> init_genrand(time());
    >>
    >> As I say, this seems to work fine - whenever I start up the program and
    >> initialise the MT I get a different string of random numbers. However,
    >> it would be great if someone who is familiar with MT could let me know
    >> whether this is a horrific hatchet job or not.

    >
    > To be correct in your C, you should have written at least
    >
    > #include <time.h>
    >
    > init_genrand((unsigned long)time(NULL));
    >
    > and probably
    >
    > #include <time.h>
    >
    > time_t tval = time(NULL);
    > if (tval == (time_t)-1) {
    > /* This system doesn't support time(), or there was an error */
    > tval = some_other_seed;
    > }
    > init_genrand((unsigned long)tval);


    The cast (like most casts) is not necessary. As long as there's a
    prototype in scope for init_genrand(), the result of time() or the
    value of tval will be implicitly converted to the required type.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Oct 25, 2006
    #7
  8. writes:
    [...]
    > There are more issues with using time(NULL) as a source of entropy.
    > The most obvious being that you can only start your program once per
    > second any guarantee that the sequence is different from the last time.

    [...]

    Actually, the C standard doesn't even guarantee that much. time_t is
    an arithmetic type capable of representing times; the standard says
    nothing about its resolution, or about *how* it represents times.

    Conceivably an implementation could make time_t a typedef for some
    floating-point type, and time() could always return a result in the
    interval [0.0, 1.0). In this case, converting the result of time()
    to an integer type would *always* yield 0.

    Realistically, you're not likely to encounter this. On every system
    I've ever seen, time_t is an integer type with a resolution of 1
    second.

    Some systems have a built-in source of random data. You might
    consider using that if it's available, and falling back to something
    like time() if it isn't.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Oct 25, 2006
    #8
  9. CBFalconer <> writes:
    > Simon wrote:
    >> I have a quick question on the Mersenne Twister (hereinafter MT)
    >>

    > ... snip ...
    >>
    >> I've made only one change to the code. In the init_by_array
    >> function I've changed line 79 from:
    >>
    >> init_genrand(19650218UL);
    >>
    >> to:
    >>
    >> init_genrand(time());
    >>
    >> As I say, this seems to work fine - whenever I start up the
    >> program and initialise the MT I get a different string of random
    >> numbers. However, it would be great if someone who is familiar
    >> with MT could let me know whether this is a horrific hatchet job
    >> or not.

    >
    > In the Mersenne Twister I use the seed call is to seedMT(unsigned
    > long) and I use it as "seedMT(time(NULL));". However see the N869
    > quote for the time function below. By failing to supply the proper
    > argument you are letting time write its result into unknown memory
    > areas, with totally undefined results.

    [snip]

    If you call time() with no arguments *and the compiler lets you get
    away with it*, it probably means that you've forgotten the mandatory
    "#include <time.h>". You've invoked undefined behavior before the
    time() function itself even tries to write its result anywhere.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Oct 25, 2006
    #9
  10. Simon

    Jack Klein Guest

    On Wed, 25 Oct 2006 21:10:46 GMT, Keith Thompson <> wrote
    in comp.lang.c:

    > "Arthur J. O'Dwyer" <> writes:
    > > On Wed, 25 Oct 2006, Simon wrote:

    > [...]
    > >> I've made only one change to the code. In the init_by_array function
    > >> I've changed line 79 from:
    > >>
    > >> init_genrand(19650218UL);
    > >>
    > >> to:
    > >>
    > >> init_genrand(time());
    > >>
    > >> As I say, this seems to work fine - whenever I start up the program and
    > >> initialise the MT I get a different string of random numbers. However,
    > >> it would be great if someone who is familiar with MT could let me know
    > >> whether this is a horrific hatchet job or not.

    > >
    > > To be correct in your C, you should have written at least
    > >
    > > #include <time.h>
    > >
    > > init_genrand((unsigned long)time(NULL));
    > >
    > > and probably
    > >
    > > #include <time.h>
    > >
    > > time_t tval = time(NULL);
    > > if (tval == (time_t)-1) {
    > > /* This system doesn't support time(), or there was an error */
    > > tval = some_other_seed;
    > > }
    > > init_genrand((unsigned long)tval);

    >
    > The cast (like most casts) is not necessary. As long as there's a
    > prototype in scope for init_genrand(), the result of time() or the
    > value of tval will be implicitly converted to the required type.


    Yes, and if time_t on the OP's platform happens to be any integer
    type, even one of higher rank than unsigned long, the result is
    well-defined. On the other hand, if time_t is a floating point type,
    and the value returned is negative or greater than ULONG_MAX, the
    behavior is undefined with or without the cast. So the cast is still
    useless.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://c-faq.com/
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
    Jack Klein, Oct 26, 2006
    #10
  11. Simon

    fermineutron Guest

    You should also keep in mind for your future products that no matter
    how sifisticated your initialization of MT is, MT by design is not
    cryptographically safe. Combining it with a hash box does yeild a
    cryptographically safe PRND.
    fermineutron, Oct 26, 2006
    #11
  12. Simon

    Ben Pfaff Guest

    [sci.crypt added due to subject matter]

    "fermineutron" <> writes:

    > You should also keep in mind for your future products that no matter
    > how sifisticated your initialization of MT is, MT by design is not
    > cryptographically safe. Combining it with a hash box does yeild a
    > cryptographically safe PRND.


    Perhaps; I am not an expert. However, in my opinion it would be
    better to use a PRNG designed to be cryptographically secure,
    instead of a kluge.
    --
    "I don't have C&V for that handy, but I've got Dan Pop."
    --E. Gibbons
    Ben Pfaff, Oct 26, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Scott Robert Ladd
    Replies:
    31
    Views:
    6,357
    Carsten Hansen
    Jan 7, 2004
  2. Fast Mersenne Twister

    , May 15, 2008, in forum: Python
    Replies:
    0
    Views:
    363
  3. Replies:
    0
    Views:
    477
  4. g000we

    Mac using Mersenne Twister in C

    g000we, Mar 5, 2011, in forum: C Programming
    Replies:
    3
    Views:
    556
    g000we
    Mar 5, 2011
  5. divya bisht

    Toughest Brain Twister Question

    divya bisht, Nov 14, 2011, in forum: C++
    Replies:
    1
    Views:
    252
    Tomasz Budzeń
    Nov 14, 2011
Loading...

Share This Page