Python random 모듈 구현하기

Python

python/cpython

 

0. MT19937 소개

파이썬에서 random.randint, random.randrange, random.seed...등은

모두 메르센-트위스터 기법 기반으로 제작되었다.

메르센 트위스터란 유사난수 생성기 중 하나이며, 주기는 2**19937-1 이며,

가장 널리 알려지고 다이하드 테스트와 같은 확률적 시험을 통과한 기법이다.

(Dieharder test > diehard test, 생일 문제 등을 포함한 테스트임)

 

이 글에서 파이썬 버전과 일치하진 않지만,

seed 함수, randrange 함수, randint 함수, random 함수를 구현해 볼 것이다.

 

(원본 파이썬 버전은 맨 아래 참고 링크

파이썬에선 SHA-1, hash를 이용하여 다음 값을 예측하기 어렵게 만들어져있다.)

 

1. 함수 구현

0. 보조 함수

이 함수는 unsigned int형으로 변환해준다.

def int_32(_, number):
    return int(number & 0xFFFFFFFF)  # unsigned int

 

1. 변수 지정

메르센 트위스터 기법을 사용하기 위한 몇몇 변수들을 지정해준다.

생성기 상태를 담을 크기는 최소 624

( ※ 계수 값 의미는 정확히 찾기가 어렵다. )

def __init__(self):
    # Coefficients
    self.a = 0x9908B0DF  # 2567483615, 난수 생성 과정에서 사용되는 계수 A
    self.b = 0x9D2C5680  # 2636928640, 난수 생성시 비트 연산에 사용되는 마스크 B
    self.c = 0xEFC60000  # 4022730752, 난수 생성 과정에서 사용되는 계수 C
    self.f = 1812433253  # 초기 상태 배열을 채우는 데 사용되는 계수 F
    self.l = 18          # 비트 시프트 연산에 사용되는 값 L
    self.m = 397         # 상태 배열에서 특정 범위 내의 요소를 참조할 때 사용되는 값 M
    self.n = 624         # 상태 배열의 크기 N
    self.s = 7           # 비트 연산에 사용되는 값 S
    self.t = 15          # 비트 시프트 연산에 사용되는 값 T
    self.u = 11          # 비트 시프트 연산에 사용되는 값 U
    self.w = 32          # 사용되는 워드의 비트 수 W

    self.state = [0] * 624  # 난수를 생성하기 위한 초기 상태 배열
    self.lower_mask = 0x7FFFFFFF  # 2147483647, 상태 배열을 업데이트할 때 사용되는 하위 마스크
    self.upper_mask = 0x80000000  # 2147483648, 상태 배열을 업데이트할 때 사용되는 상위 마스크
    self.index = 625             # 상태 배열에서 현재 인덱스를 추적하는 변수

 

2. seed 함수

사용법: seed(value)

state[624] 배열에 모든 상태를 저장한다.

파이썬 seed 부분 함수 링크

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)

 

3. twist 함수

state[1:624] 상태를 전부 업데이트 한다.

원래 주석 처리된 부분을 구현에 많이 사용하는데,

32비트 정수만 사용하므로 0xFFFFFFFF 마스킹 연산을 스킵해도 된다고 들었다.

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

 

4. 랜덤 int 생성기

index가 상태 크기를 넘으면 다시 twist하고, 아니면 비트 연산 값을 돌려준다.

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)

 

 

5. random(a, b)

0.0부터 1.0보다 작은 실수 값을 반환한다. [0.0, 1.0)

def random(self):
    """ return uniform ditribution in [0,1) """
    return self.gen_random_int() / 4294967296  # = 0xFFFFFFFF + 1

 

6. randrange(a, b)

a보다 크거나 같고, b보다 작은 값을 반환한다. [a, b)

공식 파이썬 randrange 함수 링크

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)

 

7. randint(a, b)

이 부분은 공식 파이썬과 같다.

a보다 크거나 같고, b보다 작거나 같은 값을 반환한다. [a, b]

def randint(self, a, b):
    return self.randrange(a, b + 1)

 

2. 결과 확인

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  # which is 2**w

    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)

 

시드 설정 후

gen_random_int(), random(), randrange(a, b), randint(a, b) 함수 실행

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=" ")

결과 (시드가 같으면 항상 값이 같게 나옴)

172234346
2462253275
2780881570
0.916880935896188
Random Range [a, b)
9 5 4 7 2 2 8 5 2 7 
Random Int [a, b]
9 4 4 8 2 10 10 9 10 6 

 

3. 참조 링크

파이썬 공식 random.py (Github)

python/cpython

메르센 트위스터 간단 Python언어 버전 (Github)

메르센 트위스터 간단 C++언어 버전 (Github)

메르센 트위스터 위키백과

원본 메르센 트위스터 C언어 구현

메르센 트위스터 논문1 (Archana Jagannatam)