선형합동생성기(LCG)는 연속한 출력 n개를 좌표로 묶으면 점이 등간격 평행 초평면 위에만 놓인다. IBM RANDU는 3차원에서 그 평면이 15장뿐이다. 값을 하나씩 보는 저차원 검정은 이를 못 보고, 점구름의 시점을 평면과 나란히 돌리는 순간 줄무늬가 드러난다.
한 그림, 두 시점
난수 생성기에서 값을 세 개씩 꺼내 $(u_k, u_{k+1}, u_{k+2})$ 라는 좌표로 묶는다. 10만 개를 그렇게 묶어 3차원 공간에 찍는다. 정면에서 보면 흔한 점구름이다 — 빈 곳도 뭉친 곳도 없이 입방체를 고르게 채운다. 그런데 시점을 특정 방향으로 돌리면 같은 점들이 완전히 다르게 보인다. 점이 15장의 얇은 판 위에만 놓여 있고, 판과 판 사이는 아무것도 없는 진공이다.
그림 1의 두 패널은 같은 데이터다. 데이터는 그대로 두고 보는 각도만 바꿨다. 여기 쓴 생성기는 1960년대 IBM이 배포한 RANDU이고, 이 글은 저 15라는 숫자가 어디서 나오는지를 따라간다.
균등성 검정도, 자기상관 검정도, 런 검정도 이 구조를 못 본다. 그 검정들은 값을 하나씩 또는 둘씩 보는데, 격자는 세 개를 묶은 자리에서 생기기 때문이다. 난수를 묶어 쓰는 곳은 많다. 다차원 몬테카를로 적분, 게임의 뽑기 테이블, A/B 실험의 사용자 배정, 시뮬레이션 초기 좌표 — 묶는 개수가 곧 격자가 드러나는 차원이다. 그리고 이 격자가 어디서 오는지는 생성기의 식 한 줄에 이미 다 들어 있다.
선형합동생성기와 격자
선형합동생성기는 이름 그대로 한 줄짜리 점화식이다.
곱하고, 더하고, 나머지를 취한다. 식 1로 만든 수열은 겉보기에 뒤죽박죽이지만 이웃한 두 값 사이의 관계는 완전히 결정적이다. $x_{k+1}$ 은 $x_k$ 의 일차식이다.
여기서 격자가 나온다. $n$ 개를 묶어 점 $(x_k, x_{k+1}, \dots, x_{k+n-1})$ 을 만들면, 그 좌표들끼리는 서로 일차 관계로 묶여 있다. 나머지 연산 때문에 관계식은 등식 대신 합동식으로 적히는데, 합동식은 "정수 하나만큼 어긋난다"는 뜻이다. 정수만큼씩 어긋나는 일차 관계는 곧 평행한 평면들이다. 그래서 $n$ 차원 점들은 공간에 자유롭게 흩어지지 못하고, 등간격으로 늘어선 평행 초평면 다발 위에만 앉는다.
이 사실 자체는 나쁜 소식이 아니다. 평면이 수천 장이고 간격이 촘촘하면 실제 표본 크기에서는 구별이 안 된다. 문제는 평면이 몇 장이냐다. 그 개수는 $a$, $c$, $m$ 을 어떻게 고르느냐에 따라 수천 장이 되기도 하고 열몇 장이 되기도 한다. RANDU가 고른 값들을 보면 어느 쪽인지 금방 드러난다.
RANDU의 항등식
RANDU는 $a = 65539$, $c = 0$, $m = 2^{31}$ 을 썼다. 65539라는 숫자는 $2^{16} + 3$ 이다. 곱셈을 시프트와 덧셈으로 처리할 수 있어 당시 하드웨어에서 빨랐다. 그 편의에는 대가가 따라붙는데, 승수를 제곱해 전개해 보면 곧바로 드러난다.
$m = 2^{31}$ 로 나머지를 취하면 $2^{32}$ 항은 통째로 사라지고, 남는 것은 $6 \cdot 2^{16} + 9$ 다. 그런데 $2^{16}$ 은 $65539 – 3$ 이다. 그러니 남은 값은 $6 \cdot 65539 – 9$ 로 다시 쓸 수 있다. 정리하면 $65539^2 \equiv 6 \cdot 65539 – 9 \pmod{2^{31}}$ 라는 정확한 항등식이다. 이걸 점화식에 넣으면 세 항짜리 관계가 나온다.
식 2는 근사가 아니라 모든 $k$ 에서 정확히 성립하는 항등식이다. 이제 정규화한 값 $u = x / 2^{31}$ 로 옮겨 보자. 합동식을 등식으로 풀면 $9x_k – 6x_{k+1} + x_{k+2}$ 가 $2^{31}$ 의 정수배가 된다. 양변을 $2^{31}$ 로 나누면 $s = 9u_k – 6u_{k+1} + u_{k+2}$ 가 정수라는 뜻이다.
정수라는 것만으로는 아직 개수가 안 나오고, 범위를 재야 나온다. $u$ 는 모두 0과 1 사이다. $s$ 가 가장 작아지는 조합은 $9 \cdot 0 – 6 \cdot 1 + 0 = -6$ 이다. 가장 커지는 조합은 $9 \cdot 1 – 6 \cdot 0 + 1 = 10$ 이다. 열린 구간 $(-6, 10)$ 안의 정수는 $-5$ 부터 9까지 15개이고, 그게 평면 15장이다.
말로만 하면 미덥지 않으니 직접 돌려 보자. 표준 라이브러리만 쓴다. 아래 출력에서 볼 것은 두 가지다 — $s$ 가 정수에서 얼마나 벗어나는지, 그리고 실제로 몇 개의 값을 가지는지.
M = 2**31
x, u = 1, []
for _ in range(300_000):
x = (65539 * x) % M
u.append(x / M)
s = [9 * u[k] - 6 * u[k + 1] + u[k + 2] for k in range(len(u) - 2)]
gap = max(abs(v - round(v)) for v in s)
print("정수에서 벗어난 최대치:", gap)
print("s가 가지는 값:", sorted({round(v) for v in s}))
print("평면 개수:", len({round(v) for v in s}))정수에서 벗어난 최대치: 0.0
s가 가지는 값: [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
평면 개수: 15정수에서 벗어난 최대치가 0.0이다. 30만 스텝에서 얻은 삼중항 29만 9998개가 예외 없이 15개 값 중 하나에 정확히 떨어진다. 시드를 12345나 987654321로 바꿔도 같다.
그림 2의 위쪽이 그 15개 막대다. 가운데가 높고 양끝이 낮은 삼각형꼴인데, 이는 세 균등 변수의 가중합이 중앙에 몰리는 자연스러운 결과다. 실제 개수를 세어 보면 가운데 평면들에 각각 3만 3천 개 남짓, 양 끝 평면에는 2천 7백 개 정도가 앉는다. 아래쪽은 대조군이다. 승수 16807, 모듈러스 $2^{31}-1$ 을 쓰는 MINSTD로 같은 조합을 계산하면 정수 근방에 오는 비율이 0.0으로, 이 특정 조합에 대한 이산 구조가 없다.
단위 입방체 안에서 인접한 두 평면 사이의 거리도 바로 나온다. 법선 벡터가 $(9, -6, 1)$ 이므로 간격은 $1/\sqrt{81+36+1} = 1/\sqrt{118} \approx 0.0921$ 이다. 인접한 평면 사이에는 입방체 한 변의 10분의 1 가까운 간격이 통째로 비어 있다는 뜻이다.
Marsaglia 1968의 정리와 RANDU의 위치
RANDU만 그런가. 아니다. Marsaglia가 1968년 PNAS 논문에서 증명한 것은 훨씬 일반적인 명제다. 그는 모듈러스가 $m$ 인 곱셈형 생성기($c = 0$)에 대해 모든 $n$-튜플이 다음 개수 이내의 평행 초평면 위에 놓임을 증명했고, 덧셈 상수가 있는 경우도 같은 결과가 성립한다고 밝혔다.
식 3는 Minkowski의 볼록체 정리에서 나온다. 격자의 쌍대 격자에 충분히 짧은 벡터가 반드시 하나 있다는 것이고, 그 짧은 벡터가 곧 평면 다발의 법선이 된다. 승수를 아무리 잘 골라도 이 상한은 못 넘는다.
숫자를 넣어 보자. $m = 2^{31}$ 일 때 2차원은 65,536장 미만, 3차원은 2,344장, 4차원은 476장, 10차원은 38장이다. 차원이 오르면 상한이 급격히 무너진다.
그림 3에서 눈길이 가는 곳은 곡선보다 그 아래 찍힌 점이다. $m = 2^{31}$ 이 3차원에서 허용하는 상한은 2,344장인데 RANDU가 실제로 쓴 것은 15장, 상한의 0.64%다. 승수를 제대로 골랐다면 같은 모듈러스로 두 자릿수 이상 촘촘한 격자를 만들 수 있었다는 뜻이다. RANDU는 격자를 벗어나려다 실패한 생성기가 아니라, 누구나 갇히는 격자 안에서 자기 몫을 100분의 1 이하로 쓴 생성기다.
Marsaglia는 두 번째 상한도 함께 제시했다. 격자 관계식의 계수 절댓값 합이 그 자체로 평면 개수의 상한이 된다는 것이다. RANDU의 관계식 계수는 9, −6, 1이므로 합이 16이고, 관측된 15장이 바로 그 아래에 붙는다.
누가 먼저 봤나 — 통설 두 개 정정
정리가 이렇게 깔끔하면 발견의 이야기도 깔끔했을 것 같지만, 여기서 널리 도는 이야기 두 개를 정정해야 한다. 첫째, RANDU를 두고 "당시의 통계 검정을 다 통과했다"는 서술이 자주 붙는데 정확하지 않다. MacLaren과 Marsaglia는 1965년에 이미 3차원 이상의 경험적 검정에서 RANDU 계열의 실패를 관측했다. 통과한 것은 저차원 검정이었다. 당시 실무에서 주로 돌리던 검정이 1·2차원짜리였기 때문이다.
둘째, 이 구조를 Marsaglia가 처음 발견했다는 이야기도 사실과 다르다. Greenberger는 1965년에 RANNO 생성기의 출력을 오실로스코프에 띄워 "텅 빈 공간 조각"을 관찰했고, $u_i = 6u_{i-1} – 9u_{i-2}$ 라는 같은 점화식을 이미 지적했다. 격자 구조를 정면으로 재는 도구인 스펙트럴 테스트도 Coveyou와 MacPherson이 1967년에 먼저 내놓았다.
그러면 Marsaglia의 기여는 무엇인가. 축이다. 그는 결함을 "평면이 몇 장인가"라는 세는 양으로 바꿨고, 그 양이 모든 선형합동생성기에서 지키는 보편 상한을 증명했다. 개별 생성기의 흠을 하나씩 발견하는 일과, 어떤 생성기든 흠의 크기를 미리 잴 수 있게 만드는 일은 다르다.
지금도 재발한다
축이 생겼으면 그 축이 어디까지 닿는지도 그어 둬야 한다. 식 3가 다루는 것은 $\mathbb{Z}_m$ 위에서 선형인 생성기, 즉 선형합동생성기와 그 다항 확장인 다중재귀생성기(MRG)다. 메르센 트위스터나 xorshift처럼 $\mathbb{F}_2$ 위에서 선형인 생성기에는 그대로 옮겨 붙지 않는다. 비트 단위 배타적 논리합은 정수 덧셈이 아니고, 격자를 세우는 무대가 다르다.
그렇다고 안전하다는 말은 아니다. Haramoto와 Matsumoto는 2019년에 xorshift128+ 계열을 같은 눈으로 다시 봤다. 이 생성기는 V8을 비롯한 여러 자바스크립트 엔진의 난수 함수가 쓰는 것이다. 연속한 세 출력을 묶으면 3차원에서 점들이 8장의 평면에 몰린다. 무대가 $\mathbb{F}_2$ 로 바뀌고 해석도 새로 세웠지만, 손에 남는 그림은 1968년 것과 같은 종류다.
그래서 난수 생성기의 품질을 볼 때 검정 목록을 세는 것으로는 부족하다. 차원 $n$ 을 올리면 어떤 $\mathbb{Z}_m$-선형 생성기든 식 3가 정한 장수의 평면에 갇힌다. 품질을 재려면 격자의 장수를 세어야 한다.
그림 1의 오른쪽 패널로 돌아가자. RANDU의 줄무늬는 값을 세 개씩 묶고 점을 찍고 시점을 돌리는 것으로 충분히 보인다. 지금 열려 있는 브라우저의 난수도 같은 눈으로 검사됐다 — 다만 그쪽 평면은 훨씬 가파르게 누워 있어, 한 축을 $2^{23}$ 배 확대한 얇은 조각을 잘라야 8줄이 드러난다. 보는 방법이 조금 다를 뿐, 묻는 질문은 1968년과 같다.
더 읽기
- Marsaglia, G. "Random numbers fall mainly in the planes", PNAS 61(1):25–28 (1968). https://doi.org/10.1073/pnas.61.1.25
- Haramoto, H. & Matsumoto, M. "Again, random numbers fall mainly in the planes: xorshift128+ generators" (2019). https://arxiv.org/abs/1908.10020
- L’Ecuyer, P. "History of Uniform Random Number Generation", Proc. WSC 2017, pp. 202–230. https://www.informs-sim.org/wsc17papers/includes/files/016.pdf