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

 

[mark_bluemel]

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]

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

 

[Simon]

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

 

[websnarf]

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.

 

[CBFalconer]

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

 

[Keith Thompson]

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]

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]

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.

 

[Jack Klein]

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.

 

[fermineutron]

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.

 

[Ben Pfaff]

[sci.crypt added due to subject matter]

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.