Contents

Mersenne Twister(MT) 는 1996~7년에 Makoto Matsumoto와 Takuji Nishimura에 의해 발표된 의사 난수 생성기를 말합니다. MT는 다음과 같은 장점을 가지고 있습니다.

• 기존의 다양한 생성기의 결점들을 고려하여 디자인되었습니다.
• 알고리즘이 C 언어로 코딩되어있으며, 자유롭게 다운로드 가능합니다. BSD 라이센스를 따르며, 상업적이든 어떠한 용도로든 사용이 가능합니다.
• 어떠한 다른 기존 구현된 생성기보다도 동일분포(equidistribution)에 있어서 훨씬 먼 구간과 훨씬 높은 정렬부하를 가지고 있습니다. (2^19937 - 1)의 범위를 가지고 있다고 증명되어있으며, 623차원의 동일분포 속성을 보증합니다.)
• 생성속도가 빠릅니다. (비록 시스템에 의존하긴 하지만, MT는 파이프라인이나 캐시 메모리를 가진 시스템상에서 때때로 표준 ANSI-C 라이브러리보다 빠르다고 보고되고 있습니다.)
• 메모리의 효율적인 사용. (mt19937.c 구현코드는 동작하는데 있어 단지 624 word만 소모합니다.)
• 파이선 스크립트에서는 기본 random 모듈용 알고리즘으로서 사용되고 있습니다. 즉, 파이선 사용자는 그냥 random 모듈을 사용하시면 됩니다.
• boost::random 에서 기본 알고리즘으로 포함되어있습니다.
  
  

• 원문링크 : http://www.math.keio.ac.jp/~matumoto/MT2002/emt19937ar.html

MT의 모든 이전 버전에서의 초기화 루틴에는, seed상의 최상위 비트(most significant bit)가 상태 벡터(state vector)에 잘 반영되지 않는다는 작은 문제점이 존재합니다.

We should have noticed this when an important caution on initializing tt800 (a small cousin of MT19937) was raised by Jeff Szuhay in the world-known random-number homepage pLab, or when Dick van Albada taught us that the older initialization scheme may yield just nearly "shifted" sequence and sent us mtRand.tgz, his nicely improved C++code (2000/5/24). The both phenomena arise from the same problem, namely that if two initial states are too near with respect to the Hamming distance, then the corresponding output sequences are close to each other.

This type of defficiency becomes very clear by a report by Martin Kretschmar , who initialized the state vector with many zeroes, or some bit-pattern. 이렇게 하면 난수적이지 않은 부분은 오랫동안 남아있게 됩니다.

여기 이러한 결점을 해결하는 MT19937의 새로운 표준 코드, mt19937ar.c(ar은 ARray를 의미합니다)를 게시합니다. 이 코드는 seed로서 임의의 길이의 배열을 허가하는 또다른 초기화부분을 포함하고 있습니다.

• 이전의 초기화 루틴들 대신에 init_genrand(seed)을 사용하시기 바랍니다.
• 32비트 길이보다 더 긴 초기화 seed를 필요로하는 사용자는, 초기화시 seed값으로서 임의의 길이의 배열을 받아들이는 init_by_array()을 사용할 수 있습니다.
• [0,1)이나 53비트 정밀도 실수등등과 같은 실수 버전이 이제 사용가능합니다.
  
  

• gzip압축된 tar화일: mt19937ar.tgz
• 화일별 다운로드 : C-source(mt19937ar.c), 예제 출력(mt19937ar.out), readme화일(readme-mt.txt).
  
  

이 버전은 공개입니다. 이것은 BSD 라이센스를 따른다는 것을 의미하며, 상업적 용도로서의 수정이나 사용을 허가한다는 뜻입니다.

• Those who needs speed: all the five real-versions make a function call to the integer version genrand_int(), which makes them slower than the previous versions. If you maximize your compiler's optimization level, it often develops the function call into "inline". If it does not, and if you need speed, then copy the code of genrand_int into the necessary functions, and add by hand your requiring transformation from integer to real.
  
  
• A faster version considering Shawn Cokus's code is also available (2002/Feb./11). gzipped tar-file of Cokus-type code with simplification and speed-up by Matthew Bellew: mt19937ar-cok.tgz.
  • 화일별 다운로드 : C 소스(mt19937ar-cok.c), 출력 예제(mt19937ar-cok.out), readme화일(readme-mt.txt).
    
    

In the last "return()" in the function genrand(), (double)y is divided by (unsigned long)0xffffffff, i.e. 2^32-1. If you change this to 2^32, the output is distributed in [0,1). How to construct the real constant 2^32 depends on your system, but for example

double zzz = ((double)((unsigned long) 0x80000000))*2;

sets the real 2^32 into zzz. We guess there is a smarter way: let us know.

A master course student Sin Tanaka at the electoric engineering department of Keio University suggested to obtain a real 2^{-32} as a real constant. The corresponding code is included on the main page.

(2002/Jan.8th added) Isaku Wada gave a nice comment on this. For [0,1], replace the last return with

return y*(1.0/4294967295.0); /* reals */

and for [0,1), replace the last return with

return y*(1.0/4294967296.0); /* reals: [0,1)-interval */ 

Since most compilers compute the constant when it is compiled, so this code runs with the same speed with the standard C codes, and portability and readability are better.

Concatenate two successive 32-bit integers to get a 64-bit integer.

Isaku Wada again gave us a good comment. Using integer version's genrand() twice as follows:

double random(void) 
{ 
unsigned long a=genrand()>>5, b=genrand()>>6; 
return(a*67108864.0+b)*(1.0/9007199254740992.0); 
} 

This gives a uniform randomnumber in [0,1) with 53-bit precision.

The sequence is, as it is, not cryptographically secure. However, if you use an appropriate Secure Hashing Algorithm (non-invertible function compressing several words into one word), then you may use them. To be precise, in the existing encryption methods with a linear pseudorandom generator (like GFSR), to replace the generator with the large period MT is valid. In this case, you may need more than 2^32-1 initial seeds. The initializing routine sgenrand(seed) of MT is a mere linear-congruential generator. If you do not use sgenrand, then the actual initial seed consist of the 19937 bits = the 19968 bits of the array mt0..623 minus the lower 31 bits of mt[0]. Help: we are not experts in this area. Please let us know appropriate references and knowledges on cryptographically secure generators.

If the application is not sensitive to the rounding off error, then please multiply N to [0,1)-real uniform random numbers and take the integer part (this is sufficient for most applications). Caution: never use [0,1]-real version. If one does, then a hard-to-find bug creeps in that 0xffffffff occurs once in about 4.2 billion generations hence returns N. (Isaku Wada pointed out, added on 2002/Jan.8th.) In the very rare case that the rounding off error of real numbers does matter, then generate random integers, take the minimum integer with N<=2^n, take the most significant n bits and discard the numbers greater than or equal to N.

Seed space of 622 words of 32-bit integers is available. For example, in mt19937.c, there is an array named mt[N]. Read the code of sgenrand(), then you will find that the seed word is passed to mt[0], and then mt[1], mt[2], ... are filled by a random number generator. You may put the value 0xffffffff to mt[0], and use all the rest mt[1]...mtN-1 as 622 words' seed space. Every initial value is safe. Some versions of mt implements the array in a converse way, so carefully read the code if you use other versions.