Skip to content

Instantly share code, notes, and snippets.

@Alfex4936
Last active October 17, 2020 04:18
Show Gist options
  • Select an option

  • Save Alfex4936/3ce293f5d813e5af2c12fc42cb9cf057 to your computer and use it in GitHub Desktop.

Select an option

Save Alfex4936/3ce293f5d813e5af2c12fc42cb9cf057 to your computer and use it in GitHub Desktop.
Mersenne Twister in Python
class MTP:
def __init__(self):
# Coefficients
self.a = 0x9908B0DF # 2567483615
self.b = 0x9D2C5680 # 2636928640
self.c = 0xEFC60000 # 4022730752
self.f = 1812433253
self.l = 18
self.m = 397
self.n = 624
self.s = 7
self.t = 15
self.u = 11
self.w = 32
self.state = [0] * 624
self.lower_mask = 0x7FFFFFFF # 2147483647
self.upper_mask = 0x80000000 # 2147483648
self.index = 625
def seed(self, a=0):
# Official Python implementation at
# https://github.com/python/cpython/blob/6989af0bc7ea1e9a1acea16794e6f723d7b44110/Modules/_randommodule.c#L265
self.state[0] = a
for i in range(1, self.n):
temp = (
self.f * (self.state[i - 1] ^ (self.state[i - 1] >> (self.w - 2))) + i
)
self.state[i] = self.int_32(temp)
def twist(self):
# 32비트 int를 사용하므로 0xFFFFFFFF 마스킹 스킵
for i in range(1, self.n):
"""temp = (self.state[i] & self.upper_mask) + (
self.state[(i + 1) % self.n] & self.lower_mask
)
temp_shift = temp >> 1
if temp % 2 != 0:
temp_shift ^= self.a
self.state[i] = self.state[(i + self.m) % self.n] ^ temp_shift
"""
self.state[i] = (
0x6C078965 * (self.state[i - 1] ^ self.state[i - 1] >> 30) + i
)
self.index = 0
def gen_random_int(self):
if self.index >= self.n:
self.twist()
y = self.state[self.index]
y = y ^ (y >> self.u)
y = y ^ ((y << self.s) & self.b)
y = y ^ ((y << self.t) & self.c)
y = y ^ (y >> self.l)
self.index += 1
return self.int_32(y)
def int_32(_, number):
return int(number & 0xFFFFFFFF) # unsigned int
def random(self):
""" return uniform ditribution in [0,1) """
return self.gen_random_int() / 4294967296 # 0xFFFFFFFF + 1
def randrange(self, a, b):
# Official Python implementation at
# https://github.com/python/cpython/blob/master/Lib/random.py
""" return random int in [a,b) """
n = self.random()
return int(n / (1 / (b - a)) + a)
def randint(self, a, b):
return self.randrange(a, b + 1)
if __name__ == "__main__":
rng = MTP()
rng.seed(123)
for i in range(3):
print(rng.gen_random_int())
print(rng.random())
print("Random Range [a, b)")
for i in range(10):
print(rng.randrange(1, 10), end=" ")
print("\nRandom Int [a, b]")
for i in range(10):
print(rng.randint(1, 10), end=" ")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment