Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Another Mersenne Twister question

Reply
Thread Tools

Another Mersenne Twister question

 
 
Simon
Guest
Posts: n/a
 
      10-25-2006
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

 
Reply With Quote
 
 
 
 
mark_bluemel@pobox.com
Guest
Posts: n/a
 
      10-25-2006

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 ?

 
Reply With Quote
 
 
 
 
Arthur J. O'Dwyer
Guest
Posts: n/a
 
      10-25-2006

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
 
Reply With Quote
 
Simon
Guest
Posts: n/a
 
      10-25-2006

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

 
Reply With Quote
 
websnarf@gmail.com
Guest
Posts: n/a
 
      10-25-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());


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/

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      10-25-2006
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>


 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      10-25-2006
"Arthur J. O'Dwyer" <(E-Mail Removed)> 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.velocityreviews.com/forums/(E-Mail Removed) <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.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      10-25-2006
(E-Mail Removed) 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) (E-Mail Removed) <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.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      10-25-2006
CBFalconer <(E-Mail Removed)> 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) (E-Mail Removed) <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.
 
Reply With Quote
 
Jack Klein
Guest
Posts: n/a
 
      10-26-2006
On Wed, 25 Oct 2006 21:10:46 GMT, Keith Thompson <(E-Mail Removed)> wrote
in comp.lang.c:

> "Arthur J. O'Dwyer" <(E-Mail Removed)> 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/~a...FAQ-acllc.html
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Toughest Brain Twister Question divya bisht C++ 1 11-14-2011 02:28 PM
Mac using Mersenne Twister in C g000we C Programming 3 03-05-2011 09:19 AM
Naive parallel implementation of Mersenne Twister random numbergenerator mjm2114@columbia.edu C Programming 0 06-04-2008 01:58 PM
Fast Mersenne Twister bearophileHUGS@lycos.com Python 0 05-15-2008 05:46 PM
Mersenne Twister -- A Revised C++ Implementation Scott Robert Ladd C++ 31 01-07-2004 04:45 PM



Advertisments