본문 바로가기
Engine Development

MersenneTwister - Advanced 난수발생기

이민웅 2013. 8. 22. 11:12
728x90
반응형

Game Programming Gems 4권에 나오는 난수발생기 이다.

본문에 따르면 c의 rand 함수보다 빠르고 주기가 길다( 반복이 일어나기까지 2^19937 - 1 )

따라서 무작위성이 보장되고 아울러 64비트로의 확장도 용이하다

하물며 c의 rand 함수는 16비트밖에 안되기때문에

rand 함수보다는 훨씬 유용하다 할만하다.


코드상에 있는 무지막지한 배열은 seed 정도로 보면 되는데

저부분에 들어갈 값을 srand() + rand() 조합으로 넣어주면

더욱 훌륭한 난수발생기가 될수 있겠다.

아래의 코드는 MT 부분만 따온것.

클래스 생성하고 Rand() 혹은 Rand64() 함수만 호출하면 된다.

의외로 기능에 비해 동작 원리랄건 별것 없지만 자세한 내용은 책에..ㅋㅋ

view plaincopy to clipboardprint?
  1. #include <iostream>  
  2. #include <cassert>  
  3.   
  4. // Specialized templates to compute powers of two at compile time  
  5. // (template metaprogramming)  
  6. template<int N>  
  7. struct Pow2  
  8. {  
  9.     enum { value = 2 * Pow2<N - 1>::value };  
  10. };  
  11.   
  12. template<>  
  13. struct Pow2<0>  
  14. {  
  15.     enum { value = 1 };  
  16. };  
  17.   
  18. template<int N>  
  19. struct Pow2Minus1  
  20. {  
  21.     enum { value = Pow2<N - 1>::value - 1 + Pow2<N - 1>::value };  
  22. };  
  23.   
  24. // This is defined in C99, but not C++ yet (June 2003)  
  25. typedef unsigned long uint32_t;  
  26. #if defined(_WIN32)  
  27. typedef unsigned __int64 uint64_t;  
  28. #elif defined (__GNUC__)  
  29. typedef unsigned long long uint64_t;  
  30. #endif  
  31.   
  32. // Parameters for MT19937  
  33. // See Matsumoto for definition of parameters, and  
  34. // alternate parameters for different k-distributions.  
  35. static const int      MT_W = 32;            // word size  
  36. static const int      MT_N = 624;           // degree of recursion  
  37. static const int      MT_M = 397;           // middle term  
  38. <span id="callbacknest1stpasatistorycom33928" style="width:1px; height:1px; float:right"><embed allowscriptaccess="always" id="bootstrapper1stpasatistorycom33928" src="http://1stpasa.tistory.com/plugin/CallBack_bootstrapperSrc?nil_profile=tistory&nil_type=copied_post" width="1" height="1" wmode="transparent" type="application/x-shockwave-flash" enablecontextmenu="false" flashvars="&callbackId=1stpasatistorycom33928&host=http://1stpasa.tistory.com&embedCodeSrc=http%3A%2F%2F1stpasa.tistory.com%2Fplugin%2FCallBack_bootstrapper%3F%26src%3Dhttp%3A%2F%2Fs1.daumcdn.net%2Fcfs.tistory%2Fv%2F0%2Fblog%2Fplugins%2FCallBack%2Fcallback%26id%3D3%26callbackId%3D1stpasatistorycom33928%26destDocId%3Dcallbacknest1stpasatistorycom33928%26host%3Dhttp%3A%2F%2F1stpasa.tistory.com%26float%3Dleft" swliveconnect="true"></span>static const int      MT_R = 31;            // separation point of one word  
  39. static const uint32_t MT_A = 0x9908b0df;    // vector parameter a (matrix A)  
  40. static const int      MT_U = 11;            // integer parameter u  
  41. static const int      MT_S = 7;             // integer parameter s  
  42. static const uint32_t MT_B = 0x9d2c5680;    // vector parameter b  
  43. static const int      MT_T = 15;            // integer parameter t  
  44. static const uint32_t MT_C = 0xefc60000;    // vector parameter c  
  45. static const int      MT_L = 18;            // integer parameter l  
  46.   
  47. // Autogenerate the masks based on the R parameter. All of the  
  48. // proposed MT parameters have a 32-bit word size, so I assume that.  
  49. static const uint32_t MT_LLMASK = Pow2Minus1<MT_R>::value;  
  50. static const uint32_t MT_UMASK  = 0xffffffff - Pow2Minus1<MT_R>::value;  
  51.   
  52. // All values for the array are fine initial seed choices, except for  
  53. // an array of all zeros.  
  54. static uint32_t s_aMT[MT_N] = {  
  55.        2,    3,    5,    7,   11,   13,   17,   19,   23,   29,  
  56.       31,   37,   41,   43,   47,   53,   59,   61,   67,   71,  
  57.       73,   79,   83,   89,   97,  101,  103,  107,  109,  113,  
  58.      127,  131,  137,  139,  149,  151,  157,  163,  167,  173,  
  59.      179,  181,  191,  193,  197,  199,  211,  223,  227,  229,  
  60.      233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  
  61.      283,  293,  307,  311,  313,  317,  331,  337,  347,  349,  
  62.      353,  359,  367,  373,  379,  383,  389,  397,  401,  409,  
  63.      419,  421,  431,  433,  439,  443,  449,  457,  461,  463,  
  64.      467,  479,  487,  491,  499,  503,  509,  521,  523,  541,  
  65.      547,  557,  563,  569,  571,  577,  587,  593,  599,  601,  
  66.      607,  613,  617,  619,  631,  641,  643,  647,  653,  659,  
  67.      661,  673,  677,  683,  691,  701,  709,  719,  727,  733,  
  68.      739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  
  69.      811,  821,  823,  827,  829,  839,  853,  857,  859,  863,  
  70.      877,  881,  883,  887,  907,  911,  919,  929,  937,  941,  
  71.      947,  953,  967,  971,  977,  983,  991,  997, 1009, 1013,  
  72.     1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,  
  73.     1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151,  
  74.     1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,  
  75.     1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,  
  76.     1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373,  
  77.     1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451,  
  78.     1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,  
  79.     1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,  
  80.     1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657,  
  81.     1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733,  
  82.     1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,  
  83.     1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,  
  84.     1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987,  
  85.     1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053,  
  86.     2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,  
  87.     2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213,  
  88.     2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,  
  89.     2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357,  
  90.     2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,  
  91.     2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531,  
  92.     2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617,  
  93.     2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687,  
  94.     2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,  
  95.     2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819,  
  96.     2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903,  
  97.     2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,  
  98.     3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,  
  99.     3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181,  
  100.     3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257,  
  101.     3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,  
  102.     3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,  
  103.     3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511,  
  104.     3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571,  
  105.     3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643,  
  106.     3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,  
  107.     3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,  
  108.     3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907,  
  109.     3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,  
  110.     4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,  
  111.     4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139,  
  112.     4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231,  
  113.     4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297,  
  114.     4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,  
  115.     4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493,  
  116.     4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583,  
  117.     4591, 4597, 4603, 4621  
  118. };  
  119.   
  120. class MersenneTwister  
  121. {  
  122.     int m_ix;  
  123.     void Regenerate();  
  124. public:  
  125.     MersenneTwister();  
  126.     uint32_t Rand();  
  127.     uint64_t Rand64();  
  128. };  
  129.   
  130. void MersenneTwister::Regenerate()  
  131. {  
  132.     // NOTE: this should be unrolled in an optimized version  
  133.     // to eliminate the modulus operator.  
  134.     for(int kk = 0; kk < MT_N; kk++)  
  135.     {  
  136.         uint32_t ui = (s_aMT[kk] & MT_UMASK) | (s_aMT[(kk + 1) % MT_N] & MT_LLMASK);  
  137.         s_aMT[kk] = s_aMT[(kk + MT_M) % MT_N] ^ (ui >> 1) ^ ((ui & 0x00000001) ? MT_A : 0);  
  138.     }  
  139. }  
  140.   
  141. MersenneTwister::MersenneTwister() :  
  142.     m_ix(0)  
  143. {  
  144.     // s_aMT is already initialized with the first N primes.  
  145.     Regenerate();  
  146. }  
  147.   
  148. uint32_t MersenneTwister::Rand()  
  149. {  
  150.     if (m_ix == MT_N)  
  151.     {  
  152.         m_ix = 0;  
  153.         Regenerate();  
  154.     }  
  155.     uint32_t y;  
  156.     y = s_aMT[m_ix++];  
  157.     y ^= y >> MT_U;  
  158.     y ^= y << MT_S & MT_B;  
  159.     y ^= y << MT_T & MT_C;  
  160.     y ^= y >> MT_L;  
  161.     return y;  
  162. }  
  163.   
  164. uint64_t MersenneTwister::Rand64()  
  165. {  
  166.     uint64_t ui64;  
  167.     ui64 = Rand();  
  168.     ui64 <<= 32;  
  169.     ui64 |= Rand();  
  170.     return ui64;  
  171. }  

ps http://1stpasa.tistory.com/3

728x90
반응형
저작자표시

'Engine Development' Related Articles

티스토리툴바