Another Mersenne Twister question

[Simon]

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(19 650218UL);

to:

init_genrand(ti me());

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

[mark_bluemel@pobox.com]

Re: Another Mersenne Twister question


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 ?

[Arthur J. O'Dwyer]

Re: Another Mersenne Twister question


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(19 650218UL);
>
to:
>
init_genrand(ti me());
>
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((u nsigned 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((u nsigned 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.programmin g, or for extra flamage, sci.crypt. ;)

HTH,
-Arthur

[Simon]

Re: Another Mersenne Twister question


Arthur J. O'Dwyer wrote:

To be correct in your C, you should have written at least
>
#include <time.h>
>
init_genrand((u nsigned 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

[websnarf@gmail.com]

Re: Another Mersenne Twister question

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(19 650218UL);
>
to:
>
init_genrand(ti me());

Well you shouldn't modify the MT code itself. Instead you should
simply call init_genrand(ti me(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(ti me(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/

[Keith Thompson]

Re: Another Mersenne Twister question

"Arthur J. O'Dwyer" <ajonospam@andr ew.cmu.eduwrite s:

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(1 9650218UL);
>>
>to:
>>
>init_genrand(t ime());
>>
>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((u nsigned 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((u nsigned 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_Keit h) kst-u@mib.org <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.

[CBFalconer]

Re: Another Mersenne Twister question

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(19 650218UL);
>
to:
>
init_genrand(ti me());
>
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(NU LL));". 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>

[Keith Thompson]

Re: Another Mersenne Twister question

websnarf@gmail. com 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_Keit h) kst-u@mib.org <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]

Re: Another Mersenne Twister question

CBFalconer <cbfalconer@yah oo.comwrites:

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(1 9650218UL);
>>
>to:
>>
>init_genrand(t ime());
>>
>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(NU LL));". 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_Keit h) kst-u@mib.org <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.

[Jack Klein]

Re: Another Mersenne Twister question

On Wed, 25 Oct 2006 21:10:46 GMT, Keith Thompson <kst-u@mib.orgwrote
in comp.lang.c:

"Arthur J. O'Dwyer" <ajonospam@andr ew.cmu.eduwrite s:

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(19 650218UL);
>
to:
>
init_genrand(ti me());
>
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((u nsigned 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((u nsigned 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.l earn.c-c++

http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html

[fermineutron]

Re: Another Mersenne Twister question

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
cryptographical ly safe. Combining it with a hash box does yeild a
cryptographical ly safe PRND.

[Ben Pfaff]

Re: Another Mersenne Twister question

[sci.crypt added due to subject matter]

"fermineutr on" <free4trample@y ahoo.comwrites:

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
cryptographical ly safe. Combining it with a hash box does yeild a
cryptographical ly safe PRND.

Perhaps; I am not an expert. However, in my opinion it would be
better to use a PRNG designed to be cryptographical ly secure,
instead of a kluge.
--
"I don't have C&V for that handy, but I've got Dan Pop."
--E. Gibbons