बूस्टर मेर्सन ट्विस्टर: एक से अधिक मूल्य के साथ बीज कैसे करें?

Question

मैं सिमुलेशन के लिए boost mt19937 कार्यान्वयन का उपयोग कर रहा हूं।

सिमुलेशन को पुनरुत्पादित करने की आवश्यकता है, और इसका मतलब है कि बाद में आरएनजी के बीज भंडारण और संभावित रूप से पुन: उपयोग करना। मैं बीज मूल्य उत्पन्न करने के लिए विंडोज क्रिप्टो एपीआई का उपयोग कर रहा हूं क्योंकि मुझे बीज के लिए बाहरी स्रोत की आवश्यकता है, न कि यादृच्छिकता की किसी भी विशेष गारंटी के कारण। किसी सिमुलेशन रन के आउटपुट में आरएनजी बीज सहित एक नोट होगा - इसलिए बीज को उचित रूप से छोटा होना चाहिए। दूसरी ओर, सिमुलेशन के विश्लेषण के हिस्से के रूप में, मैं कई रनों की तुलना करूँगा - लेकिन यह सुनिश्चित करने के लिए कि ये रन वास्तव में अलग हैं, मुझे अलग-अलग बीजों का उपयोग करने की आवश्यकता होगी - इसलिए बीज को लंबे समय तक होने की आवश्यकता है आकस्मिक टकराव से बचने के लिए पर्याप्त।

मैंने यह निर्धारित किया है कि बीजिंग के 64-बिट पर्याप्त होना चाहिए; टकराव का मौका लगभग 2^32 रनों के बाद 50% तक पहुंच जाएगा - यह संभावना कम है कि इसके कारण होने वाली औसत त्रुटि मेरे लिए नगण्य है। केवल 32-बिट बीज का उपयोग करना मुश्किल है; टकराव का मौका 2^16 रनों के बाद 50% तक पहुंच गया है; और यह मेरे स्वाद के लिए थोड़ा सा संभावना है।

दुर्भाग्यवश, बूस्ट कार्यान्वयन या तो पूर्ण राज्य वेक्टर के साथ बीज - जो बहुत दूर है, या एक 32-बिट हस्ताक्षरित लंबा - जो आदर्श नहीं है।

मैं 32-बिट्स से अधिक जनरेटर को कैसे बीज कर सकता हूं लेकिन पूर्ण राज्य वेक्टर से कम कैसे? मैंने राज्य वेक्टर को भरने के लिए वेक्टर को पैडिंग या बीज दोहराए जाने की कोशिश की, लेकिन परिणामों में एक सरसरी नज़र से पता चलता है कि इससे खराब नतीजे निकलते हैं।

Answer 1

आपका मान्यताओं गलत कर रहे हैं (यह कार्गो पंथ सुझाव यह है)। अनुकरण के लिए, आपको क्रिप्टोग्राफिक रूप से मजबूत बीज की आवश्यकता नहीं है। वास्तव में, बीज 1,2,3,4, इत्यादि का उपयोग अक्सर एक बेहतर विचार है। मेर्सन ट्विस्टर के आउटपुट वैल्यू असंबद्ध होंगे, फिर भी कोई भी सवाल नहीं करेगा कि क्या आपने वांछित सिमुलेशन आउटपुट प्राप्त करने के लिए अपने बीज उठाए हैं।

अन्य लोगों के लिए जो वास्तविक आवश्यकता रखते हैं, एक आसान तरीका पहले (बीज >> 32) उत्पन्न मूल्यों को त्यागना है। यह आपको लॉग 2 (बीज >> 32) राज्य के अतिरिक्त बिट्स के बारे में देता है। हालांकि, अगर आपको कुछ अतिरिक्त बिट्स की आवश्यकता होती है तो यह केवल कुशलतापूर्वक काम करता है। इस तरह 32 बिट्स जोड़ना शायद धीमा है।

एक तेज़ एल्गोरिदम अच्छा यादृच्छिक जनरेटर के लिए पूर्ण राज्य वेक्टर उत्पन्न करता है। प्रश्न (दोहराव या पैडिंग) में उल्लिखित समाधान परिणामस्वरूप राज्य वेक्टर में सीमित यादृच्छिकता के कारण बहुत अच्छे नहीं हैं। लेकिन यदि आप प्रारंभिक राज्य वेक्टर को mersenne_twister(seed1)^mersenne_twister(seed2) के आउटपुट से भरते हैं, तो यह कोई मुद्दा नहीं है।

Answer 2

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; 
    } 
    } 

लिए mt19937 UIntTypeuint32_t है, w है 32. 64-बिट बीज के लिए, हो सकता है आप कम 32 बिट इस्तेमाल कर सकते हैं कि हर भी राज्य के सूचकांक की गणना करने के (x) और उस एल्गोरिदम का उपयोग करते हुए, राज्य के विषम सूचकांक की गणना करने के लिए उच्च 32 बिट्स।