[Python] 유사난수생성기 LCG(Linear Congruential Generator) 알고리즘

 

LCG의 존재는, random 모듈을 사용하지 않고 리스트 요소들을 shuffle 해야하는 파이썬 과제를 하다가 알게되었다.

-과제의 출처는 42AI bootcamp python-

 

Linear Congruential Generator(LCG)는 다음의 점화식을 따라 난수가 생성되는 알고리즘이다. 

 

$ X_{n+1} = (aX_{n}+c) \mod n $

 

변수 a, c, m, 그리고 Xn 값이 난수의 주기에 큰 영향을 미친다. 

• 0 ＜ a < m
• 0 ≤ c < m
• 0 < m
• $X_{n}$ = seed (시작값)

이 난수 생성기는 최대값이 m인 난수를 발생시킨다.

또한, 변수에 의해 난수가 결정되기 때문에, 변수를 알면 난수를 예상할 수 있다. 그러니까 Pseudo 난수 생성기인것이다. 그다지 좋은 알고리즘이라고는 할 수 없다. 하지만, 최대한 주기가 큰 난수를 만들 수 있는 변수의 조건들을 똑똑한 수학자들이 찾아놨다.

[최대 주기를 갖는 변수 조합의 필요충분조건]

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

wikipedia lcg 문서에 있는 sample 코드(python)

def lcg(modulus, a, c, seed):
    """Linear congruential generator."""
    while True:
        seed = (a * seed + c) % modulus
        yield seed

 

---

 

이 알고리즘을 이용해 내가 해결해야할 문제는, "random 모듈을 쓰지 않고 list shuffle 하기"였다.

lcg 알고리즘으로, list의 길이 만큼만 난수를 생성하고, 생성된 난수의 index와 현재 위치의 index의 자리를 바꿔주었다.

 

generator 함수는 매개변수로 text를 입력받아 list로 변환하고, lcg함수를 호출해 list를 shuffle 해준다.

 

def lcg(seed, loop, m=2**32, a=214013, c=2531011):
    """Linear congruential generator."""
    for i in range(loop):
        seed = (a * seed + c) % m
        yield seed


def generator(text):
    result = list()
    result = text.split(" ")
    
    for i, j in enumerate(lcg(len(result), len(result))):
    j %= len(result)
    result[i], result[j] = result[j], result[i]
    for i in result:
    	yield i

list에서 두 값의 위치를 간단하게 스위치하는 것은 stackoverflow에서 힌트를 얻었다.

result[i], result[j] = result[j], result[i]

파이썬은 너무 편하다...

 

# 다음과 같이 함수를 실행한다.

text = "Le Lorem Ipsum est simplement du faux texte."
for word in generator(text):
    print(word)

 

결과

Le Lorem Ipsum ~ 은 hello world 처럼 흔히 쓰이는 별 의미 없는 텍스트이다

 

사실 알고리즘보다 yield 쓰는게 더 어려웠다. lcg에서 yield를 통해 넘어온 i가 숫자인줄 알았는데 generator라는 객체여서 값을 가져오는데 애를 먹었기 때문이다.

 

참고

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