Random 알고리즘

Algorism

http://www.gamedevforever.com/114

랜덤 알고리즘으로 2가지

MT 메르센 트위스터, Well 시리즈 (512, ...)

Well이 좋다.

rand() 함수의 분포는 그리 고르지 않다. 특히 작은 표본을 사용할때는 더욱 그렇다. 
즉, 이말은 1~10까지 랜덤을 1억번쯤 돌리면, 확률이 다들 비슷하게 나오긴 하지만, 10번 정도만 돌릴때에는 1 하나만 10번이 나온다거나 하는 가능성이 있다는 것입니다.
 

rand() 함수는 전역 함수이다. 어디서든 사용이 가능하다
이 함수는 표준 함수이기 때문에, 코드의 어디에서도 호출이 가능합니다. 그래서 호출 되는 경우를 제어할 수 가 없습니다.


이런 랜덤 생성기중에서 가장 유명하고 널리 쓰이는 알고리즘이 바로 [메르센 트위스터(MT.Mersenne Twister)]와 [WELL]이라는 랜덤 생성기입니다.

그리고 이 랜덤 생성기들은 위와 같은 테크닉에 사용할 수 있는 용도 외에도 다음과 같은 뛰어난 장점들을 가지고 있습니다

표준 함수보다 랜덤 분포가 훨씬 고르다
표준 함수의 경우 2^32승의 period를 가지는데 반해, MT의 경우는 2^19937-1를 가집니다. 그리고 623차원까지 동일분포 되어 있습니다. (자세한건 아래 링크 참조) 

표준 함수보다 훨씬 속도가 빠르다.
MT의 경우에 비트 연산만으로 구현되어 있어서, 표준 rand()보다 약 4배가 빠르다고 합니다. 그리고 WELL 같은 경우에는 MT보다 40%가 더 빠르다고 합니다.