1 #ifdef HAVE_CONFIG_H
2 # include <config.h>
3 #endif
4 #include "game.hh"
5 #include <cstdio>
6 #include <cstdlib>
7
8 #define M 1000000000
9 #define M_inv 1.0E-9
10 #define L 24
11 #define K 55
12 #define D 21
13
14 /*
15 Random number generator.
16 Uses the subtractive series
17
18 X[n] = (X[n-55] - X[n-24]) mod M, n >= 55
19
20 as suggested in Seminumerical Algorithms, exercise 3.2.2--23.
21 Knuth gives a FORTRAN implementation in section 3.6 for use as a
22 portable random number generator.
23
24 Michael Coffin
25 */
26
27 /*
28 The constant M is machine dependent. It must be even, and
29 integer arithmetic on the range [-M,+M] must be possible. The
30 function random() returns values in the half-open interval [0,M).
31
32 Minv is just 1/M.
33
34 Other possible values for L and K can be chosen from Table 1 of
35 Section 3.2.2. The constant D should be relatively prime to K and
36 approximately 0.382*K. (Don't ask me why.)
37
38 To get a random number in the real interval [X,Y) the recommended
39 formula is (X + (frandom() * (Y-X))). For an integral interval,
40 take the floor.
41 */
42
43 /* current state of generator */
44 static uint32_t X[K]; /* Fibonacci array */
45 static int cur; /* Current index in array. */
46 static int curL; /* this is always (cur - L) mod K */
47
48
49 /* seed the generator */
50 void
zrand_seed(uint32_t seed)51 zrand_seed(uint32_t seed)
52 {
53 int i;
54 uint32_t j, k;
55
56 /* Make zrandom() repeatable: Always reset X, cur and curL to their initial
57 values. -ed */
58 cur = 0;
59 curL = K - L;
60 for (i = 0; i < K; i++)
61 X[i] = 0;
62
63 /* According to Knuth, "This computes a Fibonacci-like sequence; */
64 /* multiplication of indices by 21 [the constant D] spreads the */
65 /* values around so as to alleviate initial nonrandomness */
66 /* problems..." */
67 seed = seed % M;
68
69 X[0] = j = seed;
70 k = 1;
71
72 for (i = 1; i < K; i++) {
73 int which = (D*i) % K;
74 X[which] = k;
75 if (j < k) k -= M;
76 k = j - k;
77 j = X[which];
78 }
79
80 /* `warm up' the generator. Three was good enough for Knuth... */
81 for (i = 0; i < 5 * K; i++)
82 zrand();
83 }
84
85
86 /* return next value in the sequence */
87 uint32_t
zrand()88 zrand()
89 {
90 uint32_t result;
91
92 result = X[cur] < X[curL] ? M : 0;
93 result += X[cur] - X[curL];
94 X[cur] = result;
95
96 cur++; if (cur == K) cur = 0;
97 curL++; if (curL == K) curL = 0;
98
99 return result;
100 }
101