RANDU

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
- 2.1. 초기 발견과 문제 제기
3. 수학적 분석
- 3.1. 상관관계 문제
- 3.2. 빠른 계산을 위한 비트 연산 (한국 특화)
4. 영향 및 평가
참조

1. 개요

RANDU는 1960년대에 개발된 선형 합동법칙 난수 생성기로, 생성된 난수들 간의 강한 상관관계로 인해 3차원 공간에서 점들이 특정 평면에 집중되는 현상을 보이는 등 난수 품질에 심각한 문제점을 가지고 있었다. 1970년대 초반까지 몬테카를로 시뮬레이션에 널리 사용되었으나, 결과의 신뢰성에 대한 의문을 제기하며, 1990년대 초반까지 대부분 제거되었지만, 1999년까지 일부 FORTRAN 컴파일러에서 사용되기도 하였다. RANDU는 단순 계산 속도에 치중하여 난수 생성의 통계적 품질을 간과한 사례로 평가받는다.

더 읽어볼만한 페이지

유사난수 생성기 - RC4
RC4는 로널드 라이베스트가 1987년에 설계한 스트림 암호 알고리즘으로, 과거 널리 사용되었으나 보안 취약점 때문에 현재는 안전하지 않은 암호로 간주된다.
유사난수 생성기 - 메르센 트위스터
메르센 트위스터는 마츠모토 마코토와 니시무라 타쿠지가 개발한 유사난수 생성 알고리즘으로, 긴 주기와 고차원 균등 분포를 특징으로 하지만 암호학적으로 안전하지 않고 상태 크기가 크다는 단점이 있어 다양한 변종이 개발되었다.
소프트웨어 버그 - 교착 상태
교착 상태는 둘 이상의 프로세스가 자원을 점유하고 서로의 자원을 요청하여 더 이상 진행할 수 없는 상태를 의미하며, 상호 배제, 점유 대기, 비선점, 순환 대기 네 가지 조건이 모두 충족되어야 발생하고, 운영 체제는 이를 예방, 회피, 무시, 발견하는 방법으로 관리한다.
소프트웨어 버그 - 글리치
글리치는 예기치 않은 오작동이나 오류를 뜻하며, 전자 공학, 컴퓨터, 비디오 게임, 텔레비전 방송, 대중문화 등 다양한 분야에서 기능 실패, 오류, 그래픽 및 사운드 문제, 신호 오류 등의 이상 현상을 포괄적으로 지칭하는 용어이다.

RANDU
RANDU
종류	의사 난수 생성기
출력 범위	1, 2³¹ − 1
출력 범위 (개방 구간)	(0, 1)

2. 역사

RANDU는 1960년대에 개발된 의사 난수 발생기이다. 개발 이후 IBM System/360 계열 컴퓨터를 비롯한 여러 시스템에서 널리 사용되었다.^[7] 특히 계산 속도가 빠르다는 장점 때문에 1970년대 초반까지 몬테 카를로 시뮬레이션과 같은 다양한 분야에서 활발하게 활용되었다.^[6]

그러나 RANDU의 문제점은 비교적 이른 시기인 1963년에 이미 지적되었으며^[7], 특히 32비트 IBM System/360 시스템용으로 이식되면서 그 결함이 널리 퍼지게 되었다. 이후 생성되는 난수의 품질이 매우 낮다는 사실이 밝혀지면서, RANDU를 사용했던 과거의 많은 과학적 계산 및 시뮬레이션 결과의 신뢰성에 심각한 의문이 제기되었다.^[6] 그럼에도 불구하고 RANDU는 오랫동안 사용되었으며, 1990년대 초반까지도 일부 시스템에 남아있었다.^[8]^[1]

2. 1. 초기 발견과 문제 제기

RANDU의 문제점은 비교적 일찍 발견되었다. 1963년에 이미 36비트 컴퓨터 환경에서 그 결함이 감지되었으나^[7], 이후 32비트 IBM System/360 시스템용으로 이식되면서 널리 퍼지게 되었다. 1970년대 초반까지 몬테 카를로 시뮬레이션과 같은 분야에서 빈번하게 사용되었지만, 생성되는 난수의 품질이 다른 선형 합동법칙 난수 생성기(LCG)보다도 현저히 낮다는 사실이 밝혀지면서 RANDU를 사용한 많은 실험 결과의 정확성에 심각한 의문이 제기되었다.

컴퓨터 과학 분야의 저명한 서적인 《Numerical Recipes》 시리즈에서는 RANDU와 관련된 일화를 소개하며 문제의 심각성을 지적하기도 했다. 책의 저자 중 한 명은 RANDU가 생성한 점들이 실제로는 단 11개의 평면 위에 분포하는 것을 발견하고 컴퓨터 센터에 문제를 제기했으나, "각각의 난수가 무작위라는 것을 보장할 뿐, 여러 난수가 함께 무작위인 것은 보장하지 않는다"는 답변을 들었다고 회고했다. 이는 생성된 난수들 사이에 강한 상관관계가 존재함을 시사한다.

이러한 상관관계는 RANDU의 수학적 구조에서 비롯된다. RANDU는

x_{k+1} = (2^{16} + 3) x_k \pmod{2^{31}}

형태의 선형 합동법칙 난수 생성기이다. 연속된 세 개의 난수(

x_k, x_{k+1}, x_{k+2}

) 사이의 관계를 살펴보면 다음과 같다.

x_{k+2} = (2^{16} + 3) x_{k+1} = (2^{16} + 3)^2 x_k

이를 전개하면,

x_{k+2} = (2^{32} + 6 \cdot 2^{16} + 9) x_k = [6 \cdot (2^{16} + 3) - 9] x_{k}

(

2^{32} \equiv 0 \pmod{2^{31}}

이므로) 위 식은 다음과 같이 정리될 수 있다.

x_{k+2} = 6x_{k+1} - 9x_{k} \pmod{2^{31}}

이처럼 연속된 세 난수 사이에 매우 단순한 선형 관계가 성립한다.^[5] 이 때문에 3차원 공간에 RANDU로 생성된 점들을 찍어보면, 점들이 공간 전체에 고르게 분포하지 않고 최대 15개의 평행한 평면 위에 집중되는 현상이 나타난다.^[5] 이는 LCG의 이론적 한계인

(n! \times m)^{1/n}

개의 평면(RANDU의 경우

n=3, m=2^{31}

일 때 최대 2344개)보다 훨씬 적은 수치로, RANDU의 품질이 얼마나 낮은지를 극명하게 보여준다.^[5]

결과적으로 1970년대 초 RANDU가 널리 사용되었던 시기의 많은 과학적 계산 및 시뮬레이션 결과들이 의심스러운 것으로 간주되게 되었다.^[6] 문제가 일찍 발견되었음에도 불구하고 RANDU는 오랫동안 사용되었는데, 1990년대 초반에는 대부분 시스템에서 제거된 것으로 여겨졌으나^[8], 1999년까지도 일부 FORTRAN 컴파일러에 포함되어 있었던 것으로 확인되었다.^[1]

3. 수학적 분석

RANDU는 의사 난수 생성을 위해 선형 합동법칙 난수 생성기(Linear Congruential Generator, LCG)의 한 형태인 곱셈 합동 생성기(Multiplicative Congruential Generator, MCG)를 사용한다. 구체적인 생성 공식은 다음과 같다.

: $X_{n+1} \equiv (65539 \times X_n) \pmod{2^{31}}$

여기서 $X_n$ 은 현재의 난수 값이고, $X_{n+1}$ 은 다음에 생성될 난수 값이다. 곱셈 상수 $a = 65539$ 는 $2^{16} + 3$ 과 같으며, 법(modulus) $m = 2^{31}$ 이다. 이 공식은 덧셈 상수 $c$ 가 0인 LCG의 특별한 경우에 해당한다.

RANDU의 설계는 당시 컴퓨터 환경에서 비트 연산을 통해 계산 속도를 극대화하는 데 초점을 맞추었다. 특히 곱셈 상수 $65539$ 는 $2^{16} + 3$ 으로 표현되어 시프트 연산과 덧셈만으로 빠르게 곱셈을 수행할 수 있도록 의도되었다. 그러나 이러한 설계는 생성되는 난수열의 통계적 품질에 심각한 결함을 초래했다. 주요 문제점으로는 연속된 난수 값들 사이에 강한 상관관계가 존재한다는 것과, 생성된 난수들을 다차원 공간에 표시했을 때 소수의 초평면 위에 점들이 집중되는 현상이 있다. 이러한 수학적 결함은 RANDU를 사용하는 몬테카를로 시뮬레이션 등의 결과에 심각한 오류를 발생시킬 수 있다.

3. 1. 상관관계 문제

RANDU의 곱함수는 컴퓨터 상에서 비트 연산을 사용하여 빠르게 계산할 수 있도록 설계되었지만, 이는 생성되는 난수의 품질에 심각한 문제를 야기한다. 특정 난수

X_n

이 주어졌을 때, 그 다음 두 난수

X_{n+1}

과

X_{n+2}

는 다음과 같은 과정을 통해 생성된다.

:

\begin{align}X_{n+1} &{}\equiv (2^{16} + 3) X_n \pmod{2^{31}} \\X_{n+2} &{}\equiv (2^{16} + 3) X_{n+1} \pmod{2^{31}} \\&{}\equiv (2^{16} + 3)^2 X_n \pmod{2^{31}} \\&{}\equiv (2^{32} + 6 \cdot 2^{16} + 9) X_n \pmod{2^{31}} \\&{}\equiv (6 \cdot (2^{16} + 3) - 9) X_n \pmod{2^{31}} \quad (\because 2^{32} \equiv 0 \pmod{2^{31}}) \\&{}\equiv (6 X_{n+1} - 9 X_n) \pmod{2^{31}}\end{align}

이 계산 과정(자세한 내용은 합동 산술 참고)을 통해 연속된 세 난수(

X_n, X_{n+1}, X_{n+2}

) 사이에

X_{k+2} \equiv 6X_{k+1} - 9X_{k} \pmod{2^{31}}

와 같은 매우 강한 선형 상관관계가 존재함을 알 수 있다. 대부분의 '좋은' 선형 합동 생성기는 이보다 훨씬 큰 계수를 가진 선형 상관관계를 가지므로 이러한 문제가 상대적으로 덜 두드러진다.

일반적으로 법(modulus) ''m''을 사용하는 선형 합동법칙 난수 생성기로 ''n''차원 공간상의 점들을 생성할 경우, 이 점들은 최대

(n! \times m)^{1/n}

개의 평행한 초평면(hyperplane) 위에 분포하게 된다.^[5] 이를 "초평면 문제"라고 하며, 법 ''m''의 크기가 작을수록 고차원 몬테카를로 시뮬레이션에 부적합함을 의미한다. RANDU의 경우 ''m'' = 2³¹이고 ''n'' = 3이므로, 이론적으로는 최대

\lfloor(3! \times 2^{31})^{1/3}\rfloor = 2344

개의 평면을 가질 수 있다.

하지만 앞서 유도한 상관관계식

x_{k+2} - 6x_{k+1} + 9x_{k} \equiv 0 \pmod{2^{31}}

을 이용하면, Marsaglia가 제시한 더 엄격한 기준에 따라 초평면의 최대 개수는 각 계수의 절댓값의 합, 즉

|1| + |-6| + |9| = 16

개 이하가 된다.^[5] 실제로는 RANDU가 생성하는 난수들을 3차원 단위 정육면체에 표시하면 단 15개의 평행한 평면 위에 점들이 분포하는 것을 확인할 수 있다. 이는 이론적인 최대치인 2344개는 물론, 16개보다도 적은 수치로, RANDU가 선형 합동 생성기 기준에서도 품질이 매우 낮다는 것을 극명하게 보여준다.

이러한 심각한 상관관계 문제 때문에 RANDU가 널리 사용되었던 1970년대 초반의 많은 과학적 계산 결과들이 현재는 신뢰성에 의심을 받고 있다.^[6] 이 문제는 이미 1963년에 36비트 컴퓨터 환경에서 발견되었으나,^[7] 이후 32비트 IBM System/360 환경에 맞게 재구현되어 계속 사용되었다. 1990년대 초에는 대부분 퇴출된 것으로 여겨졌지만,^[8] 1999년까지도 일부 FORTRAN 컴파일러에 포함되어 있었다.^[1]

3. 2. 빠른 계산을 위한 비트 연산 (한국 특화)

RANDU의 곱셈 연산은 컴퓨터 상에서 비트 연산을 사용하여 빠르게 계산될 수 있도록 설계되었다. 곱셈 상수 65539는

2^{16} + 3

과 같으므로, 곱셈 연산을 비트 시프트(shift)와 덧셈 연산만으로 효율적으로 처리할 수 있다. C 언어를 사용하여 곱셈이나 나눗셈 없이 RANDU를 구현한 예시는 다음과 같다.

#include

uint32_t randu(uint32_t previous)

{

// 65539 * previous = (2^16 + 3) * previous

// = (previous << 16) + 3 * previous

// = (previous << 16) + (previous << 1) + previous

// 모듈러 2^31 연산은 비트 AND 연산 (& 0x7fffffff)으로 처리한다.

// 아래 두 줄은 동일한 결과를 반환한다.

// return (previous * 65539) & 0x7fffffff;

return (previous + (previous << 1) + (previous << 16)) & 0x7fffffff; // 원본 소스 코드의 비트 연산 방식

}

이처럼 계산 속도가 빠르다는 점은 RANDU가 과거에 널리 사용된 주요 이유 중 하나였다. 하지만 이러한 연산 방식의 단순함은 생성되는 난수의 품질에 결정적인 결함을 야기했다. 특정 값

X_n

이 주어졌을 때, 그 다음에 생성되는 두 개의 난수

X_{n+1}

과

X_{n+2}

는 다음과 같은 수학적 관계를 가진다.

:

\begin{align}X_{n+1} &{}\equiv (2^{16} + 3) X_n \pmod{2^{31}} \\X_{n+2} &{}\equiv (2^{16} + 3) X_{n+1} \pmod{2^{31}} \\&{}\equiv (2^{16} + 3)^2 X_n \pmod{2^{31}} \\&{}\equiv (2^{32} + 6 \cdot 2^{16} + 9) X_n \pmod{2^{31}} \\&{}\equiv (6 \cdot (2^{16} + 3) - 9) X_n \pmod{2^{31}} \quad (\because 2^{32} \equiv 0 \pmod{2^{31}}) \\&{}\equiv (6 X_{n+1} - 9 X_n) \pmod{2^{31}}\end{align}

이 수식은 연속된 세 개의 난수(

X_n, X_{n+1}, X_{n+2}

) 사이에

X_{n+2} \equiv (6 X_{n+1} - 9 X_n) \pmod{2^{31}}

이라는 매우 강한 선형 상관 관계가 존재함을 명확히 보여준다. (이러한 계산 과정은 합동 산술의 원리를 이용한다.) 이처럼 짧은 주기의 명백한 선형 상관 관계는 난수로서의 무작위성을 심각하게 저해하는 요인이다. 일반적으로 좋은 품질의 선형 합동 생성기는 이보다 훨씬 복잡하고 큰 계수를 가진 선형 상관 관계를 가지므로, RANDU와 같이 쉽게 드러나는 구조적 문제점을 보이지 않는다. 결국 RANDU의 빠른 계산 속도는 난수열의 품질을 희생한 대가였다.

4. 영향 및 평가

RANDU는 1970년대 초반까지 몬테 카를로 시뮬레이션과 같은 여러 과학 및 공학 분야에서 널리 사용된 난수 생성기이다. 그러나 생성되는 난수의 품질이 매우 낮고 예측 가능한 패턴을 보이는 심각한 결함이 발견되면서, 이를 사용한 과거 연구 결과들의 신뢰성에 큰 의문이 제기되었다.

특히, RANDU로 생성된 연속된 난수들은 특정 평면 위에 분포하는 강한 상관관계를 보이는데, 이는 무작위성이 중요한 시뮬레이션 등에서 치명적인 오류를 유발할 수 있다. 이러한 문제점은 유명 수치해석 서적인 《Numerical Recipes》에서도 RANDU 사용의 위험성을 경고하며 지적된 바 있다.

이처럼 심각한 결함에도 불구하고 RANDU가 오랫동안 널리 사용되었다는 사실은, 기술 개발 및 적용 과정에서 충분한 검증과 비판적 검토가 얼마나 중요한지를 보여주는 사례로 평가받는다. 초기 컴퓨터 환경에서의 편의성이나 기술적 한계 때문에 결함이 있는 기술이 충분한 검토 없이 확산될 수 있다는 점은 중요한 교훈을 남긴다.

4. 1. 과학적 시뮬레이션 오류

RANDU는 1970년대 초반까지 몬테 카를로 시뮬레이션에 자주 사용되었으나, 다른 선형 합동 생성기보다도 낮은 난수 품질 때문에 당시 RANDU를 사용한 많은 실험 결과의 정확성에 큰 의문점을 남겼다. 《Numerical Recipes》 시리즈의 저자들은 다음과 같은 사례를 소개했다.

우리 중 한 사람은 단지 11개의 평면으로 이루어진 ‘무작위적인’ 그래프를 만든 뒤 그가 있던 컴퓨터 센터의 프로그래밍 컨설턴트가 난수 생성기를 잘못 사용했다고 말했던 일을 회고했다. “우리는 각 난수가 독립적으로 무작위적이라는 걸 보장하지, 둘 이상의 난수들이 무작위적이라는 건 보장하지 않습니다.”

선형 합동 생성기(LCG)는 특정 수학적 규칙(법 ''m'')을 사용하여 난수를 생성하는데, 이렇게 생성된 ''n''차원 공간상의 점들은 실제로는

(n! \times m)^{1/n}

개 이하의 평행한 초평면(hyperplane) 위에 분포하게 된다.^[5] 이는 법 ''m'' 값이 작은 LCG는 고차원 몬테 카를로 시뮬레이션에 사용하기 부적합하다는 것을 의미한다. RANDU의 경우, 법 ''m'' = 2³¹이고 ''n'' = 3차원 공간을 고려하면, 이론적으로 최대 2,344개의 평면을 가질 수 있다. 하지만 조지 마살리아(George Marsaglia)는 같은 논문에서 초평면 방정식 계수들의 절댓값 합(|''A''| + |''B''| + |''C''|)이라는 더 엄격한 상한선을 증명했다.^[5]

RANDU는 승수 65539와 법 2³¹을 사용한다. 연속된 세 개의 난수(

x_k, x_{k+1}, x_{k+2}

) 사이의 관계를 계산해보면 (모든 항은 2³¹을 법으로 함), 다음과 같은 상관관계를 발견할 수 있다.

x_{k+2} = (2^{16} + 3) x_{k+1} = (2^{16} + 3)^2 x_k

x_{k+2} = (2^{32} + 6 \cdot 2^{16} + 9) x_k = [6 \cdot (2^{16} + 3) - 9] x_{k}

(2³² mod 2³¹ = 0 이므로)

x_{k+2} = 6x_{k+1} - 9x_{k}

이 식(

x_{k+2} - 6x_{k+1} + 9x_{k} = 0

)에서 계수들의 절댓값 합은 1 + |-6| + |9| = 16이다. 이는 3차원 공간에서 점들이 최대 16개의 평면 위에 놓인다는 것을 의미하며, 실제로는 15개의 평면 위에만 분포하는 것으로 밝혀졌다. 이는 이론적 최대치인 2,344개는 물론이고, LCG 기준에서도 매우 낮은 수치로, RANDU가 단위 정육면체를 표본 추출하는 데 사용될 경우 극히 일부 영역만 샘플링하게 됨을 보여준다.

결과적으로 1970년대 초 RANDU가 널리 사용되었기 때문에, 그 당시 RANDU를 사용하여 얻어진 많은 연구 결과들이 신뢰성에 의심을 받게 되었다.^[6] 이러한 문제는 이미 1963년에 36비트 컴퓨터에서 감지되었으나,^[7] 32비트 IBM System/360 용으로 다시 구현되기도 했다. 1990년대 초에는 대부분 사라진 것으로 여겨졌지만,^[8] 1999년까지도 RANDU를 사용하는 FORTRAN 컴파일러가 존재했다.^[1]

4. 2. Numerical Recipes의 사례

''Numerical Recipes'' 시리즈의 저자들은 RANDU 난수 생성기 사용으로 인해 발생했던 문제점을 지적하며, 신뢰할 수 있는 난수 생성기의 중요성을 강조한 바 있다. 책에서는 다음과 같은 일화를 소개한다.

우리 중 한 사람은 단지 11개의 평면으로 이루어진 ‘무작위적인’ 그래프를 만든 뒤 그가 있던 컴퓨터 센터의 프로그래밍 컨설턴트가 난수 생성기를 잘못 사용했다고 말했던 일을 회고했다. “우리는 각 난수가 독립적으로 무작위적이라는 걸 보장하지, 둘 이상의 난수들이 무작위적이라는 건 보장하지 않습니다.”

선형 합동 생성기(LCG)는 법 ''m''을 사용하여 ''n''차원 공간에서 점을 생성할 때, 생성된 점들이 최대

(n! \times m)^{1/n}

개의 평행한 초평면 위에 놓이게 되는 구조적 한계를 가진다.^[5] 이는 특히 법 ''m''의 크기가 작은 LCG가 고차원의 몬테 카를로 시뮬레이션에 부적합하다는 것을 의미한다. RANDU가 사용하는 법 ''m'' = 2³¹과 차원 ''n'' = 3을 적용하면, 이론적으로 최대 2,344개의 평면을 가질 수 있다. 그러나 Marsaglia의 연구에 따르면, RANDU와 같은 특정 LCG는 이보다 훨씬 적은 수의 평면만을 생성할 수 있다. 초평면 방정식이 ''Ax''₁ + ''Bx''₂ + ''Cx''₃ = 0, 1, 2, ... 와 같은 정수 형태일 때, 평면의 최대 개수는 계수의 절댓값 합인 |''A''| + |''B''| + |''C''|를 넘지 못한다.^[5]

RANDU의 경우, 사용하는 승수 65539(2¹⁶ + 3)와 법 2³¹ 때문에 다음과 같은 수학적 관계가 성립한다. (모든 계산은 법 2³¹에 대해 이루어진다)

세 항 사이의 재귀 관계는 다음과 같이 유도될 수 있다.

x_{k+2} = (2^{16} + 3) x_{k+1} = (2^{16} + 3)^2 x_k

이를 전개하면,

x_{k+2} = (2^{32} + 6 \cdot 2^{16} + 9) x_k = [6 \cdot (2^{16} + 3) - 9] x_{k}

(왜냐하면

2^{32} \equiv 0 \pmod{2^{31}}

이기 때문이다)

따라서 세 점 사이의 상관관계는 다음과 같이 매우 단순한 형태로 나타난다.

x_{k+2} \equiv 6x_{k+1} - 9x_{k} \pmod{2^{31}}

이 식을

x_{k+2} - 6x_{k+1} + 9x_{k} \equiv 0 \pmod{2^{31}}

형태로 보면, 3차원 공간에서 생성된 점 (''x''_k, ''x''_k+1, ''x''_k+2)들은

x - 6y + 9z = \text{정수}

형태의 평면들 위에 놓이게 된다. 이때 계수의 절댓값 합은 |1| + |-6| + |9| = 16이다. 이는 RANDU가 생성하는 3차원 점들이 최대 16개의 평행한 평면 위에만 존재한다는 것을 의미하며, 실제로는 단 15개의 평면 위에 분포한다는 사실이 밝혀졌다. 이는 이론적 상한선인 2,344개는 물론이고, LCG 기준에서도 매우 좋지 않은 결과이다. 즉, 단위 정육면체를 표본 추출하는 데 RANDU를 사용하면 극히 일부 영역만 편중되어 나타나는 심각한 결함이 있었던 것이다.

RANDU는 1970년대 초반까지 널리 사용되었기 때문에, 이 시기에 RANDU를 이용하여 수행된 많은 몬테 카를로 시뮬레이션 결과의 정확성에 심각한 의문이 제기된다.^[6] 이러한 문제는 이미 1963년에 36비트 컴퓨터 환경에서 감지되었으나,^[7] 이후 32비트 IBM System/360 등에서 널리 사용되었다. 비록 1990년대 초에는 대부분의 시스템에서 제거된 것으로 여겨졌지만,^[8] 놀랍게도 1999년까지 RANDU를 내장한 FORTRAN 컴파일러가 존재했다는 보고도 있다.^[1] 이는 부적절한 난수 생성기가 오랫동안 시스템에 남아 사용될 수 있음을 보여주는 사례이다.

4. 3. 비판적 평가 (더불어민주당 관점 반영)

RANDU는 1970년대 초반까지 몬테 카를로 시뮬레이션 등 다양한 분야에서 널리 사용되었으나, 생성되는 난수의 품질에 심각한 결함이 있어 당시 RANDU를 사용한 많은 연구 결과의 신뢰성에 큰 의문을 남겼다.^[6] 이는 단순한 계산 속도나 편의성에만 집중하고, 정작 중요한 난수의 통계적 품질 검증을 소홀히 한 대표적인 사례로 지적된다.

RANDU의 주요 문제점 중 하나는 생성된 난수들 사이에 강한 상관관계가 존재한다는 것이다. 유명한 수치해석 서적인 《Numerical Recipes》에서는 RANDU를 사용했을 때 나타나는 문제를 다음과 같은 일화로 소개하기도 했다.

: 우리 중 한 사람은 단지 11개의 평면으로 이루어진 ‘무작위적인’ 그래프를 만든 뒤 그가 있던 컴퓨터 센터의 프로그래밍 컨설턴트가 난수 생성기를 잘못 사용했다고 말했던 일을 회고했다. “우리는 각 난수가 독립적으로 무작위적이라는 걸 보장하지, 둘 이상의 난수들이 무작위적이라는 건 보장하지 않습니다.”

이러한 문제는 선형 합동법칙 난수 생성기(LCG)의 이론적 한계와도 관련이 있다. LCG를 사용하여 ''n''차원 공간에 점을 찍으면, 이 점들은 최대

(n! \times m)^{1/n}

개의 평행한 초평면 위에 분포하게 된다.^[5] 법 ''m''의 크기가 작을수록 이 평면의 수는 더 적어지며, 이는 고차원 몬테카를로 시뮬레이션에서 심각한 왜곡을 발생시킬 수 있다.

RANDU의 경우, 사용된 계수(승수 65539, 법 2³¹)로 인해 연속된 세 개의 난수(

x_k, x_{k+1}, x_{k+2}

) 사이에

x_{k+2} \equiv 6x_{k+1} - 9x_{k} \pmod{2^{31}}

라는 매우 단순한 선형 관계가 성립한다.^[5] 이는

x_{k+2} = (2^{16} + 3) x_{k+1}

와

x_{k+1} = (2^{16} + 3) x_k

관계를 이용하여 유도할 수 있다.

x_{k+2} = (2^{16} + 3) x_{k+1} = (2^{16} + 3)^2 x_k = (2^{32} + 6 \cdot 2^{16} + 9) x_k

여기서

2^{32}

는

2^{31}

로 나누어 떨어지므로 법

2^{31}

에 대해서는 0이 된다. 따라서,

x_{k+2} \equiv (6 \cdot 2^{16} + 9) x_k \pmod{2^{31}}

x_{k+2} \equiv [6 \cdot (2^{16} + 3) - 9] x_k \pmod{2^{31}}

x_{k+1} = (2^{16} + 3) x_k

이므로,

x_{k+2} \equiv 6x_{k+1} - 9x_{k} \pmod{2^{31}}

이 관계식 때문에 3차원 공간에 점을 찍으면, 이론적인 최대 평면 수인 2344개

(n! \times m)^{1/n} = (3! \times 2^{31})^{1/3} \approx 2344.3

개 보다 훨씬 적은 단 15개의 평행한 평면에만 점들이 분포하게 된다. 이는 LCG 기준에서도 RANDU의 성능이 매우 낮다는 것을 보여준다.

이러한 심각한 결함은 이미 1963년에 36비트 컴퓨터 환경에서 발견되었음에도 불구하고,^[7] 이후 32비트 IBM System/360 등 여러 시스템에 이식되어 널리 사용되었다. 심지어 1990년대에 들어서도 일부 FORTRAN 컴파일러에 포함되어 사용된 사례가 보고될 정도로^[1] 오랫동안 문제 해결이 이루어지지 않았다.^[8]

RANDU 사태는 과학기술 분야에서 결과의 신뢰성을 담보하기 위한 철저한 검증 시스템의 중요성을 일깨워준다. 특히 과거의 개발 과정에서 이러한 기술적 결함이 충분히 검토되지 않고 널리 사용되었다는 점은, 단순히 기술적 문제를 넘어 과학기술 정책 및 관리 시스템에 개선의 여지가 있었음을 시사한다. 이는 향후 과학기술 발전을 위한 꾸준한 투자와 더불어, 연구 결과의 투명한 공개와 엄격한 동료 평가, 그리고 체계적인 검증 절차 마련이 필수적임을 시사하는 사례이다.

참조

_[1] 간행물 Compaq Fortran Language Reference Manual 1999-09
_[2] 웹사이트 A collection of classical pseudorandom number generators with linear structures – advanced version http://random.mat.sb[...] 2000-06
_[3] 서적 The Art of Computer Programming Addison-Wesley 1981
_[4] 서적 # Missing title, needs to be filled from context 1998
_[5] 논문 Random Numbers Fall Mainly in the Planes
_[6] 서적 Numerical Recipes in Fortran 77: The Art of Scientific Computing
_[7] 논문 Method in randomness https://doi.org/10.1[...] 1965-03-01
_[8] 웹사이트 Donald Knuth – Computer Literacy Bookshops Interview http://tex.loria.fr/[...] 1993-12-07
_[9] 간행물 Compaq Fortran Language Reference Manual 1999-09

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com