컴퓨터가 난수를 생성하는 방법에는 여러 가지가 있는데,

외부의 물리적인 도움을 받지 않고 생성되는 난수는 모두 의사 난수라고 불린다.

진정한 의미의 난수가 아니라 시드에 의해 결정되거나 (출력을 시드로서 되먹임을 하는 구조인 경우) 주기성을 가지고 반복되기 때문이다.


팩토리오 내에서 RNG를 구현 한다면 스네이크 게임 등을 만들 수 있을 것이다.


의사 난수를 생성하는 방법을 검색을 해 보니 주로 4가지 방법이 보였다.


1. 중앙제곱법

중앙제곱법은 폰 노이만이 1949년에 고안한 방법이다.

임의의 숫자를 제곱한 다음 그 숫자의 중앙 부분을 가져와 새로운 난수를 만드는 방식이다.

페이즈대상값제곱값난수
0123415227561522756
152272732152927321529
232151033622510336225

딱 봐도 엄청 예측하기 쉬워보이고, 아웃풋도 0과 9999 사이에 균일하게 분포되어 있지 않다.


2. 선형합동법(LCG)

위키백과 '선형 합동 생성기'

선형합동법은 다음과 같은 점화식으로 정의된다.

여기서 X가 우리가 원하는 의사 난수 수열이고 나머지는 임의의 정수다.

ANSI C 표준은 m=2147483648, a=1103515245, c=12345로 정해져 있다.

이는 암산으로 계산하기는 살짝 어려워 보이지만 그래도 한 수를 알면 다음 수를 쉽게 계산할 수 있다.

최고의 경우 m의 주기를 기대해 볼 수 있다. (이 경우 2^32)


3. 메르센 트위스터

선형 되먹임 시프트 레지스터(LSFR)을 약간 변형한 방법인 GSFR를 이용하여 624차원 벡터를 'Twist'하는 방법이라고 한다.

무슨 말인지 잘 모르겠지만 시프트 연산의 구조 때문에 의외로 선형합동법 보다도 속도가 빠르다고 하며,

난수의 품질이 좋기 때문에 거의 모든 프로그램이 이 구조로 난수를 생성한다고 한다.

반복 주기는 2^19937-1 이라고 한다.


4. XOR 시프트

위키백과 'XOR시프트'

이것도 역시 LSFR을 이용하지만 메르센 트위스터보다 훨씬 간단하고 속도는 더욱 빠르다.

TeatU01 이라고 하는 난수 품질 테스트를 통과하지 못 한다고 한다.




LCG를 이용한 방법


포럼에도 몇 가지 있지만 청사진 스트링이 없으니,

레딧 글에 있는 구조를 설명하도록 하겠다.



위에 있는 두 조합기가 m, a, c값이 들어 있는 진짜 RNG고 밑은 출력 장치다.

먼저 위에서 점화식을 계산하고 밑에서 오른쪽 비트 시프트를 하고 65536을 더해 양수로 만든다.

그 이후 모듈로 연산을 통해 0-25 사이의 값을 뽑아낸다.


청사진 링크


레딧 글 2


이 둘은 XOR시프트 기반 RNG이다.

밑에 있는 구조의 엔트로피 주입기가 흥미로운데, 기차가 선로를 지나갈 때 마다 신호를 입력해서 난수를 더욱 랜덤하게 만드는 구조다.


레딧 글 3

이것도 역시 XOR시프트 기반 RNG인데 위에 둘 보다 훨씬 복잡한 구조로 완전히 균일한 16비트 난수를 생성한다.

(시드와 아웃풋이 모두 16비트 숫자인데 이 둘이 일대일대응한다)




작동 구조:

인풋의 숫자를 왼쪽으로 8번 시프트 시킨다.

인풋과 방금 만든 새로운 숫자를 XOR하고 결과값을 S0으로 저장한다.

S0의 왼쪽 8비트와 오른쪽 8비트를 바꾼 다음 인풋에 덮어쓰기한다.

S0을 왼쪽으로 1번 시프트 시킨다.

FF80과 방금 만든 숫자를 XOR하고 결과값을 S1에 저장한다.

S1이 1로 끝나면 8180, 0으로 끝나면 1FF4와 XOR시키고 결과값을 인풋에 덮어쓰기한다.

S1이 22016이나 21674면 강제로 인풋을 0으로 만든다.


더 읽어볼 만한 글:

재밌게 읽은 난수 관련 포스팅

위키백과 '난수 생성'

위키백과 '선형 되먹임 시프트 레지스터'

꺼무위키


이번에는 Html 배워서 표도 걸어보고 링크 걸고 밑에 밑줄도 그어봤음

되게 깔끔해서 좋은듯