Talk:Mersenne twister
From Wikipedia, the free encyclopedia
 |
To-do list for Mersenne twister: | edit · history · watch · refresh |
|---|---|---|
|
||
For the technically interested somebody should give a reference to the original publication.
- Done.
Contents |
[edit] equidistributed
What does "equidistributed in 623 dimensions" mean? AxelBoldt, Saturday, March 30, 2002
- Well... It means that if you take the outputs and use them to pick points in 623-dimensional space, you get a statistically uniform distribution in the unit hypercube (assuming you pick between 0 and 1). I would have thought that was obvious? If not, perhaps some parenthetical clarification is indicated?
-
- Perhaps better: that all sequences of bits of length up to 623 digits appear equally often in the output. Acanon 23:30, 1 Sep 2004 (UTC)
No. It is *not* merely "all sequences of up to 623 output *bits*". It's the much stronger "all sequences of up to 623 output *values*, where each value is 32 bits".
(In contrast, a 65 bit LFSR has equidistribed all sequences of only 2 output 32 bit values. The third 32 bit output value of that LFSR is heavily biased. The fourth value can always be predicted from the previous 3 with 100% accuracy.)
--DavidCary 8 July 2005 23:46 (UTC)
"twist" is for long period, "temper" is for equidistribution. but I can't say it well in English. 61.211.103.62 12:04, 5 February 2006 (UTC) M.Saito
[edit] description
Perhaps some person should include a description of the algorithm?
[edit] Changed seeding algorithm!
Was: MT[i] := last_32bits_of(69069 * MT[i-1])
Is now: MT[i] := last_32bits_of((69069 * MT[i-1]) + 1)
There are 2^19937 possible states for the MT19937 generator and only one of them is unacceptable - all zeros. The old LCG will itself produce an endless run of zeros if the seed is 0. Moreover, I believe it is a mangled version of a VAX generator. See [1]
[edit] Mistake in code?
Within the 'k' indexed 'for' loop the pseudocode uses 'i' instead of 'k'
Also 'index' / 'i' in the final function.
I've corrected both of these.
[edit] cryptography and the MT
i added a sentence about why the MT can't be used for cryptography — observing the sequence of iterates for long enough allows one to predict or independently calulate all future iterates. dunno if this is sufficient. Lunch 01:23, 16 March 2006 (UTC)
[edit] Seeding
The C implementation of MT takes a 32-bit value as a seed. Does anyone know how to choose seeds that will generate sequences that don't overlap (for, say, 2^64 values) in the 2^19937-1 long full sequence? Or one can be "reasonably sure" that all those 2^32 seeds generate disjuct sequences? Any results published on this? Andras 84.3.64.82 09:54, 12 April 2006 (UTC) Yes, there are positive results from Matsumoto & Nishimura themselves (see web site): Makoto Matsumoto and Takuji Nishimura, "Dynamic Creation of Pseudorandom Number Generators", Monte Carlo and Quasi-Monte Carlo Methods 1998, Springer, 2000, pp 56--69
[edit] The "twist" and equidistribution
The article says: "The "twist" is a transformation which assures equidistribution of the generated numbers in 623 dimensions (linear congruential generators can at best manage reasonable distribution in 5 dimensions)" I think this is probably wrong. The equidistribution in 623 dimensions is also attained by a linear congruential generator provided it is as big as Mersenne Twister, and that it is based on a primitive polynomial. In fact all the widely discussed good properties of Mersenne Twister are shared by a such a construction. There are a few good things the "twist" achieves but they are very subtle (perhaps too much so for an encyclopedia article). 203.164.223.124 02:49, 28 April 2006 (UTC)
[edit] Speed
The article says: "It is faster than all but the most statistically unsound generators." Not really. It is quite fast. It is difficult to make a generator this good that runs faster. But a lagged fibonacci generator with sufficiently large lags can run quite a lot faster, and has good enough properties for many purposes. A lagged fibonacci generator with 4 taps (instead of the usual 2) is likely at least as fast as MT and behaves quite well. The construction used in SPRNG with two lagged fibonnaci generators combined with right shift and XOR is also very fast and very good. None of these have the proveable nice properties of the twister, but in practice i would not call them "most statistically unsound".
BTW the free source code distributed by the original inventors of MT is kind of acceptibly quick, but could be a lot faster if optimised, especially for a particular machine. But even when optimised it will be a lot slower than lagged fibonacci. 203.164.223.124 02:49, 28 April 2006 (UTC)
[edit] equidistribution
The proveable equidistribution in 623 dimensions may be a red herring. It only applies totalled over the whole period of the generator. The period is so huge that it is unlikely to be used in any real application. It is actually possible to achieve the same guarantee for some really bad generators.
Here's one: take a unsigned binary number with 623*32 = 19936 bits. Initialise it to some value as the seed. Return successive 32 bit sections from the number as pseudo-random return values. When the end of the number is reached, increment the number and start back at the first 32 bit section. Over the whole period, this has equidistribution in 623 dimensions. Over any data set you would use in practice, it sucks.
Mersenne Twister seems to be very well behaved in practice, but this has very little to do with the theoretical guarantee. 203.164.223.124 02:49, 28 April 2006 (UTC)
[edit] Revision Update
There is a new revision (2002/1/26) by the original authors of MT. We need to update this article to reflect the changes: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c
- (Yes, please. The previous initialization, the one that the article mentions, had severe problems; see the explanation (Google's cache) and the new code (Google's cache). The function to revise is init_genrand().) --pgimeno 13:23, 2 January 2007 (UTC)
Also, we need more explanations about the code. I'm a little unclear of a particular for-loop used in this new revision:
k = (N>key_length ? N : key_length);
for (; k; k--) { ... }
What does this mean? k is initialised to either N or key_length, and used as the default for the empty parameter in the for-loop, but the second parameter is also k. From the code, it looks like as if he's decrementing k, but with the same initial and end conditions. The for-loop is the same as
for(k;k;k--) {...}
I don't make any sense of this. Can anyone explain? Thanks.
- It's equivalent to:
k = max(N, key_length);
while(k != 0) {
...
k--;
}
- --64.235.97.125 19:16, 16 October 2006 (UTC)
[edit] I don't undestand...
I'm somewhat puzzled by the "applications" paragraph. What does it mean that 624 observations allows one to predict the future iterates? Are there any known issues with some seeds? (Please try to be simple, I'm not really in those things)
MaxDZ8 talk 14:32, 26 October 2006 (UTC)
- Tempering function is bijective. So inverse function exists. So we can rebuild internal vectors from 624 outputs. Then we can run MT algorism to get next sequence.133.41.131.128 01:11, 14 March 2007 (UTC)
I believe I got it. Thank you.
MaxDZ8 talk 06:59, 14 March 2007 (UTC)
[edit] Pseudo code
MT generates 624 numbers at once, but it's for speed. Pseudo code should show algorithm clearly without considering speed. I don't know the grammer of pseudo code, so I show it in C:
unsigned long genrand_int32(void)
{
unsigned long y;
static unsigned long mag01[2]={0x0UL, MATRIX_A};
/* mag01[x] = x * MATRIX_A for x=0,1 */
mti = mti % N;
y = (mt[mti] & UPPER_MASK) | (mt[(mti + 1) % N] & LOWER_MASK);
mt[mti] = mt[(mti + M) % N] ^ (y >> 1) ^ mag01[y & 0x1UL];
y = mt[mti];
mti++;
/* Tempering */
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);
return y;
}
—The preceding unsigned comment was added by 133.41.131.128 (talk) 04:32, 27 March 2007 (UTC).
