This is the mail archive of the
gsl-discuss@sources.redhat.com
mailing list for the GSL project.
Mersenne Twister (Bug?)
- To: <gsl-discuss at sourceware dot cygnus dot com>
- Subject: Mersenne Twister (Bug?)
- From: "Franz Eder" <franz at eder-home dot de>
- Date: Fri, 28 Jul 2000 18:35:54 +0200
Hi!
The Mersenne Twister (mt.c, V. 0.6) delivers very strange results for
seed = 1 << 31 = pow(2,31) ...
I don't know if that is a bug but it seems so to me ...
Here is why:
a = 69069
e = 32
p = 2
m = pow(p, e) = pow(2, 32)
We have gcd(a, m) = 1.
X[0] = seed
X[n+1] = a*X[n] % m
is equivalent to
X[n] = pow(a, n) * X[0]
For X[0] = 0 we have X[n] = 0 for all n >= 0; this case is excluded in your
program.
There exists 0 <= f < e=32 with pow(2,f) = gcd(pow(2,e),X[0])
The period L of the generator does not exceed phi(pow(2,e))=2,147,483,648.
L equals the order of a=69069 modulo pow(p,e-f)=pow(2,32-f)
f L
0 1073741824
1 536870912
2 268435456
3 134217728
4 67108864
5 33554432
6 16777216
7 8388608
8 4194304
9 2097152
10 1048576
11 524288
12 262144
13 131072
14 65536
15 32768
16 16384
17 8192
18 4096
19 2048
20 1024
21 512
22 256
23 128
24 64
25 32
26 16
27 8
28 4
29 2
30 1
31 1
Solution: Allow only odd values for seed ...
Then we have L = 1,073,741,824 = phi(pow(2,32)) / 2
and that is quite good.
Taken from
KNUTH volume 2, 2nd edition 1981, p. 18-29
Yours,
Franz Eder
e-mail: franz@eder-home.de