Last active
October 17, 2020 04:18
-
-
Save Alfex4936/3ce293f5d813e5af2c12fc42cb9cf057 to your computer and use it in GitHub Desktop.
Mersenne Twister in Python
This file contains hidden or 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
| 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