기본기) 랜덤 - 의사 난수 발생기 (Pseudo Random Number Generator : PRNG)

랜덤 - 의사 난수 발생기 (Pseudo Random Number Generator : PRNG)

의사 난수 발생기는 많은 양의 난수 발생이 필요할 때 확률 및 통계, 응용프로그램을 위해서 사용되는 랜덤 발생기이다.

랜덤이라는 알고리즘이 아무리 정교하더라도 다음 숫자를 예측할 수 있는 상황이 생기기 때문에 이러한 숫자 난수 시퀀스는 실제로는 무작위가 아니다. 의사 난수 발생기는 초기 시드(Seed)를 이용해서 임의의 시작 상태에서 시작하여 난수의 속성에 가까운 일련의 숫자를 생성한다.

반응형

난수 발생기 중 가장 유명한 3가지에 대해서 간략하게 코드만 정리하도록 한다.

 

<선형합동법 (Linear Congruential Method) >

Xn+1=(aXn+c)mod m

   return (float)((seed * 9301 + 49297) % 233280 / 233280.0f);

<메르센 트위스트 (Mersenne twister)>

기존의 난수 생성의 문제점을 개선한 난수 발생으로 난수의 품질과 속도를 개선했다.

seed를 포함한 624개의 정수를 이용해서 난수 발생을 한다.

난수의 생성 비트에 따라 MT19937, MT19937-64로 나뉜다.

 public class RandomMersenne
    {
        const int MERS_N = 624;
        const int MERS_M = 397;
        const int MERS_U = 11;
        const int MERS_S = 7;
        const int MERS_T = 15;
        const int MERS_L = 18;
        const uint MERS_A = 0x9908B0DF;
        const uint MERS_B = 0x9D2C5680;
        const uint MERS_C = 0xEFC60000;

        uint[] mt = new uint[MERS_N];          // state vector
        uint mti;                            // index into mt

        private RandomMersenne() { }
        public RandomMersenne(uint seed)
        {       // constructor
            RandomInit(seed);
        }
        public void RandomInit(uint seed)
        {
            SetSeed(seed);
        }

        public void SetSeed(uint seed)
        {
            mt[0] = seed;
            for (mti = 1; mti < MERS_N; mti++)
                mt[mti] = (1812433253U * (mt[mti - 1] ^ (mt[mti - 1] >> 30)) + mti);
        }
        public void RandomInitByArray(uint[] seeds)
        {
            // seed by more than 32 bits
            uint i, j;
            int k;
            int length = seeds.Length;
            RandomInit(19650218U);
            if (length <= 0) return;
            i = 1; j = 0;
            k = (MERS_N > length ? MERS_N : length);
            for (; k != 0; k--)
            {
                mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1664525U)) + seeds[j] + j;
                i++; j++;
                if (i >= MERS_N) { mt[0] = mt[MERS_N - 1]; i = 1; }
                if (j >= length) j = 0;
            }
            for (k = MERS_N - 1; k != 0; k--)
            {
                mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1566083941U)) - i;
                if (++i >= MERS_N) { mt[0] = mt[MERS_N - 1]; i = 1; }
            }
            mt[0] = 0x80000000U; // MSB is 1; assuring non-zero initial array
        }
        public int IRandom(int min, int max)
        {
            // output random integer in the interval min <= x <= max
            int r;
            r = (int)((max - min + 1) * Random()) + min; // multiply interval with random and truncate
            if (r > max)
                r = max;
            if (max < min)
                return -2147483648;
            return r;
        }
        public double Random()
        {
            // output random float number in the interval 0 <= x < 1
            uint r = BRandom(); // get 32 random bits
            if (System.BitConverter.IsLittleEndian)
            {
                byte[] i0 = System.BitConverter.GetBytes((r << 20));
                byte[] i1 = System.BitConverter.GetBytes(((r >> 12) | 0x3FF00000));
                byte[] bytes = { i0[0], i0[1], i0[2], i0[3], i1[0], i1[1], i1[2], i1[3] };
                double f = System.BitConverter.ToDouble(bytes, 0);
                return f - 1.0;
            }
            return r * (1.0 / (0xFFFFFFFF + 1.0));
        }
        public uint BRandom()
        {
            // generate 32 random bits
            uint y;

            if (mti >= MERS_N)
            {
                const uint LOWER_MASK = 2147483647;
                const uint UPPER_MASK = 0x80000000;
                uint[] mag01 = { 0, MERS_A };

                int kk;
                for (kk = 0; kk < MERS_N - MERS_M; kk++)
                {
                    y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
                    mt[kk] = mt[kk + MERS_M] ^ (y >> 1) ^ mag01[y & 1];
                }

                for (; kk < MERS_N - 1; kk++)
                {
                    y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
                    mt[kk] = mt[kk + (MERS_M - MERS_N)] ^ (y >> 1) ^ mag01[y & 1];
                }

                y = (mt[MERS_N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
                mt[MERS_N - 1] = mt[MERS_M - 1] ^ (y >> 1) ^ mag01[y & 1];
                mti = 0;
            }

            y = mt[mti++];

            // Tempering (May be omitted):
            y ^= y >> MERS_U;
            y ^= (y << MERS_S) & MERS_B;
            y ^= (y << MERS_T) & MERS_C;
            y ^= y >> MERS_L;
            return y;
        }
    }

 

코드 : [링크]

Mersenne Twister Random Number Generation in C# - PROWARE technologies

 

<WELL512>

public class Well512
    {
        static int[] state = new int[16];
        static int index = 0;

        public Well512()
        {
            System.Random random = new System.Random((int)System.DateTime.Now.Ticks);

            for (int i = 0; i < 16; i++)
            {
                state[i] = (int)random.Next();
            }
        }

        internal int Next(int minValue, int maxValue)
        {
            return (int)((Next() % (maxValue - minValue)) + minValue);
        }

        public int Next(int maxValue)
        {
            return Next() % maxValue;
        }

        public int Next()
        {
            int 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 ^ (int)((a << 5) & 0xda442d24U);
            index = (index + 15) & 15;
            a = state[index];
            state[index] = a ^ b ^ d ^ (a << 2) ^ (b << 18) ^ (c << 28);

            return state[index];
        }

코드 : [링크]

.NET Framework: 313. WELL512 난수 발생 알고리즘 - C#

 

<선형합동법 (Linear Congruential Method) >	씨드를 기준으로 랜덤값을 만듬 속도는 빠르지만 단순해서 예측이 쉽다.
<메르센 트위스트 (Mersenne twister)>	선형 합동법보다 복잡하고 기존의 랜덤의 분포도를 개선한 랜덤
<WELL512>	메르센 트위스트를 개선한 알고리즘으로 균등한 랜덤의 분포도를 가진다.

반응형

 

최소한의 표현의 방식으로 x,y로만 테스트를 진행했다.

해당 코드로 Cube를 같은 조건(1000개)을 x, y 포지션을 생성한 결과이다.

c/c++ rand	<선형합동법 (Linear Congruential Method) >	<메르센 트위스트 (Mersenne twister)>	WELL512

같은 조건으로 2000개를 생성한 결과는 다음과 같다.

c/c++ rand	<선형합동법 (Linear Congruential Method) >	<메르센 트위스트 (Mersenne twister)>	WELL512

 

<분기별로 0.5f 딜레이 이후에 테스트한 코드 영상>

<결론>

 

가장 단순한 작업에서는 내장 Random를 사용하고

고정된 Seed 별로 일련의 순서를 처리하기 위해서는 단순하게는 선형합동법 (Linear Congruential Method)을 사용하고

반복된 랜덤으로 균등하게 보장된 값을 원하면 메르센 트위스트 (Mersenne twister), WELL512 을 사용하면 될것 같다.

결국 어떤 빈도와 어떤 형태의 랜던값이 필요한지에 따라 선택해서 사용하면 된다.

 

모든 랜덤에 대해서 전부 이해하고 작업했다고 보기에는 무리가 있습니다.

여러가지 사이트를 참고했고

개인적인 생각 + 개인적인 코드로 인해서 테스트 결과가 정상적이지 않을수 있습니다. (단순테스트)

 

 

★★☆☆☆