의사 난수 생성 - 2. LCG (Linear Congruential Generator)

선형 합동 생성기 라고 직역 할 수 있겠습니다.

C 언어의 rand() 함수 구현과 Java.util.Random에 사용되었습니다.

가장 잘 알려진 간단한 의사 난수 생성 방법 중의 하나로, 1958년에 만들어 졌으며 재귀적으로 아래와 같은 점화식으로 정의 됩니다.

출처: https://en.m.wikipedia.org/wiki/Linear_congruential_generator

    1) m > 0
    2) 0 < a < m
    3) 0 < c < m
    4) 0<= X0 < m (X의 초기값)

결과는 최대 m가지 경우가 있을 수 있겠습니다.

최대 주기를 가지기 위한 필요 충분 조건은

    1) c 와 m이 서로소여야 한다.
    2) a - 1이 m의 모든 소인수로 나누어져야 한다.
    3) m이 4의 배수일 경우, a - 1도 4의 배수여야 한다.

일반적으로 m이 2의 배수일 경우 결과의 하위 비트들은 상관 관계가 나타날수 있기 때문에

일반적으로 하위 비트를 버리고 상위 비트만 사용합니다.

1차원에서는 분포가 균일하지만 n차원에서는 균일하지 않고 패턴이 발생됩니다.

이를 작은 수로 시뮬레이션 해보면 아래와 같이 보일 수 있습니다.

출처: https://en.m.wikipedia.org/wiki/Linear_congruential_generator

아래와 같은 C 언어로 구현할 수 있습니다.

//ISO9899

#define MULTI    0x41C64E6D
#define INCR     0x3039

unsigned seed = 1;

int custom_rand(void)
{
	seed = seed * MULTI + INCR;
    	return (seed>>16) % 0x8000;
}

 

참고:

https://en.m.wikipedia.org/wiki/Linear_congruential_generator

Linear congruential generator - Wikipedia