Created
August 7, 2014 15:42
-
-
Save cuixin/1b8b6bd7bfbde8fe76e8 to your computer and use it in GitHub Desktop.
Mersenne Twister in c# & golang
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
public class MT19937 | |
{ | |
private const ulong N = 312; | |
private const ulong M = 156; | |
private const ulong MATRIX_A = 0xB5026F5AA96619E9L; | |
private const ulong UPPER_MASK = 0xFFFFFFFF80000000; | |
private const ulong LOWER_MASK = 0X7FFFFFFFUL; | |
private static ulong [] mt = new ulong[N+1]; | |
private static ulong mti = N + 1; | |
public MT19937(ulong seed) | |
{ | |
this.Seed(seed); | |
} | |
public void Seed(ulong seed) | |
{ | |
mt[0]= seed; | |
for (mti=1; mti < N; mti++) | |
{ | |
mt[mti] = (6364136223846793005L * (mt[mti-1] ^ (mt[mti-1] >> 62)) + mti); | |
} | |
} | |
public ulong Int63() | |
{ | |
ulong x = 0; | |
ulong [] mag01 = new ulong[2] {0x0UL, MATRIX_A}; | |
if (mti >= N) | |
{ | |
ulong kk; | |
if (mti == N+1) | |
{ | |
Seed(5489UL); | |
} | |
for (kk=0; kk < (N - M); kk++) | |
{ | |
x = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK); | |
mt[kk] = mt[kk + M] ^ (x >> 1) ^ mag01[x & 0x1UL]; | |
} | |
for (;kk<N-1;kk++) | |
{ | |
x = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK); | |
mt[kk] = mt[kk - M] ^ (x >> 1) ^ mag01[x & 0x1UL]; | |
} | |
x = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK); | |
mt[N-1] = mt[M-1] ^ (x >> 1) ^ mag01[x & 0x1UL]; | |
mti = 0; | |
} | |
x = mt[mti++]; | |
x ^= (x >> 29) & 0x5555555555555555L; | |
x ^= (x << 17) & 0x71D67FFFEDA60000L; | |
x ^= (x << 37) & 0xFFF7EEE000000000L; | |
x ^= (x >> 43); | |
return x; | |
} | |
public ulong IntN(ulong value) { | |
return Int63() % value; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package MersenneTwister | |
const N = 312 | |
const M = 156 | |
const MATRIX_A = 0xB5026F5AA96619E9 | |
const UPPER_MASK = 0xFFFFFFFF80000000 | |
const LOWER_MASK = 0x7FFFFFFF | |
type MT19937_64 struct { | |
array [312]uint64 //state vector | |
index uint64 // array index | |
} | |
func New() *MT19937_64 { | |
return &MT19937_64{ | |
index: N + 1, | |
} | |
} | |
func (m *MT19937_64) Seed(seed int64) { | |
m.array[0] = uint64(seed) | |
for m.index = 1; m.index < N; m.index++ { | |
m.array[m.index] = (6364136223846793005*(m.array[m.index-1]^(m.array[m.index-1]>>62)) + m.index) | |
} | |
} | |
func (m *MT19937_64) Int63() uint64 { | |
var i int | |
var x uint64 | |
mag01 := []uint64{0, MATRIX_A} | |
if m.index >= N { | |
if m.index == N+1 { | |
m.Seed(int64(5489)) | |
} | |
for i = 0; i < N-M; i++ { | |
x = (m.array[i] & UPPER_MASK) | (m.array[i+1] & LOWER_MASK) | |
m.array[i] = m.array[i+(M)] ^ (x >> 1) ^ mag01[int(x&uint64(1))] | |
} | |
for ; i < N-1; i++ { | |
x = (m.array[i] & UPPER_MASK) | (m.array[i+1] & LOWER_MASK) | |
m.array[i] = m.array[i+(M-N)] ^ (x >> 1) ^ mag01[int(x&uint64(1))] | |
} | |
x = (m.array[N-1] & UPPER_MASK) | (m.array[0] & LOWER_MASK) | |
m.array[N-1] = m.array[M-1] ^ (x >> 1) ^ mag01[int(x&uint64(1))] | |
m.index = 0 | |
} | |
x = m.array[m.index] | |
m.index++ | |
x ^= (x >> 29) & 0x5555555555555555 | |
x ^= (x << 17) & 0x71D67FFFEDA60000 | |
x ^= (x << 37) & 0xFFF7EEE000000000 | |
x ^= (x >> 43) | |
return x | |
} | |
func (m *MT19937_64) IntN(value uint64) uint64 { | |
return m.Int63() % value | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Please note, if seeding MT with less than 2496 bytes' worth of data it's recommended to run the generator for ~10000 iterations as part of initialization to ensure the full internal state is primed:
https://stackoverflow.com/questions/13114823/priming-the-mersenne-twister-prng#13291297