부스터 Mersenne Twister : 두 개 이상의 값으로 시드하는 방법?

시뮬레이션을 위해 boost mt19937 구현을 사용하고 있습니다.부스터 Mersenne Twister : 두 개 이상의 값으로 시드하는 방법?

시뮬레이션은 재생성이 가능해야하며 이는 나중에 RNG 시드를 저장하고 잠재적으로 재사용한다는 의미입니다. 씨앗에 대한 외부 소스가 필요하고 난수의 특정 보장 때문에가 아니기 때문에 저는 시드 암호를 생성하기 위해 Windows 암호화 API를 사용하고 있습니다. 모든 시뮬레이션 실행 결과에는 RNG 시드를 포함하는 메모가 있습니다. 따라서 씨앗은 비교적 짧아야합니다. 다른 한편, 시뮬레이션 분석의 일환으로 몇 가지 실행을 비교해 보겠습니다. 그러나 이러한 실행이 실제로 다르다는 것을 확인하려면 다른 시드를 사용해야합니다. 따라서 시드가 길어야합니다. 우발적 인 충돌을 피하기에 충분합니다..

필자는 64 비트의 시딩으로 충분하다고 판단했습니다. 충돌 가능성은 약 2^32 회 실행 후 50 %에 도달합니다. 그 확률로 인해 발생하는 평균 오류가 저에게는 거의 미치지 않습니다. 단지 32 비트의 시드를 사용하는 것은 까다 롭습니다. 충돌의 기회는 2^16의 달리기 후에 이미 50 %에 이릅니다. 그건 내 취향에 맞지 않을 것 같아.

불행히도, 부스트 구현은 전체 상태 벡터 - 멀리, 너무 길다 - 또는 하나의 32 비트 부호없는 long으로 시드한다 - 이상적이지 않다.

전체 상태 벡터보다 작지만 32 비트 이상으로 생성기를 시드하려면 어떻게해야합니까? 나는 단지 벡터 패딩을 시도하거나 상태 벡터를 채우기 위해 씨앗을 반복하려했지만, 결과를 간략하게 보여도 그 결과가 좋지 않음을 보여줍니다.

출처

2010-05-26 Eamon Nerbonne

현재 상태를 얻고 수정하십시오. – kennytm

충돌 계산이 정확하지 않습니다. 예를 들어, 64 비트 시드의 경우 77163! = 65536이 실행 된 후 복제 확률은> 0.5입니다. – user168715

충돌 수학은 단지 대략적인 근사값입니다. 64 비트 시드가 아닌 32 비트 시드를 의미한다고 가정합니다. –

귀하의 가정은 잘못된 것입니다. 시뮬레이션의 경우 암호 학적으로 강력한 시드가 필요하지 않습니다. 실제로 씨앗 1,2,3,4 등을 사용하면 더 좋은 아이디어입니다. Mersenne Twister의 출력 값은 상관 관계가 없지만 원하는 시뮬레이션 출력을 얻기 위해 체리를 뽑았는지에 대한 질문은 없습니다.

진짜 필요가있는 다른 사람들을 위해, 쉬운 방법은 생성 된 첫 번째 값 (seed >> 32)을 버리는 것입니다. 이것은 log2 (시드 >> 32) 상태에 대한 추가 비트를 제공합니다. 그러나 몇 가지 추가 비트가 필요한 경우에만 효율적으로 작동합니다. 이 방법으로 32 비트를 추가하는 것은 너무 느립니다.

더 빠른 알고리즘은 좋은 임의 생성기에 대한 전체 상태 벡터를 생성하는 것입니다. 질문 (반복 또는 패딩)에서 언급 한 솔루션은 결과 상태 벡터의 제한된 임의성으로 인해별로 좋지 않습니다. 그러나 mersenne_twister(seed1)^mersenne_twister(seed2)의 출력에서 초기 상태 벡터를 채우는 경우에는 문제가되지 않습니다.

출처

2010-05-27 09:33:51 MSalters

나는 암호로 보호받는 것에 대해 걱정하지 않는다; 그냥 * 어딘가에서 시드 값을 가져와야합니다 *. 순차적 인 씨앗을 사용할 때의 단점은 부분적으로 관리하는 것입니다. 즉 씨앗의 미리 결정된 시퀀스를 사용하면 어떻게 든 씨앗을 관리하지 않으면 (즉, 실수로 씨앗을 재사용하지 않도록 파일을 어딘가에 사용하지 않는 한) 모든 실행이 동일하다는 것을 의미합니다. –

'mersenne_twister (seed1)^mersenne_twister (seed2) '의 문제점은 seed 값이 동일 할 수 있다는 것입니다.이 경우 출력은 XOR이 0 인 경우입니다 - 전체 상태 벡터를 0으로 채우기 붙어있는 트위스터 (나는 그것이 전혀 빠져 나올 수는 없지만 확실히 빠르지는 않는다). –

그러나 개별적으로 검사 가능한 실행 (32 비트 시드는 괜찮음)과 집계 된 분석 실행 (순차 시드가 완벽하게 일치하는 경우)을 구별하면 순차 시드를 사용하는 아이디어를 사용할 수 있습니다. –

boost sources of mersenne_twister template에서 상대 :

void seed(UIntType value) 
    { 
    // New seeding algorithm from 
    // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html 
    // In the previous versions, MSBs of the seed affected only MSBs of the 
    // state x[]. 
    const UIntType mask = ~0u; 
    x[0] = value & mask; 
    for (i = 1; i < n; i++) { 
     // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106 
     x[i] = (1812433253UL * (x[i-1]^(x[i-1] >> (w-2))) + i) & mask; 
    } 
    }

UIntType mt19937를 들어 uint32_t입니다 w됩니다 (32)가 64 비트 종자를 들어, 어쩌면 당신이 국가의 모든 심지어 인덱스를 계산하기 위해 (x를) 하위 32 비트를 사용할 수 있습니다 그 알고리즘을 사용하여 상태의 홀수 인덱스를 계산하기위한 상위 32 비트.

출처

2010-05-26 22:40:30 sbk

부스터 Mersenne Twister : 두 개 이상의 값으로 시드하는 방법?

답변

관련 문제