-
Notifications
You must be signed in to change notification settings - Fork 1
/
rand.go
82 lines (70 loc) · 1.61 KB
/
rand.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package hackutils
import "fmt"
// Implementation of the Mersenne Twister PRNG algorithm, following the
// constants and pseudocode from https://en.wikipedia.org/wiki/Mersenne_Twister,
// for the 32-bit version.
const mtW = 32
const mtN = 624
const mtM = 397
const mtR = 31
const mtF = 1812433253
const mtA = 0x9908B0DF
const mtU = 11
const mtD = 0xFFFFFFFF
const mtS = 7
const mtB = 0x9D2C5680
const mtT = 15
const mtC = 0xEFC60000
const mtL = 18
const mtLowerMask uint32 = (1 << mtR) - 1
const mtUpperMask uint32 = ^mtLowerMask
type mt19937 struct {
state [mtN]uint32
index uint32
}
// NewMT19937 creates a new MT PRNG with the given seed.
func NewMT19937(seed uint32) *mt19937 {
mt := new(mt19937)
mt.state[0] = seed
mt.index = mtN
for i := 1; i < mtN; i++ {
xn1 := mt.state[i-1]
mt.state[i] = mtF*(xn1^(xn1>>(mtW-2))) + uint32(i)
}
return mt
}
// NewMT19937FromState creates a new MT PRNG with the given state.
func NewMT19937FromState(state [mtN]uint32, index uint32) *mt19937 {
mt := new(mt19937)
mt.state = state
mt.index = index
return mt
}
func (mt *mt19937) DumpState() {
fmt.Println("state:", mt.state)
fmt.Println("index:", mt.index)
}
func (mt *mt19937) Next() uint32 {
if mt.index >= mtN {
mt.twist()
}
// Tempering.
y := mt.state[mt.index]
y ^= ((y >> mtU) & mtD)
y ^= ((y << mtS) & mtB)
y ^= ((y << mtT) & mtC)
y ^= (y >> mtL)
mt.index++
return y
}
func (mt *mt19937) twist() {
for i := 0; i < mtN; i++ {
x := (mt.state[i] & mtUpperMask) + (mt.state[(i+1)%mtN] & mtLowerMask)
xA := x >> 1
if x%2 != 0 {
xA ^= mtA
}
mt.state[i] = mt.state[(i+mtM)%mtN] ^ xA
}
mt.index = 0
}