[Python] Python은 난수를 어떻게 생성할까?

🧐 파이썬에서 나오는 난수는 어떻게 고른 수 일까요?

Python 에서는 아래와 같은 코드로 여러 난수를 생성할 수 있습니다.

Python 난수 생성 예시

이 때 난수는 어떤 방식으로 생성되는 것일까요?
결론부터 말하자면 파이썬은 메르센 트위스터 (Mersenne Twister)를 사용해 난수를 생성합니다!
 
 
 

🤨 그렇다면 메르센 트위스터란 무엇일까요?

컴퓨터는 사람과 달리 진짜 난수를 생성할 수 없습니다.
하지만, 개발을 하다보면 랜덤한 수가 필요할 때가 있습니다.
각종 개발 언어는 이런 상황에 개발자에게 난수를 제공하기 위해
랜덤해 보이지만 사실은 규칙이 있는 의사 난수 생성기 (pseudorandom number generator)를 사용합니다.
Python, C++, 더 나아가 엑셀,  MATLAB등에서 사용하는 의사 난수 생성기가 바로 메르센 트위스터입니다!

메르센 소수는 2의 거듭제곱에서 1이 모자란 $2^1-1=1, 2^2-1=3, 2^3-1=7$ 등의 수를 말합니다.
메르센 트위스터라는 이름은 난수의 반복 주기가 메르센 소수인 것에서 유래했으며,
생성하는 난수의 bit 수에 따라 MT19937, MT19937-64로 구분됩니다.

 
메르센 트위스터는 LFSR(Linear Feedback Shift Register) 계열의 의사 난수 생성기 입니다.
LFSR는 현재 상태에서 선형 연산을 통해 다음 상태를 생성하는 레지스터로,
이 때 사용되는 선형 연산은 보통 XOR 연산이라고 합니다.
 
 
 

😞 그래서 그게 뭔데,,,

이렇게 하이 레벨의 설명을 찾아보는 것보다
그냥 어떻게 구현됐나 보는게 이해가 쉬울 것 같아 알고리즘 구현체를 찾아봤습니다 😂
전반적인 과정을 간단히 설명하자면 아래와 같은 단계로 이루어 집니다.

1. seed를 기반으로 $n$개의 수가 들어있는 state array 준비
2. State array를 사용해서 $n$개의 난수 생성
3. $n$개의 난수를 다 사용했을 경우 state array를 업데이트 (Twist)
4. 2번부터 다시 반복

아래에서는 32비트 난수를 생성하는 MT19937 알고리즘을 예시로 설명하도록 하겠습니다.
 

1. State array를 준비

MT19937 알고리즘으로 난수를 생성하기 위해서는 $n=624$ 개의 32-bit 정수가 들어있는 state array를 준비해야합니다.
배열의 $i$ 번 째 원소 $x_i $ 는 아래와 같이 표현할 수 있고, $x_0$ 은 seed로 주어지는 값입니다.
$$x_i = f \times (x_{i-1} \oplus (x_{i-1} \gg (w - 2)) + i )$$
이 때 $w=32$는 word 크기로, 생성하고자 하는 난수의 비트 수를 의미하며, $f=1812433253$ 입니다.
 

2. State array를 사용하여 난수 생성

이 부분은 코드로 설명을 대체하도록 하겠습니다,,,
코드의 u, d, s, b, t, c, l 은 모두 하이퍼파라미터로, 사전에 정의하는 숫자 입니다.
해당 연산에 주기성이 왜 메르헨소수 인지에 대한 수학적 이론이 있을 것 같은데,
이것까지 알아보기엔 너무 깊은 내용인 것 같아 관뒀습니다ㅎ,,,

 

3. Twist 과정을 통한 state array 초기화

2번 과정을 통해 state array안의 숫자 $n$개를 모두 난수로 만들었을 경우 state array를 다시 채워 주어야 하는데,
이 부분또한 코드로 설명을 대체하도록 하겠습니다.

막상 수학적 원리를 제외하고 설명하다보니 상당히 간단해보이는데요,
전체 구현체를 살펴보면 아래와 같습니다.

MT19937 구현체

 
문득 궁금해서 가벼운 마음으로 찾아봤는데, 생각보다 깊은 내용이라 제대로 알아보지 못한 느낌이네요 🥹
잘못된 내용이 있다면 알려주시길 바랍니다! 감사합니다 😊