Typescript / Javascript 환경에서 메르센-트위스터 [MT19937] 알고리즘 사용하여 난수 생성하기

Typescript 환경에서 난수를 사용 해야 하는 니즈가 있었다. 단순히 seedrandom 같은 라이브러리를 사용해도 되었지만, 의사난수 생성 알고리즘 중 메르센-트위스터 19937 알고리즘에 관심이 생겨 사용하고자 하였다. 

 

가볍게 깃헙에서 구현된 코드를 발견하였고 (https://gist.github.com/aradzie/c12da8c537e83c0fae52), 그대로 가져다가 사용하였다. 그런데 온라인에 구현된 메르센-트위스터 생성기와 시드가 동일함에도 불구하고 다른 난수를 생성함을 우연히 발견하였다. (온라인에서 발견한 난수생성 사이트 https://asecuritysite.com/primes/twister)

 

구현된 코드를 비교해 보았을 때 크게 다른 점이 없어서 의문이었다. 직접 cpp 컴파일을 하며 디버깅을 해본 결과, 자바스크립트의 부동 소수점 오류 때문 임을 알게되었다. 32bit 정수를 곱하면서 문제가 생긴 것 이었다.

 

구체적으로는 다음과 같다. 예를 들어 seed가 0인 경우, gpp 환경에서 initial array는 다음과 같이 시작한다. 

0, 1, 1812433255 1900727105, 1208447044, 2481403966, ...

 

하지만 javascript 환경에서는 다음과 같다.

0, 1, 1812433255, 1900727296, 3115714048, 2954195200, ...

 

문제가 되는 4번째 항을 살펴보면, 1812433253 * (1812433255 ^ (1812433255 >> 30)) + 3 의 결과가 서로 다르게 나오는데, 직접 계산기를 돌려보면 1900727105 가 옳음을 알 수 있었다.

 

이대로 typescript 환경에서의 구현을 포기할 수는 없어서 조금 더 탐색해보았고 다행히도 32bit 정수 계산을 잘 해놓은 라이브러리가 있었다. https://www.npmjs.com/package/@stdlib/random-base-mt19937

 

사실 라이브러리를 활용하라는 당연한 글이지만, javascript의 한계에 의해 삽질 하게 되었어서 기록해본다.

 

참고: 비교해 본 cpp 코드

#include <iostream>
#include <cstdint>

class MT19937
{
private:
    uint32_t state[624];
    int index;

public:
    MT19937(uint32_t seed)
    {
        index = 0;
        state[0] = seed;
        std::cout << state[0] << std::endl;
        for (int i = 1; i < 624; ++i)
        {
            state[i] = (1812433253 * (state[i - 1] ^ (state[i - 1] >> 30)) + i) & 0xFFFFFFFF;
            std::cout << state[i] << std::endl;
        }
    }

    uint32_t extractNumber()
    {
        if (index == 0)
        {
            generateNumbers();
        }
        uint32_t y = state[index];
        y ^= (y >> 11);
        y ^= ((y << 7) & 0x9D2C5680);
        y ^= ((y << 15) & 0xEFC60000);
        y ^= (y >> 18);
        index = (index + 1) % 624;
        return y;
    }

private:
    void generateNumbers()
    {
        for (int i = 0; i < 624; ++i)
        {
            uint32_t y = (state[i] & 0x80000000) + (state[(i + 1) % 624] & 0x7FFFFFFF);
            state[i] = state[(i + 397) % 624] ^ (y >> 1);
            if (y % 2 != 0)
            {
                state[i] ^= 0x9908B0DF;
            }
        }
    }
};

int main()
{
    uint32_t seed = 0;
    MT19937 generator(seed);
    uint32_t firstValue = generator.extractNumber();

    std::cout << "First Value with Seed 0: " << firstValue << std::endl;

    return 0;
}