====== LCG ======

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

<.center>$$x_{n+1} = (ax_n + b) \mod M$$</>

연속된 난수끼리 correlation이 꽤 있기 때문에 시뮬레이션 따위로 쓰기는 좀 그렇다. (요즘은 이 용도로 [[메르센트위스터]]를 많이 쓴다.) [[George Marsaglia]]에 따르면 이 알고리즘으로 $$n$$-tuple을 만들어서 $$n$$차원 초공간에 점을 찍으면 많아봐야 $$(n! M)^{1/n}$$개의 초평면에 위치한다. 그러나 1970년대 악명 높던 ''RANDU''((a=65539, b=0, M=2<sup>31</sup>. 주어진 M에 대하여 최대 가능한 초평면의 수는 대략 2천여개.))는 고작 15개의 평면에 속했다;

{{tag>전산학}}