진짜 랜덤한 난수를 생성하려면...?
Kidong Lee
안녕하세요.
rand() 함수를 쓰고 있는데, 실제로 여러번 계속 쓰게 되다보니,
그리 랜덤하게 나오지 않는다는 사실을 발견하였습니다.
관련된 코드만 간단히 뽑아봤습니다.
srand(time(NULL));
while() {
random_number = rand() % 8; /* 0부터 7까지의 수 */
srand(rand());
}
위와 상당히 많은 횟수의 rand()를 호출합니다.
좋은 알고리즘 있으면 좀 알려주시길 부탁드립니다.
--
Kidong Lee
Dept. of Computer Science & Engineering, ChungAng Univ.
E-mail: kid...@shinbiro.com
Korean Linux Document Project http://kldp.linux-kr.org
Ahn. Jin-su
Kidong Lee (kid...@opera.cse.cau.ac.kr) wrote:
: 안녕하세요.
: rand() 함수를 쓰고 있는데, 실제로 여러번 계속 쓰게 되다보니,
: 그리 랜덤하게 나오지 않는다는 사실을 발견하였습니다.
: 관련된 코드만 간단히 뽑아봤습니다.
것은 불가능하다..... 고 합니다.
: srand(time(NULL));
:
: while() {
: random_number = rand() % 8; /* 0부터 7까지의 수 */
: srand(rand());
: }
:
: 위와 상당히 많은 횟수의 rand()를 호출합니다.
:
자꾸 srand()를 하는 이유를 모르겠습니다. 처음 것은 이해가 가지만, 루프 안에서
자꾸 srand()를 하는 이유는 대체.....
Numerical Recipes in C에서 읽었던 것도 같은데, %연산을 써서 어떤 범위의
난수를 얻는 경우 randomness가 떨어진다는 말도 있었고..... -.-
솔라리스의 rand()매뉴얼에는 rand()함수는 randomness가 떨어진다는 말도 있고...
그리고, MT프로그램에서는 rand()가 비정상적으로 동작합니다....
(흐음 도움이 안될 것 같아..... -.-)
- 진수
-----
Ahn, Jin-su email: js...@ee.snu.ac.kr
School of Electrical Engineering
Seoul National University, Korea
Gyujin Han
Kidong Lee wrote:
>
> 안녕하세요.
안녕하세요. 컴싸를 전공하시나요? 혹시 교수님이시라면 제글이 강의조로
나가더라도 양해하시기 바랍니다.
> rand() 함수를 쓰고 있는데, 실제로 여러번 계속 쓰게 되다보니,
> 그리 랜덤하게 나오지 않는다는 사실을 발견하였습니다.
아주 훌류한 관찰을 하였읍니다. 이제 이 관찰된 내용을 이해하고 응용하는
과정이 남아있군요. 혹시 제가 도움이 될까 해서 이글을 씁니다.
rand() 함수는 진정한 의미의 난수발생기(random number generator)가
아닙니다. 난수 발생기라면 최소한 , pattern을 발견할 수 없고, 예측이
불가능하여야 하며, 골고루 분산되어야 합니다. 그러나 rand() 함수는 주어진
seed에 대해서 정해진 수열을 차례로 발생합니다. 자세한 것은 그 함수의
메뉴얼 페이지를 읽어보시면 아시겠고... 따라서 이를 pseudo-random
number라 부릅니다. 다음을 여러번 수행하여 그 결과를 비교해 보세요.
#include <stdlib.h>
#include <stdio.h>
int main(){int i;srand(0);for(i=0;i<100;i++)printf("%d\n",rand());}
그다음은 srand의 인수인 0을 다른 숫자로 바꾸어 여러번 수행해보고 0일
때의 결과와 비교해 보세요. 이제 rand()의 정체를 눈치채었으면 rand라는
이름이
(Rythmically Accumulated Numbers, which is essencially DETERMINISTIC)의
약자라고 외우세요. (필자주: rand가 원래 무엇의 약자인지는 필자는
모릅니다. 그냥 필자가 한번 만들어본 것입니다.
srand()의 s는 그러면 Series of 쯤 되나? 8^) rand()를 사용할 때 발생하는
문제들의 대부분은 rand를 random으로 읽는데서 부터 비롯됩니다.
> 관련된 코드만 간단히 뽑아봤습니다.
>
> srand(time(NULL));
>
> while() {
> random_number = rand() % 8; /* 0부터 7까지의 수 */
음... sizeof(int)*CHAR_BIT 개의 bit를 발생하여 그 중에 3개 (가장
오른쪽의 3개의 bit) 만을 사용하시는군요. 가장 간단하게 생각해 낼 수 있는
초식이죠.
그러나 여기에서 문제가 되는 것은 일부 컴파일러가 제공하는 rand() 함수는
끝의 몇자리의 비트가 특히 덜 random하다라는 사실입니다. 패턴이
발견된다는 이야기지요. 심지어는 제일 끝 비트가 (rand()%2의 결과가)
0,1,0,1,0,1... 로 계속 oscillate하는 그런 rand () 함수가 들어있는
시스템도 있다는 사실입니다. 따라서 32개의 비트 (앗 죄송, 저와다른
시스템을 사용하시는 분들을 위해 정정합니다. sizeof(int)*CHAR_BIT 개의
비트) 모두를 사용하여 연산하는 것이, 보다 나은 질의 결과를 얻어낼 수
있겠지요. 예를들면;
(int)((double)rand() / ((double)RAND_MAX + 1) * N)
이라던지, 실수연산하는 것이 마음에 들지 않으면;
rand() / (RAND_MAX / N + 1)
라던지...
단 두번째 방법은 (RAND_MAX % N)' 보다 큰 수와 작거나 같은 수가 나올
각각의 확률이 1/(RAND_MAX/N)' 만큼 차이가 나므로 N이 RAND_MAX에 비해
현저히 작을 경우가 아니면 좋은 결과를 기대할 수 없겠죠. (여기에서 X'은
X-1, X, X+1 중의 하나인데 자세히 따지기 귀찮은 관계로 그렇게
표시하였으니 이해하시기 바랍니다. ;-) 당신이 좋은 컴파일러를 가지고
있다면 실행시 연산횟수는 rand()%8과 같을것입니다. 단지 % 연산과 / 연산의
차이가 있다면 있을뿐.... (단, #define N 8 일 경우)
> srand(rand());
메뉴얼 페이지를 잘 읽어보시면 아시겠지만, 한번 실행시에 srand가 두번이상
호출되는 것은 상황을 호전시키는데 거의 도움을 주지 못합니다. srand()의
인자가 예상할 수 없는 그야말로 random number라고 하면 다르겠지만, 이것은
순수한 착각입니다. (앞에서 rand를 random으로 읽지 말라는 말을 한 적이
있읍니다.) 처음에 srand에 의해 seed가 정해지면, 그 이후에 이루어지는
rand() 호출의 결과는 deterministic 하고, 또한 deterministic한 seed가
주어졌을 때, 그 이후의 상황은 계속 deterministic하다는 것이죠. 너무
어렵나요? 그러면 원래의 예제에서 처음의 srand 호출시 인수를 0으로
바꾸고, rand()의 결과를 출력하도록 고쳐서 여러번 실행해 보세요. 뒤에
있는 srand(rand())가 어떠한 도움이 되고 있읍니까?
> }
>
> 위와 상당히 많은 횟수의 rand()를 호출합니다.
>
> 좋은 알고리즘 있으면 좀 알려주시길 부탁드립니다.
소프트웨어적으로 진정한 난수발생기를 만드는 것은 불가능한 것으로 알려져
있읍니다. (불가능한 것이 수학적으로 증명된 것인지에 대해서는 저로서는
아는 바가 없읍니다.) 따라서 하드웨어적인 시도가 있는것으로 알고
있읍니다. 예를 들면 rand()의 deterministic한 성질을 보완하기 위해 단락된
마이크 단자에 잡히는 미세한 노이즈를 seed로 이용한다든지 하는것
말입니다. 하지만 위에서 언급한 몇개의 필수 성질을 모두 만족시키는 것은
쉬운 일이 아니죠.
난수의 분포성에 대해서는, 가령 정규분포를 갖는 난수발생기라든지...
균등분포성이 증명된 rand()와 같은 난수발생기를 바탕으로 알고리즘적으로
만들 수 있으니 알고리즘책을 잘 찾아보세요.
마지막으로 한마디만...
난수는 컴싸의 엄연한 한 분야로 자리잡고 있읍니다. 물론 게임제작 등에도
필수이지만 이를 바탕으로 암호학 (cryptography)등 발전분야가
무궁무진합니다. 열심히 공부합시다.
>
> --
> Kidong Lee
> Dept. of Computer Science & Engineering, ChungAng Univ.
> E-mail: kid...@shinbiro.com
> Korean Linux Document Project http://kldp.linux-kr.org
--
Gyujin Han gj...@samsung.co.kr UNITEL:은수아빠
박종대
Kidong Lee <kid...@opera.cse.cau.ac.kr> wrote:
: srand(time(NULL));
: while() {
: random_number = rand() % 8; /* 0부터 7까지의 수 */
: srand(rand());
: }
: 위와 상당히 많은 횟수의 rand()를 호출합니다.
: 좋은 알고리즘 있으면 좀 알려주시길 부탁드립니다.
어떤 환경인지를 적지 않았군요..
rand()는 상당히 나쁜 random 함수입니다.
더 좋은 함수로 많은 unix에서 lrand48(), random() 등이 제공됩니다.
(제공되지 않는 경우도 많습니다.)
실제 분석등을 위해서라면 수치해석 책등에 나오는 random 함수들을 구현해서
쓰는 건 어떨까요? 자신이 원하는 특성을 만족하는 random 함수를 만들 수
있을겁니다.
--
박종대
-- ' C-language Edition
#define cdpark /* KAIST, CSDept, Theory of Computation Lab. */
#include <signature.h> /* the Hitchhiker's Guide to the Internet?? */
bbug...@cns.snu.ac.kr
>>>>> "Kidong" == Kidong Lee <kid...@opera.cse.cau.ac.kr> writes:
Kidong> 안녕하세요. rand() 함수를 쓰고 있는데, 실제로 여러번 계속
Kidong> 쓰게 되다보니, 그리 랜덤하게 나오지 않는다는 사실을
Kidong> 발견하였습니다. 관련된 코드만 간단히 뽑아봤습니다.
Kidong> srand(time(NULL));
Kidong> while(){
Kidong> random_number = rand() % 8; /* 0부터 7까지의 수 */
Kidong> srand(rand());
Kidong> }
rand만을 쓴다면 맨날 같은 sequence로 나오게 됩니다.
#include <stdio.h>
#include <stdlib.h>
main()
{
while (1)
printf("%d\n", rand());
}
16838
5758
10113
17515
31051
5627
23010
7419
16212
4086
....
Solaris 2.5에서 돌렸더니 위와 같은 식으로 나오는 군요.
srand는 이러한 것을 보완하기 위해서 seed(salt?)를 주는 것입니다.
즉, 초기치를 주어서 첫번째 나오는 수를 바꾸어 주는 것입니다.
근데, 초기치를 매번 같이 두면 별 소용이 없기 때문에, 매번 다르게
주기 위해서 보통 time()을 씁니다. 그러나, 이것도 비슷한 시간에 여러개를
같이 돌리면 같은 sequence로 나오더군요. 그러니깐 cryptography에서
쓰기에는 적당하지 않습니다.
rand를 여러개 써서 만드는 것도 생각해 볼 수 있으나 역시 소용이 없습니다.
예를 들어
rand() + rand() * rand() * rand()
라고 한다고 해도 효과는 그냥 하나 쓰는 거나 마찬가지입니다.
random, srandom들도 마찬가지라고 생각합니다.(해보지는 않았지만)
rand보다는 좋겠죠.
제일 좋은 방법(?)은 사람에게 5살 난 조카보고 키보드를 마구 두드리라고
하는 방법이라고 생각합니다. 그걸로 seed를 삼으면 되겠지요.
ftp://sunsite.kren.nm.kr/pub/document/RFC/rfc1750.txt
를 참조하세요.
--
====================================================
* Dept. of Math and CSS, Seoul Nat'l Univ., Korea *
* <mailto:bbug...@shiva.snu.ac.kr> *
* TEL: 02-880-5374, Pager: 012-201-0322 *
====================================================
bbug...@cns.snu.ac.kr
>>>>> "bbugging" == bbugging <bbug...@cns.snu.ac.kr> writes:
>>>>> "Kidong" == Kidong Lee <kid...@opera.cse.cau.ac.kr> writes:
Kidong> 안녕하세요. rand() 함수를 쓰고 있는데, 실제로 여러번 계속
Kidong> 쓰게 되다보니, 그리 랜덤하게 나오지 않는다는 사실을
Kidong> 발견하였습니다. 관련된 코드만 간단히 뽑아봤습니다.
Kidong> srand(time(NULL));
Kidong> while(){
Kidong> random_number = rand() % 8; /* 0부터 7까지의 수 */
Kidong> srand(rand());
Kidong> }
하나 빼먹은 것이 있는데, 위 code에서 srand(rand())를 하는 것은
별 효과가 없습니다. 물론 없는 거랑 결과는 다르겠지만 randomness가
좋아지는 것은 아니죠. 어차피 나오는 모든 sequence는 srand(time(NULL))에
의존하게 되니까요. 그러니까 time(NULL)의 결과가 같은 모든 program에서
같은 결과가 나온다는 것입니다. 즉, 같은 시간에 여러개를 돌리면
같은 수들이 쏟아져 나오겠죠.
박종대
bbug...@cns.snu.ac.kr wrote:
: srand는 이러한 것을 보완하기 위해서 seed(salt?)를 주는 것입니다.
: 즉, 초기치를 주어서 첫번째 나오는 수를 바꾸어 주는 것입니다.
: 근데, 초기치를 매번 같이 두면 별 소용이 없기 때문에, 매번 다르게
: 주기 위해서 보통 time()을 씁니다. 그러나, 이것도 비슷한 시간에 여러개를
: 같이 돌리면 같은 sequence로 나오더군요. 그러니깐 cryptography에서
: 쓰기에는 적당하지 않습니다.
이걸 피하기 위한 테크닉은 srand(time() + getpid()) 입니다.
(물론 암호화에 쓰기엔 역시 부적절하지만..)
random seed를 기반으로 한 게임을 만들었더니... 누군가 동시에 두 프로그램을
띄워서 하나에서는 답을 보고 다른 하나에서 그냥 맞추더군요. -_-
위와 같은 방법으로 쉽게 퇴치(?)할 수 있었습니다.
Jimi Lee
컴퓨터가 외부의 아무런 인풋 없이 자체적으로 랜덤한 수를
만들어 낼 수는 없습니다. 랜덤도 일종의 펑션이고 인풋이
같다면 아웃풋도 같음은 어쩔 수 없는 걸요...
뭐.... 여자 한명을 키보드 앞에 앉혀 놓고 가끔 좋아하는 수를
입력하라 하면 될려나... (여자의 마음처럼 랜덤은 없다고 누가...)
참고로 머드 같은 게임에서는 주사위를 여러번 굴리는 식으로
랜덤함수를 씁니다. 가령 칼이 하나 있는데 이 칼의 데미지를
랜덤으로 정합니다. 단순히 랜덤함수만 이용하면
10~20사이의 수 하나를 출력하겠죠. 하지만 머드에서는
2면 10굴림 식의 용어를 씁니다. 2면 주사위를 10번 굴려 나온 수를
합한다는 의미입니다. 그러면 10~20 사이의 수가 나오겠지요.
13면 8굴림... 4면 7굴림... 식으로 사용합니다.
오히려 원래 램덤함수보다 덜 램덤할 수도 있지만 그냥 이런 방법도
있다고 알아두세요....
박종대
Jimi Lee <le...@daidun.kaist.ac.kr> wrote:
: 참고로 머드 같은 게임에서는 주사위를 여러번 굴리는 식으로
: 랜덤함수를 씁니다. 가령 칼이 하나 있는데 이 칼의 데미지를
: 랜덤으로 정합니다. 단순히 랜덤함수만 이용하면
: 10~20사이의 수 하나를 출력하겠죠. 하지만 머드에서는
: 2면 10굴림 식의 용어를 씁니다. 2면 주사위를 10번 굴려 나온 수를
: 합한다는 의미입니다. 그러면 10~20 사이의 수가 나오겠지요.
: 13면 8굴림... 4면 7굴림... 식으로 사용합니다.
: 오히려 원래 램덤함수보다 덜 램덤할 수도 있지만 그냥 이런 방법도
: 있다고 알아두세요....
덜 랜덤하기 때문이 아니라.. 다른 성질을 원하기 때문이죠..
2면 주사위를 10번 굴리면, 10이나 20도 나올 수 있지만, 15가 나올 확률이
가장 높습니다. 즉, 여지간하면 13~17이 나오는거죠..
(binomial distribution)
컴퓨터에서 제공하는 random 함수는 대개 0~1 또는 0-N 사이의 uniform 분포를
가지지만, 작은 조작을 통해 원하는 분포(정규분포, Poisson 분포, ...)로
바꿀 수 있습니다.
Artist
박종대 wrote:
> 컴퓨터에서 제공하는 random 함수는 대개 0~1 또는 0-N 사이의 uniform 분포를
> 가지지만, 작은 조작을 통해 원하는 분포(정규분포, Poisson 분포, ...)로
> 바꿀 수 있습니다.
작은 조작이라는게 뭔가요?
아시는 데도 소개좀 부탁 드립니다.
--
mailto:art...@soback.kornet.nm.kr
박종대
Artist <art...@soback.kornet.nm.kr> wrote:
: 박종대 wrote:
:> 컴퓨터에서 제공하는 random 함수는 대개 0~1 또는 0-N 사이의 uniform 분포를
:> 가지지만, 작은 조작을 통해 원하는 분포(정규분포, Poisson 분포, ...)로
:> 바꿀 수 있습니다.
: 작은 조작이라는게 뭔가요?
: 아시는 데도 소개좀 부탁 드립니다.
적당한 table을 쓰거나... 확률밀도함수의 역함수를 만들거나...
Jimi Lee
>> 컴퓨터에서 제공하는 random 함수는 대개 0~1 또는 0-N 사이의 uniform 분포를
>> 가지지만, 작은 조작을 통해 원하는 분포(정규분포, Poisson 분포, ...)로
>> 바꿀 수 있습니다.
>
>작은 조작이라는게 뭔가요?
>아시는 데도 소개좀 부탁 드립니다.
>
랜덤 펑션의 경우 a-b의 범위에서 n회 추첨시 각 수가
거의 비슷하게 나옵니다. 초보 도박사가 주사위를 던지듯
정말 무슨 수가 나올지 모릅니다. 하지만 약간 숙련을
한 도박사의 경우 대충 원하는 수가 나오게 던질 수 있게 됩니다.
하지만 도신의 경지에는 못올라 언제나 그러지는 못하죠.
이것이 변형된 랜덤 함수의 예중 하나입니다.
좀더 간단히 설명을 드리면 N회를 던지고 나서 그동안 나온 수들의
데이터를 조사해서 그래프로 그리면 원래 랜덤은 수평선이
나오지만 조작을 가해 정규뷴포 곡선이나 기타의 분포도를
보이도 할 수 있습니다. 가령 전에 전에 제가 올린 머드에서의
랜덤의 경우도 구간의 끝쪽 값 보다는 가운데 값이 자주 나오죠.
혹은 뭐.. a~b구간에서 b쪽으로 갈수록 확률을 높게 할 수도 있습니다.
또다른 것은 전에 나온 값에 영향을 받게 할 수도 있는데요...
직전에 나온 값을 정규 분포의 축으로 잡고 다시 랜덤을 돌려 다음수를
결정할 수도 있습니다. 근처의 숫자가 나오도록 유도하는 방법이죠.
자세한 것은 책을 보세요. 알고리즘 책중 알고리즘 보다는 이런
테크닉들을 다룬 책들에 랜덤도 나옵니다.
Ahn Changwon
터보씨를 쓰신다면 그럭저럭 쓸만한 방법이 있습니다. 다른 컴파일러에도 이
함수가 있는지는 모릅니다.
rand나 random 함수를 사용하는 함수 시작부분에서 randomize를 사용하는
방법입니다. seed를 예측할 수 없게 주자는건데, rand는 직접 seed를 주게
되어 있으니 이 방법은 별로.. 겠고, random 같이 seed를 직접 주지 않는
함수를 쓰실 때에는 간단하게 아무데서나 함수 사용 전에 randomize() 만
호출해 주시면 됩니다.
이것이 왜 그럭저럭 쓸만한고 하니, CPU clock tick 이란게 있습니다.
결국 시간인데, 현재 시각을 초 단위가 아닌 컴 내부에서 돌아가는 미세한
clock tick 단위로 체크하는거죠. 워낙 빨리 바뀌는 수이기 때문에,
호출하는 순간에 따라 어떤 값이 나올지 예측하기 어려울겁니다. 이걸
seed 비슷하게 사용하기 때문에, 실행할 때마다 다른 수가 나올겁니다.
물론 seed값을 주는 것이기 때문에, 랜덤 함수의 시드에 따른 난수 발생
테이블을 갖고 있는 사람이라면 분석해 낼 수도 있겠죠. randomize를 수시로
호출해 준다면, 이런것도 막을 수 있지 않을까 하네요. 이건 안해본겁니다.
할튼, 매우 중요한 사안에 쓸 게 아니라면 randomize로 웬만큼 커버가 될겁니다.
랜더마이즈 함수가 없는 컴파일러라면, 시스템 클럭 틱 값을 뽑아내는 clock
함수를 씨드로 쓰는것도 대안이 될 수 있겠죠. 하여튼, 컴퓨터상에서 정말 완벽한
난수를 발생할 수는없는 걸로 알고 있습니다.
참고로, 컴퓨터 알고리즘에서 나오는 난수는 유니폼 디스트리뷰트가 되지
않습니다. 직접 한 10만개 정도 뽑아서 그림으로 그려 보세요. 한쪽으로 기운
모양이 나올겁니다. 아래 어떤 분이 말씀하신 '적당한 조작'을 가하면 웬만큼
유니폼하게 나오죠.. 예전에 숙제로 짜 본 적이 있어서.. 약간 알고 있는 내용
중얼거려봤습니다.
-----------------------------------------------------------
pig...@nownuri.net , pig...@netsgo.com
http://myhome.netsgo.com/pighair
All right reserved. copyright ⓒ1994 pighair lab.
-----------------------------------------------------------