एक 36 बिट यादृच्छिक संख्या जनरेटर

Question

मैं एक वातावरण है कि सुविधाओं

• 36 बिट किसी के पूरक पूर्णांकों
• अंकगणित +, -, *, / और शेष
• तक ही सीमित में एक आवेदन पत्र लिख रहा हूँ लेखन AND या OR जैसे कुछ ऑपरेशन नहीं। लेकिन किसी के पूरक के कारण, XOR घटाव के बराबर है और NOT अस्वीकरण के बराबर है।
• न्यूमेरिक ओवरफ्लो घातक है, इसलिए चुपचाप के लिए उपयोग नहीं किया जा सकता है
• हां, सशर्त हैं: IF/THEN/ELSEIF/ELSE/IF।

आदर्श रूप में, मुझे 35 या 36 बिट यादृच्छिक पूर्णांक चाहिए, लेकिन 25 बिट भी पर्याप्त होंगे।

linear congruential generator के मेरे बेवकूफ कार्यान्वयन पर्याप्त संख्याओं के आधार पर अतिप्रवाह में चलाते हैं और छोटे संख्याओं का उपयोग करते समय केवल थोड़ी सी बिट्स का उत्पादन करते हैं।

तो मैं या तो संख्या का एक सेट के लिए देख रहा हूँ एक, ग, मी कि बाधाओं में बिट्स की अधिकतम संख्या निकलेगा, या LCG की एक समझदार अनुकूलन 2 या अधिक संख्या गठबंधन करने के लिए।

एक प्रारंभिक बिंदु के रूप में, यहाँ मैं अब तक क्या उपयोग कर रहा हूँ है:

*DEFINE NextRandom . min,max resultVar 
* . This is a very shitty RNG. The numbers were never checked 
* . for suitability for a long-period linear congruential generator. 
* . But it yields numbers that look vaguely random. 
*CLEAR rq 
*CLEAR rr 
*SET RandZ = RandZ * 169687 + 347011  . RandZ is a global var. 
*DIVIDE RandZ BY 131072 GIVING rq, RandZ . Division yields a remainder 
*DIVIDE RandZ BY 4 GIVING rq 
*SET r0 = +[#,[#],1,1]     . r0 = argument 'min' 
*SET r9 = +[#,[#],1,2]     . r9 = 'max' 
*SET rd = r9 - r0 + 1 
*DIVIDE rq BY rd GIVING rq, rr 
*SET [#,[#],2,1] TO r0 + rr    . return in 'resultVar' 
*ENDDEFINE 

---

मामले में किसी को भी परवाह करता है, पटकथा भाषा एक यूनिसिस 2200 मेनफ्रेम ऑपरेटिंग सिस्टम में एसएसजी (प्रतीकात्मक धारा जनरेटर) है EXEC 8.

---

गंभीरता पर: यह आरएनजी परीक्षण डेटा उत्पन्न करने में काम करता है। यह राज्य रहस्यों या परमाणु मिसाइल कोड एन्क्रिप्ट नहीं कर रहा है। तो हम "मिशन महत्वपूर्ण" के बजाय "अच्छा होना" और "सर्वोत्तम प्रयास" के बारे में बात कर रहे हैं। मैं एक सुधार के बारे में खुश हूं लेकिन परम समाधान की तलाश नहीं कर रहा हूं। आप recursions के साथ 12 बिट पर 3 LCGs हो सकता था

x_i (एन) एक x_i = (n-1) + p_i (आधुनिक:

Answer 1

यह एक रैखिक congruential यादृच्छिक संख्या जनरेटर है कि कर सकते हैं कभी नहीं अतिप्रवाह लिखने के लिए, स्टीफन लालकृष्ण पार्क और और उनके अखबार में कीथ मिलर डब्ल्यू demonstrateयादृच्छिक संख्या जनरेटर के रूप में संभव है: अच्छे के लिए खोजें हार्ड हैं:

function Random : real; 
        (* Integer Version 2 *) 
const 
    a = 16807; 
    m = 2147483647; 
    q = 127773; (* m div a *) 
    r = 2836; (* m mod a *) 
var 
    lo, hi, test : integer; 
begin 
    hi := seed div q; 
    lo := seed mod q; 
    test := a * lo - r * hi; 
    if test > 0 then 
    seed := test 
    else 
    seed := test + m; 
    Random := seed/m 
end; 

यहां एम 2^31-1 है, लेकिन आप इसे 36-बिट संख्याओं के उत्पादन के लिए बदल सकते हैं। चाल यह है कि बीज हाय और लो भागों में विभाजित है और अंतिम यादृच्छिक संख्या भागों को संक्षेप में उत्पन्न किया जाता है।

यदि आपको यह पसंद नहीं है, तो मेरे पास मेरे ब्लॉग पर यादृच्छिक संख्या जेनरेटर के lots हैं। शायद उनमें से एक आप जो चाहते हैं वह करेगा।

Answer 2

बस एक साधारण विचार है, मुझे लगता है कि यदि वास्तव में सबसे अच्छा है पता नहीं है 2^{12})

जिसमें विभिन्न प्राइम्स p_i हैं। यदि कोई बहुत बड़ा नहीं है (12-बिट कहें), यह कभी भी बह जाएगा नहीं। फिर, 3 12-बिट यादृच्छिक संख्याओं के साथ, आप 36-बिट यादृच्छिक पूर्णांक बना सकते हैं:

z (n) = x_0 (n) + 2^{12} x_1 (n) + 2^{24} x_2 (एन)

टिप्पणी करें कि यदि पी_आई प्राइम और अपेक्षाकृत बड़े हैं, तो 3 यादृच्छिक जेनरेटर काफी स्वतंत्र होना चाहिए, ताकि रणनीति ठीक होनी चाहिए।

कठिनाई के लिए एक अच्छा विकल्प होना है।

वैसे भी, इसका उपयोग करने से पहले, मुझे लगता है कि यह कुछ परीक्षण बेहतर होगा।