क्यों रैंड में 1103515245 का उपयोग किया जाता है?

Question

मैं सी मानक से rand() की this के बारे में आश्चर्यजनक रूप से सरल कार्यान्वयन बात कर रहा हूँ:

static unsigned long int next = 1; 

int rand(void) /* RAND_MAX assumed to be 32767. */ 
{ 
    next = next * 1103515245 + 12345; 
    return (unsigned)(next/65536) % 32768; 
} 

this Wikipedia article से हम जानते हैं कि गुणक a (ऊपर कोड a = 1103515245 में) केवल 2 शर्तों को पूरा करना चाहिए:

1. a - 1m के सभी प्रमुख कारकों द्वारा विभाजित है।
   (हमारे मामले m = 2^32 में, पूर्णांक के आकार, इसलिए m केवल एक प्रधानमंत्री कारक है = 2)
2. a - 1 के 4 अगर m 4.
   (32768 की एक बहु है एक बहु है 4 के एक से अधिक, और 1103515244 भी)

क्यों वे चुना है इस तरह के एक अजीब, मुश्किल से याद है, "यार, मैं इन यादृच्छिक संख्या के साथ तंग आ गया हूँ, लिख जो कुछ भी" संख्या, ११०३५१५२४५ की तरह?

शायद कुछ बुद्धिमान कारण हैं, कि यह संख्या किसी अन्य से बेहतर है?

उदाहरण के लिए, a = 20000000001 क्यों सेट नहीं करें? यह याद रखने के लिए बड़ा, शांत दिखने वाला और आसान है।

Answer 1

आप घ आयामी अंतरिक्ष पर अंक आकर्षित करने के लिए एक LCG का उपयोग करते हैं, वे सबसे अधिक (घ! मीटर) पर पर झूठ होगा ^{/ _घ} hyperplanes। यह एलसीजी का ज्ञात दोष है।

यदि आप ध्यान से नहीं चुनते हैं और एम (पूर्ण आवधिकता के लिए स्थिति से परे), तो वे उससे कम विमानों पर झूठ बोल सकते हैं। उन नंबरों को चुना गया है जिन्हें वर्णक्रमीय परीक्षण कहा जाता है।

"वर्णक्रमीय परीक्षण" (नाम संख्या सिद्धांत से आता है) लगातार हाइपरप्लेन के बीच अधिकतम दूरी है जिस पर डी-आयामी संयुक्त वितरण झूठ बोलते हैं। आप जितना संभव हो उतना छोटा होना चाहते हैं जितना आप परीक्षण कर सकते हैं।

विषय पर ऐतिहासिक समीक्षा के लिए this paper देखें। ध्यान दें कि आपके द्वारा उद्धृत जनरेटर का उल्लेख पेपर (एएनएसआईसी के रूप में) में किया गया है और यह बहुत अच्छा नहीं है। उच्च आदेश 16 बिट स्वीकार्य हैं, लेकिन कई अनुप्रयोगों को 32768 से अधिक विशिष्ट मानों की आवश्यकता होगी (जैसा कि आप टिप्पणियों में इंगित करते हैं, अवधि वास्तव में 2^31 है - विकिपीडिया के लिंक में पूर्ण आवधिकता की शर्तें शायद आवश्यक हैं)।

एएनएसआई दस्तावेज़ में मूल स्रोत कोड उच्च आदेश 16 बिट्स नहीं लिया, एक बहुत ही गरीब जनरेटर जो दुरुपयोग करने के लिए आसान है उपज (rand() % n क्या लोगों को पहली 0 और n, और इस बीच एक संख्या आकर्षित करने के लिए के बारे में सोच है इस मामले में कुछ गैर-यादृच्छिक पैदा करता है)।

न्यूमेरिकल व्यंजनों में एलसीजी पर भी चर्चा देखें। का हवाला देते हुए:

भी बदतर, कई प्रारंभिक जनरेटर मीटर है और एक के लिए विशेष रूप से बुरा विकल्प बनाने के लिए हुआ है। एक कुख्यात इस तरह की दिनचर्या, रैंडू, एक = 65539 और एम = 231 के साथ, आईबीएम मेनफ्रेम कंप्यूटर पर कई वर्षों, पर व्यापक रूप से व्यापक थी और व्यापक रूप से अन्य प्रणालियों पर प्रतिलिपि बनाई गई थी। हम में से एक स्नातक छात्र के रूप में याद करता है जो केवल 11 विमानों के साथ "यादृच्छिक" साजिश का उत्पादन करता है और को अपने कंप्यूटर सेंटर के प्रोग्रामिंग सलाहकार द्वारा बताया जा रहा है कि उसने यादृच्छिक संख्या जनरेटर का दुरुपयोग किया था: "हम गारंटी देते हैं कि प्रत्येक नंबर यादृच्छिक व्यक्तिगत रूप से है, लेकिन हम गारंटी नहीं देते हैं कि उनमें से एक से अधिक यादृच्छिक है। "इससे कम से कम एक वर्ष तक हमारी स्नातक शिक्षा वापस आ गई!

Answer 2

याद रखें कि rand()uniform distribution का अनुमान है। उन संख्याओं का उपयोग किया जाता है क्योंकि उन्हें यह दिखाने के लिए परीक्षण किया गया है कि वे एक समान वर्दी दिखने वाले वितरण उत्पन्न करते हैं।

प्रदर्शनीय रेंज में अहस्ताक्षरित पूर्णांकों के जोड़े की भीड़ को देखते हुए, मैं किसी उन सब को सभी वैध बीज के साथ की कोशिश की है संदेह है। यदि आपको लगता है कि आपके पास पैरामीटर की बेहतर पसंद है, तो बस इसे आज़माएं! आपके पास कोड है, बस LCG के पैरामीटर को कारक बनाएं और परीक्षण चलाएं। संख्याओं का एक गुच्छा उत्पन्न करें (10 मिलियन कहें), उत्पन्न संख्याओं और साजिश के हिस्टोग्राम की गणना करें जो वितरण को देखने के लिए है।

संपादित आप वास्तविक अनुप्रयोगों में प्रयोग के लिए एक छद्म यादृच्छिक संख्या जनरेटर को विकसित करने में रुचि रखते हैं, मैं सुझाव है कि आप इस विषय पर काफी साहित्य को पढ़ने। "सलाह" ऊपर दिए गए केवल मदद करने के लिए पता चलता है कि चुनने मनमाने ढंग से "बड़ा, शांत दिखने और आसान याद करने के लिए" LCG मापदंडों एक बहुत ही गरीब वितरण दे देंगे सुझाव दिया है। /संपादन

इसके अलावा, यह एक पुस्तकालय समारोह है और मैं अपने LCG के मापदंडों को याद करने के rand() के मानक पुस्तकालय संस्करण का उपयोग कर एक कार्यक्रम कभी नहीं देखा।

Answer 3

संख्या विशेष लगता है कि, यह सिर्फ दो अभाज्य संख्या के बीच है: पी।

अब गंभीरता से बात कर रहे हैं, यह देखने के लिए कि यह एक अच्छा विकल्प है, बस आउटपुट देखें। एक बिट को फिसलने के बावजूद आपको बहुत अलग परिणाम देखना चाहिए।

इसके अलावा, इस बात पर विचार करें कि आप कितनी भविष्यवाणी की उम्मीद करते हैं ... कि कार्यान्वयन भयानक है, आप FNV-1a जैसे अधिक मजबूत लेकिन सरल विकल्प पर विचार कर सकते हैं।

Answer 4

प्रारंभिक संगणना बिट्स और बाइट्स और रजिस्टरों के साथ खेला चाल के साथ खुद में काफी चिंतित कोड के बाइट्स को कम से कम करने की प्रवृत्ति (लाइनों से पहले वहाँ थे बाइट्स)

मैं केवल एक उचित सुराग नीचे पाया है:

इस जनरेटर का आउटपुट बहुत यादृच्छिक नहीं है। यदि हम ऊपर सूचीबद्ध नमूना जनरेटर का उपयोग करते हैं, तो 16 कुंजी बाइट्स का अनुक्रम अत्यधिक गैर-यादृच्छिक होगा। उदाहरण के लिए, यह पता चला है कि रैंड() के प्रत्येक क्रमिक आउटपुट का निम्न बिट वैकल्पिक होगा (उदाहरण के लिए, 0,1,0,1,0,1, ...)। क्या तुम देखते हो क्यों? एक्स * 1103515245 का निम्न बिट एक्स के निम्न बिट के समान है, और फिर 12345 जोड़ना बस कम बिट को फ़्लिप करता है। इस प्रकार कम बिट alternates। यह केवल 2113 संभावनाओं के लिए संभावित कुंजी के सेट को कम करता है, 2128 के वांछित मूल्य से बहुत कम है।

http://inst.eecs.berkeley.edu/~cs161/fa08/Notes/random.pdf

और दो उचित जवाब:

एक गरीब यादृच्छिक संख्या जनरेटर (1976) Bays, डरहम Bays, कार्टर, एसडी डरहम

http://en.wikipedia.org/wiki/TRNG