20200914 - 심심해서 쓰는 글 - 난수 생성 알고리즘

def generate(n):
	return (a * generate(n-1)+c) % m

컴퓨터는 일정한 규칙을 가지고 그를 통해 output을 출력해내는 존재이다. 하지만 랜덤이라는 것은 일정한 규칙이 있으면 안 된다. 당연한 거 아닌가? 규칙이 있는 순간 랜덤은 랜덤이 아니다. 그렇다면 랜덤처럼 보이게 알고리즘을 짜야한다. 다음 글을 참고하였다:https://evan-moon.github.io/2019/07/14/what-is-random/

컴퓨터가 만드는 랜덤은 정말로 랜덤할까?

 

1. 중앙제곱법

이 방법은 특정 숫자에 대해 제곱을 하고 특정한 부분을 뽑아내고, 다시 그 숫자를 제곱하여 다시 일부분을 뽑아내고...이렇게 하는 방식이다. 랜덤이라기에는 규칙이 너무 단조롭다. 좀 더 잘 이해하기 위해 예를 추가하자면 다음과 같다:

 

Phase	대상값	제곱	뽑아낼 난수(bold처리)
0	1234	1522756	1522756
1	5227	27321529	27321529
2	3215	10336225	10336225

 

아~너무 예측하기 쉬운걸~

 

2. Linear Congruential Method

다음과 같은 재귀적 방법으로 난수를 뽑아낸다. 

def generate(n):
	return (a*generate(n-1)+c)%m

ANSI C 표준에서 m = 2**31, a=1103515245,c=12345 로 정해져 있다고 한다.

하지만 이 또한 얼마든지 예측 가능한 난수 생성법이다.

 

3. Mersenne Twister

우선 주기 한번동안의 알고리즘을 살펴보자.

1. seed를 사용하여 624 만큼의 길이를 가진 벡터를 생성. seed는 보통 하드웨어 노이즈나 오늘 날짜를 사용한다.
2. 이 벡터를 사용하여 624개의 유사 난수를 만든다.
3. 이 벡터에 노이즈를 준 후 다시 2번을 반복. 이 노이즈를 주는 행위를 Twist한다고 한다.

Twist하는 과정에서 GFSR(Generalized Feedback Shift Register라는 방법을 사용한다고 한다. GFSR은 LFSR에서 발전한 방법인데, LFSR이란 우선 몇개의 간단한 메모리 주소를 골라놓고 초기화된 인풋을 레지스터에 넣어놓는다. 그러면 오른쪽으로 비트가 한개씩 밀리게 되고, 그러면 끝에서 삐져나온 비트를 얻게 된다. 그러고 나면 미리 골라놨던 메모리 주소에서 값을 빼온 다음 순서대로 3개의 XOR 게이트에 통과시키게 되고, 그렇게 되면 다음 인풋이 나오게 되고 그 값을 레지스터에 넣고하는걸 반복한다.

 

 

이들도 아주 기초적인 수준의 알고리즘이다. 내가 이런걸 구현안하는게 다행이다 싶기도 하다.