LCG

Linear Congruential Generator, 또는 선형 합동 생성기. 유사난수 알고리즘으로 씨수(seed) x_0에 대하여 다음 연산을 반복하여 얻어진다.

x_{n+1} = (ax_n + b) \mod M

연속된 난수끼리 correlation이 꽤 있기 때문에 시뮬레이션 따위로 쓰기는 좀 그렇다. (요즘은 이 용도로 메르센트위스터를 많이 쓴다.) George Marsaglia에 따르면 이 알고리즘으로 n-tuple을 만들어서 n차원 초공간에 점을 찍으면 많아봐야 (n! M)^{1/n}개의 초평면에 위치한다. 그러나 1970년대 악명 높던 RANDU1)는 고작 15개의 평면에 속했다;

1) a=65539, b=0, M=231. 주어진 M에 대하여 최대 가능한 초평면의 수는 대략 2천여개.

도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기