※ [ ]속의 영어는 한글로 제가 의역하거나 약자만 사용했습니다.
c++에서 rand()함수는 의사 난수를 만들기 위해서 선형 합동 생성기(Linear Congrence Generator)를 사용한다고 했다.
파이썬에서는 MT19937을 사용한다.
메르센 트위스터는 1997년에 마츠모토 마코토와 니시무라 다쿠지가 개발한 의사 난수 생성기이다.
솔직히 쉽게 설명하고 싶은데 내용의 난이도가 높았다. 그래서 문답 형식으로 설명해보려고 한다.
1. 왜 이름이 메르센 트위스터 일까?메르센 소수(Mersenne Primes)의 메르센과 TGFSR[Twisted Generalized Feedback Shift Register]의 Twisted에서 따와서 만들었다.
TGFSR은 마코토와 쿠리아가 GFSR[Generalized Feedback Shift Register]을 개량시킨 것이다.
그렇다면 GFSR은 무엇일까?
내 실력으로 설명하기가 너무 어렵다. 그래도 할 수 있을 때까지 해본다.
GFSR은 이름에서 추측 할 수 있듯이, LFSR[Linear Feedback Shift Register]라는 것의 일반화한 것인데 감을 잡기위해서 설명해본다.
LFSR의 기능은 기존에 숫자에서 특정한 bit들만 뽑아서 XOR연산을 거듭해서 하고 그 나온 결과 값을 높은 자리의 bit에 넣으면서 한 bit를 밀어내는 것(shift)이다.
특정한 bit들을 잘만 뽑는다면 기존에 숫자에서 겹치지 않고 다양한 숫자를 만들 수 있다.
GFSR은 bit들만 뽑아서 XOR연산을 거듭해서하는 것 뿐만 아니라 더 다양한 방법을 채택하는 것들이라고 추측할 수 있다.
2. 왜 메르센 지수19937을 가진 메르센 소수를 골랐을까?메르센 트위스터로 생성하고 난뒤 2^19937 번째가 되면 다시 같은 수가 된다.
이를 증명하려면 O(19937^2)정도의 계산이 필요하다.
메르센 지수가 너무 크면 주기가 메르센 소수인 것을 같은 방식으로 보이기 힘들다.
3. 왜 빠른가?Bitshift, Bitwise XOR, Bitwise OR, bitwise AND만 가지고 계산할 수 있기 때문이다. 즉 비트 단위의 연산으로만 구성할 수 있다.
사실은 행렬의 곱으로 수를 생성해야 한다.
하지만 연산에서 사용되는 A행렬과 T행렬의 모양이 매우 좋아서 위의 비트 연산만 가지고 표현이 가능하다.
행렬곱은 비트연산에 비해서 느린편이다.
행렬 연산을 위해서 따로 반도체 칩이 만들어지기 까지한다.
4. 어떻게 만드는가?초기값[Initial Seeds]를 0이 아닌 양의 정수 623개를 만들어서 사용한다.
{seed 메서드 가 이 값들을 변경 시켜준다.}
그렇다면 623개가 들어있는 양의 정수 배열이 있다고 생각하자.
0번째 정수의 상위 첫번째 비트와 1번째 정수의 상위 첫번째 비트를 뺀 나머지 비트와 결합을 한다.
그 정수를 x0라고 하자
x0의 하위 첫번째 비트가 0이면 Bit right shift연산을 하고
하위 첫번째 비트가 1이면 Bit right shift연산을 하고난 다음에
행렬A의 연산을 쉽게하기위한 a의 이진수 표현인 1001 1001 0000 1000 1011 0000 1101 1111과 Bitwise AND연산을 한다.
마지막으로 397번째 정수와 Bitwise XOR연산을 한다. 그후 0번째 정수에 넣는다.
1번째 정수의 상위 첫번째 비트와 2번째 정수의 상위 첫번째 비트를 뺀 나머지 비트와 결합을 한다.
그 정수를 x1라고 하자
x1의 하위 첫번째 비트가 0이면 Bit right shift연산을 하고 , 하위 첫번째 비트가 1이면 Bit right shift연산을 하고난 다음에
a의 이진수 표현인 1001 1001 0000 1000 1011 0000 1101 1111과 Bitwise AND연산을 한다.
마지막으로 398번째 정수와 Bitwise XOR연산을 한다. 그후 1번째 정수에 넣는다.
위의 과정을 226번째 정수까지 실시한다.
{위 과정과 아래 과정이 뒤바뀌는 것을 보고 Twister라고 했을 지도 모르겠다.}
227번째 정수의 상위 첫번째 비트와 228번째 정수의 상위 첫번째 비트를 뺀 나머지 비트와 결합을 한다.
그정수를 x227이라고 하자.
x227의 하위 첫번째 비트가 0이면 Bit right shift연산을 하고 , 하위 첫번째 비트가 1이면 Bit right shift연산을 하고난 다음에
a의 이진수 표현인 1001 1001 0000 1000 1011 0000 1101 1111과 Bitwise AND연산을 한다.
마지막으로 0번째 정수와 Bitwise XOR연산을 한다. 그후 227번째 정수에 넣는다.
228번째 정수의 상위 첫번째 비트와 229번째 정수의 상위 첫번째 비트를 뺀 나머지 비트와 결합을 한다.
그정수를 x228이라고 하자.
x228의 하위 첫번째 비트가 0이면 Bit right shift연산을 하고 , 하위 첫번째 비트가 1이면 Bit right shift연산을 하고난 다음에
a의 이진수 표현인 1001 1001 0000 1000 1011 0000 1101 1111과 Bitwise AND연산을 한다.
마지막으로 1번째 정수와 Bitwise XOR연산을 한다. 그후 228번째 정수에 넣는다.
위과정을 622번째 정수까지 실시한다.
623번째 정수의 상위 첫번째 비트와 0번째 정수의 상위 첫번째 비트를 뺀 나머지 비트와 결합을 한다.
그 정수를 x623이라고 하자.
x623의 하위 첫번째 비트가 0이면 Bit right shift연산을 하고 , 하위 첫번째 비트가 1이면 Bit right shift연산을 하고난 다음에
a의 이진수 표현인 1001 1001 0000 1000 1011 0000 1101 1111과 Bitwise AND연산을 한다.
마지막으로 396번째 정수와 Bitwise XOR연산을 한다. 그후 623번째 정수에 넣는다.
0번째 정수를 꺼내서 템퍼링(Tempering)을 한다.
템퍼링은 템퍼링 행렬(Tempering Matrix) T을 곱하는 것이다.
목적은 K분포[K-distribution]의 정확도를 높이기 위함이다.
행렬T의 연산은 Bit right shift와 Bit left shift, bitwise AND 들로 쉽게 계산 할 수 있다.
템퍼링한 0번째 정수가 우리가 원하는 난수다.
다음에 있는 내용을 바탕으로 작성하였습니다.
[http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/ewhat-is-mt.html]; 히로시마대학교 수학과에 있는 MT설명 페이지
[https://www.sciencedirect.com/science/article/pii/S1071579785710027]; Niederreiter H가 작성한 MRMM 설명글
[https://en.wikipedia.org/wiki/Linear-feedback_shift_register]; GFSR의 특별한 케이스인 LFSR 설명
이야기 상 논리가 문제가 있거나 잘못된 정보를 알려 주신다면 고맙겠습니다. 수정하겠습니다.
알려주신 여러분 덕에 이 글을 읽는 모두가 올바른 정보를 얻을 수 있게 합니다
