समान रूप से वितरित यादृच्छिक संख्या पीढ़ी

Question

यह कोड समान रूप से वितरित संख्या क्यों उत्पन्न करता है? मुझे समझने में कुछ कठिनाइयां हैं। क्या कोई समझा सकता है? धन्यवाद।

int RandomUniform(int n) { 
    int top = ((((RAND_MAX - n) + 1)/n) * n - 1) + n; 
    int r; 
    do { 
    r = rand(); 
    } while (r > top); 
    return (r % n); 
} 

अपडेट: मुझे समझ में आता है कि क्यों रैंड()% n आपको समान रूप से वितरित अनुक्रम नहीं देता है। मेरा सवाल है कि

top = ((((RAND_MAX - n) + 1)/n) * n - 1) + n; 

यहां चिंता क्या है? मुझे लगता है कि एक साधारण शीर्ष = RAND_MAX/n * n करेगा।

Answer 1

फ़ंक्शन मानता है कि rand() समान रूप से वितरित किया गया है; चाहे वह मान्य धारणा है या नहीं rand() के कार्यान्वयन पर निर्भर करता है।

एक समान rand() को देखते हुए, हम rand()%n की गणना करके [0,n) श्रेणी में यादृच्छिक संख्या प्राप्त कर सकते हैं। हालांकि, सामान्य रूप से, यह काफी समान नहीं होगा। उदाहरण के लिए, मान लीजिए n 3 और RAND_MAX 7:

rand()  0 1 2 3 4 5 6 7 
rand() % n 0 1 2 0 1 2 0 1 

हम देख सकते हैं कि 0 और 1 3/8 की संभावना के साथ आते हैं, जबकि 2 केवल 2/8 की एक संभावना के साथ आता है: वितरण एक समान नहीं है।

आपका कोड rand() के किसी भी मूल्य को n के सबसे बड़े एकाधिक के बराबर या बराबर करता है जो इसे उत्पन्न कर सकता है।

rand()  0 1 2 3 4 5 6 7 
rand() % n 0 1 2 0 1 2 X X 

तो 0,1 और 2 सभी 1/3 की संभावना के साथ आते हैं, जब तक कि हम इतनी बदकिस्मत कि पाश कभी नहीं समाप्त हो जाता है नहीं कर रहे हैं: अब प्रत्येक मान एक समान आशंका होती है।

अपने अद्यतन के बारे में:

मुझे लगता है कि एक साधारण शीर्ष = RAND_MAX/n * n करना होगा।

यदि RAND_MAX एक विशेष बाध्य (वास्तविक अधिकतम से अधिक एक) थे, तो यह सही होगा।चूंकि यह एक समावेशी बाध्य है, इसलिए हमें अनन्य बाध्य करने के लिए एक जोड़ना होगा; और के बाद से निम्नलिखित तर्क एक समावेशी बाध्य खिलाफ > के साथ तुलना करें, तो एक बार फिर गणना के बाद घटाना:

int top = ((RAND_MAX + 1)/n) * n - 1; 

हालांकि, अगर RAND_MAXINT_MAX के बराबर थे, तो गणना अतिप्रवाह होगा, कि से बचने के लिए, गणना की शुरुआत में n घटाना, और अंत में फिर से जोड़ें:

int top = (((RAND_MAX - n) + 1)/n) * n - 1 + n; 

Answer 2

अंतर्निहित समस्या यह है: मान लीजिए कि आपके पास यादृच्छिक संख्या जनरेटर my_rand() है जो 0 से 6 के मूल्य का उत्पादन करता है, और आप 0 से 5 के मूल्यों को शामिल करना चाहते हैं; यदि आप अपना जनरेटर चलाते हैं और my_rand() % 6 लौटाते हैं, तो आपको एक समान वितरण नहीं मिलेगा। जब my_rand() 0 देता है, तो आपको 0 मिलता है; जब यह 1 लौटाता है, तो आपको 1, आदि प्राप्त होता है जब तक my_rand() रिटर्न 6; उस स्थिति में my_rand() % 6 0 है। तो कुल मिलाकर, my_rand() % 6 किसी अन्य मान के रूप में अक्सर दो बार वापस आ जाएगा। इसे ठीक करने का तरीका 5 से अधिक मानों का उपयोग नहीं करना है, यानी my_rand() % 5 के बजाय आप एक लूप लिखते हैं और my_rand() से मानों को त्यागते हैं जो बहुत बड़े होते हैं। यह अनिवार्य रूप से प्रश्न में कोड क्या कर रहा है। मैंने इसका पता लगाया नहीं है, लेकिन सामान्य कार्यान्वयन n के सबसे बड़े एकाधिक की गणना करना है जो RAND_MAX से कम या उसके बराबर है, और जब भी rand() उस मान को अधिक देता है जो उस एकाधिक से अधिक है, तो वापस जाएं और एक नया मान प्राप्त करें।

Answer 3

मैं कोड है कि शीर्ष गणना के माध्यम से पता लगाने नहीं था, लेकिन RAND_MAX सबसे बड़ा मान है कि rand() लौट सकते है ; (RAND_MAX + 1)/n * n एक बेहतर छत होगी, लेकिन RAND_MAX कहें, INT_MAX, परिणाम अप्रत्याशित होगा। तो शायद वह कोड ओवरफ्लो से बचने की कोशिश कर रहा है।