WELL512 랜덤 알고리즘의 랜덤성? 확인&비교

2014.12.21. 23:40

WELL512와 rand의 랜덤성을 해 보았습니다.

소스는 이렇습니다.

#include <stdio.h> #include <stdint.h> #include <time.h> uint32_t state[16]; uint32_t index = 0; #define TESTMAX 131072 uint32_t myrand() { uint32_t a, b, c, d; a = state[index]; c = state[(index+13)&15]; b = a^c^(a<<16)^(c<<15); c = state[(index+9)&15]; c ^= (c>>11); a = state[index] = b^c; d = a^((a<<5)&0xDA442D20UL); index = (index+15)&15; a = state[index]; state[index] = a^b^d^(a<<2)^(b<<18)^(c<<28); return state[index]; } int main() { int i, j, cnt; uint32_t seed; uint32_t vals[TESTMAX]; seed = time(NULL); printf("WELL512 Testing...\r\n"); { for(i=0; i<16; i++) { state[i] = seed+i; } for(i=0;i<TESTMAX;i++) { vals[i] = myrand(); } cnt = 0; for(i=0;i<TESTMAX;i++) { for(j=0;j<i;j++) { if(vals[i]==vals[j]) { printf("vals[%d] == vals[%d] = %u SAME\r\n", i, j, vals[i]); cnt++; } } } printf("Same : %d\r\n", cnt); } printf("rand Testing...\r\n"); { srand(seed); for(i=0;i<TESTMAX;i++) { vals[i] = rand(); } cnt = 0; for(i=0;i<TESTMAX;i++) { for(j=0;j<i;j++) { if(vals[i]==vals[j]) { printf("vals[%d] == vals[%d] = %u SAME\r\n", i, j, vals[i]); cnt++; } } } printf("Same : %d\r\n", cnt); } return 0; }

131072개의 랜덤한 수를 생성하고 그중에 중복되는 것들을 찾는 것이다.

우선 결과값...

WELL512 Testing...  vals[24420] == vals[20756] = 4037534957  vals[103568] == vals[90396] = 554428502  vals[121486] == vals[101993] = 4222066151

rand Testing...  vals[275] == vals[157] = 15143 SAME!!!!  vals[394] == vals[18] = 31020 SAME!!!!  vals[545] == vals[44] = 8844 SAME!!!!  vals[578] == vals[280] = 15915 SAME!!!!  vals[615] == vals[392] = 17895 SAME!!!!  vals[753] == vals[252] = 12064 SAME!!!!  vals[782] == vals[553] = 16153 SAME!!!!  vals[785] == vals[552] = 21462 SAME!!!!  vals[798] == vals[280] = 15915 SAME!!!!  vals[798] == vals[578] = 15915 SAME!!!!  vals[838] == vals[544] = 4251 SAME!!!!  vals[847] == vals[288] = 9481 SAME!!!!  vals[863] == vals[43] = 12759 SAME!!!!  vals[939] == vals[421] = 24623 SAME!!!!  vals[1009] == vals[488] = 20298 SAME!!!!  ... 너무 많아서...

결과적으로 WELL512는 131072개 중에 3개정도 (여러번 테스트 해보았는데 보통 2-3번 중복되었습니다.) 중복되고

rand는 262059개... (여러번 테스트시 평균 262337번 / 하나의 값에 여러개의 값이 중복되어서 이런 숫자가...ㄷㄷㄷ)

WELL512는 하나의 랜덤한 값에 하나의 같은 랜덤값이 나왔는데

rand는 많은 랜덤값을 생성할수록 하나의 랜덤값이(131070번째 랜덤값) 8개가 같은 값이 나오기도 하였다.

궁금해서 소스를 수정해서 알아봤더니...

하나의 같은 값이 131072번중에 13-14번 정도 나오기도 하였다.

쨋든... WELL512이 rand보다 좋은건 아주 많이 알려진 사실이다.

만약 이것보다 더 높은 랜덤율? 이 필요하다면 WELL1024같은것을 쓰는것도 좋을거 같다.

추가로...

WELL512 100000000번 랜덤발생시 1734ms

rand 100000000번 랜덤발생시 1875ms 의 속도가 걸리었다.

WELL512가 좀더 빠른데 거기거 거기인듯 하지만 WELL512가 워낙 더 좋은 랜덤값이 나온다.